Write a C program that declares an array of length N containing integers between 1 and N, determine if it contains any duplicates.

Question

1.00/5 (3 votes)

See more:

Hi All,

Could someone please help me on the below question

What I have tried:

Hi All,

Could someone please help me on the below question.

Posted 30-Jul-22 3:58am

Manohar7370

Updated 30-Jul-22 5:11am

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2022-07-30T05:11:00

Solution 2

0x01AA has suggested a good idea, but a simpler (and more efficient) solution is to sort the array of values. Once in order, duplicates are next to each other, so a single pass through the array will identify if it contains any duplicates very quickly and easily as they will be next to each other.

Have a think about it, and you'll see what I mean.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]

Posted 30-Jul-22 5:11am

OriginalGriff

Comments

0x01AA 30-Jul-22 11:17am

5. And more, your solution works also in case the 'values' are not in the range '1...N'.
Sometimes(?) my brain is shorted, *blush* :D

[Edit]
'more efficient': Now sorting is not cheap. But again, your solution is much better/universal.

OriginalGriff 30-Jul-22 14:10pm

Sorting isn't free, but Quicksort doesn't use too much memory and is pretty quick (there are "cheaper" sorting algorithms if the sample size is small enough).

Having a count array that is the sample space size can get very expensive in terms of memory at large samples!

But you know this - I'm only mentioning it because it's likely the OP doesn't!

0x01AA · Answer 2 · 2022-07-30T04:31:00

Have first a look to 'Solution 2'. It is much easier and universal and in general better ;)

This is your task to solve to learn c.
Therefore I will not give you the solution, but a hint.

Instanciate two arrays of integers, both with the size N.
Let's name them:

Values    // The values you need to evalate
Counts   // Don't forget to initialize all elements with 0

Values will hold the numbers you need to evaluate.
Loop over Values and count the corresponding number in Counts. Something like:

countIx= Values[valueIx] - 1;  // Think about why here '-1'
Counts[countIx]= Counts[countIx] + 1;

After all that you can loop over Counts and e.g. show how many time a number occured in Values.

Hint: What is fundamental here is that the indices of the array Count have a unique relationship to the values in Values. Try to understand the relationship, it has to do with the '-1' mentioned above.

[Edit]
Important: Be aware, this solution works only because of the restriction that the numbers to evaluate need to be in the range 1...N.

I hope it gives you an idea.