Welcome, %1$s. Please login or register.

December 12, 2017, 12:03:37 PM
: 1
: Find the repeating numer  ( 4843 )
« : May 19, 2007, 11:48:57 AM From Ria»



Find the repeating numer


You are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (Example: 1 2 3 3 4 5).

How can you find the repeating number?

 
Liked It? Share it!

              


« #1 : May 21, 2007, 12:21:31 AM From Sarbartha Senupta»

for(i=0;i<n;i++)
      {
        if(a==i) { c=i; break;}
       }
printf("the repeted no. is %d",c);


====================================
with the above calculation we can solve the problem.
« #2 : May 21, 2007, 12:30:25 AM From Sarbartha Sengupta»

for(i=0;i<n;i++)
      {
        if(a==i) { c=i; break;}
       }
printf("the repeted no. is %d",c);


====================================
with the above calculation we can solve the problem.

« #3 : May 21, 2007, 07:08:23 PM From Deepak»

Solution -1
As the upper limit is given.. use hashing.. it'll give the solution in O(n)

Solution -2
Sum the numbers of the array and subtract if from the sum of the first n natural numbers.
i.e., let s be the sum of the array
then the missin number is
number = (n(n+1)/2) - s

others solutions are welcome i also want to know more solution for this problem  ???
« #4 : May 21, 2007, 09:08:06 PM From Prateek»

Sarbartha, your solution fits if the numbers are sequential. However, I don't think it would be (though the example is).

Deepak's first solution would require extra space... that too of the O(n). the extra memory constraint can be reduced by using bits to represent n numbers. Suppose if the array is of size 30 then use a integer which will be 32 bits, initially set to 0. Then mark the bit location as you traverse the array as 1. If a value obtained in the array is already set as 1 in its corresponding bit location then that number is a repetition.

However, Deepak's solution 2 is the best I guess. I cannot think of any more optimal solution. Only drawback in this solution is that both the best and the worst case is O(n) unlike solution 1.
« #5 : May 26, 2007, 10:29:36 AM From siva»

build a binary tree with the nos. u ll know if the number exists. however this is more complex than the summin of all nos solution
« #6 : August 20, 2007, 10:31:22 PM From Lokesh»

Deepak,

Could please explain me briefly how the solution2 works to find out the missing number
for the following examples

1)  1 1 2 3

My interpretation

n=4

number= (n(n+1)/2) - s = 10 - 7 = 3


2)  1 2 3 3

My interpretation

n=4

number= (n(n+1)/2) - s = 10 - 9 = 1


I think
missing number = n - number

Please give your comments.
« #7 : November 14, 2007, 07:31:00 PM From Rahul»

use method of arrngingd no. in increasing order
put the constraint if == then print no n break
« #8 : November 22, 2007, 11:23:55 PM From spazinvader»

What about this?
for(i=0;i<n;i++)
if(a==a[i+1])
{
printf("Missing number:%d",i);
break;
}

It will be more optimal right?
« #9 : January 22, 2008, 10:09:07 AM From thequark»

@spazinvader: The numbers need not be in increasing order. The problem statement doesnt mention this even if the example is given with sorted order.

@Deepak: This is not the right solution the difference of the two quantities gives 'difference of omitted number and repeated number'

eg.
5 2 3 4 5.

The ideal sum is 15, the actual sum is 14 the omitted number is 1 and repeated number is 5.

Let us take a trivial example by variables

a b c d e should be the numbers but actually they are a b c e e

So the difference of sum gives
(a+b+c+d+e) - (a+b+c+e+e) = d - e

Now since we have two unknown we would need to have two equations.

Lets take square.

  a^2 + b^2 + c^2 + d^2 + e^2 = SS  (this is n*(n+1)*(n+2)/6 if i am right)
- a^2 + b^2 + c^2 + e^2 + e^2 = SA
-----------------------------------------
d^2 -e^2 = SS - SA

(d-e)*(d+e) = SS - SA

So now we have two _independent_ equations to get both the values, the repeated number and omitted number
« #10 : February 26, 2008, 11:31:48 PM From spazinvader»

@thequark
The problem itself is mentioned as a sequence from 1 to n-1.Hence it should be in increasing order right?
« #11 : February 27, 2008, 12:35:55 PM From thequark»

if it is then the problem is trivial hence i interpreted the problem as that the numbers are _between_ 1 and n but in any order.

This version of the problem is often asked by job interviewers in Indian companies
« #12 : February 28, 2008, 09:32:43 AM From Poonam»

Yes, thequark is right. The example given is in increasing order but the problem doesn't mention it.
: 1
« previous next »

 

Best RatedList All>>



Latest
Random



SMF 2.0.10 | SMF © 2015, Simple Machines | Contact Webmaster | OnlineFunDb.com © 2009/10 | Legal Disclaimer