Solve my interview questions

Question

1.36/5 (8 votes)

See more:

Write a program for the following problem?
You are given an array of number that contain all numbers from 0 to n, in some random
Order, except that one number is missing and another number is repeated (thus, there are still n numbers in the array). Find the missing and repeated number

Posted 27-Jan-14 19:55pm

prasanna.raj

Updated 27-Jan-14 21:40pm

Manfred Rudolf Bihy

v4

Add a Solution

Comments

Sergey Alexandrovich Kryukov 28-Jan-14 2:17am

Please stop spamming this forum with the problem you should solve by yourself. You questions don't require any expert advice or answer, they only require that you do some effort. Don't waste our time and your time, start learning.
—SA

2 solutions

Solution 1

Here I offer you two approaches:

1. Use a BitArray[^] and set the bit corresponding to the current number of the array you are iterating over, but test before you set because if it already is set you'll have your duplicate entry. After you're done with your array iterate over the BitArray to find the bit that isn't set. The index of this bit is the number that was missing from the array.

2. Sort your array in ascending. Iterate over your array and calculate the current element minus the former element. These cases exist:
- The difference is one -> Everything is fine
- The difference is zero -> You've found your duplicate
- The difference is two -> You've found the missing element (former element + 1 or current element - 1)

That's really quite easy to implement.

Regards,

— Manfred

Posted 27-Jan-14 21:33pm

Manfred Rudolf Bihy

Comments

CPallini 28-Jan-14 4:00am

5.
The OP might also find the missing and the repeated number while performing a selection sort (however your first method is faster).

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)

Prasad Avunoori · Accepted Answer · 2014-01-27T23:04:00

C#

static void Main(string[] args)
       {
           // 2 repeated , and 3 missing in the following array
           int[] values = {1,2,2,4,5 };


           Array.Sort(values);
           int leastValue = values[0];
           int highestValue = values[values.Length-1];

           int[] missingValues = new int[highestValue-leastValue+1];
           int[] repeatedValues = new int[highestValue-leastValue+1];
           int[] distinctValues = new int[highestValue - leastValue + 1];
           int j = 0;
           int k = 0;
           int l = 0;

           //Find Missing Numbers
           for (int i = leastValue; i < highestValue; i++)
           {
               if (!values.Contains(i))
               {
                   missingValues[j]= i;
                   j++;
               }

           }


           //Find Repeated Values
           for (int i = 0; i < values.Length; i++)
           {
               if (!distinctValues.Contains(values[i]))
               {
                   distinctValues[k] = values[i];
                   k++;
               }
               else
               {
                   repeatedValues[l] = values[i];
                   l++;
               }
           }

           Console.WriteLine("************MISSING VALUES************************");
           foreach (var i in missingValues)
               Console.WriteLine(i);

           Console.WriteLine("************REPEATED  VALUES************************");
           foreach (var i in repeatedValues)
               Console.WriteLine(i);

           Console.ReadLine();





       }

Try the above code it will help you.
Prasad