Given an array of size n+1 which contains all the numbers from 1 to n. Find the number which is repeated in O(n) time. How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to n?
Ans
The number appearing 2 times is (sum of all the numbers in the array) - (sum of the numbers from 1 to n). For floating numbers multiply it with 100 and proceed.
Subscribe to:
Post Comments (Atom)
Ok. If I have :
ReplyDelete1 1 3 2 5 4
then {1+1+3+2+5+4} - {1+1+3+2+5} = 4. but it should be 1. right? Or you meant something else?
Find the number which is repeated in O(n) time.
ReplyDeletethe number that is repeated in O(n) time is 4, which you got
No. He meant
ReplyDelete{1+1+3+2+5+4} - {1+2+3+4+5} = 1
Say, Sum of integers from 1 to n, Sn = (n*(n+1))/2
ReplyDeleteSum of integers in the array is Sm. You need to iterate over the array elements to find Sm.
The repeated element would be (Sm-Sn).
I think your interpretation is wrong
ReplyDelete{1+1+3+2+5+4} - {1+2+3+4+5} = 1
your second part is weong..it should be
ReplyDelete{1+1+3+2+5+4} - {1+4+3+2+5}
There seems some confusion... let me know if im wrong...
ReplyDeleteSm = 1+2+3+4+5
Sn1 = 1+3+3+4+5 (smaller is missing and bigger repeated)
Sn2 = 1+2+2+4+5 (bigger is missing and smaller repeated)
Sm-Sn1 = 1
Sm-Sn2 = -1
This will happen for any number.
Sn22 = 1+2+3+4+4
Sm-Sn22 = 1
etc
How do u ppl propose to find which one is missing and which one is repeated ?!?
If we just add the number answer could be any (x,y) where x-y == difference that could be many different pairs. The idea is to add up squares of number ... squares of number is diverging in nature so difference between larger^2 - smaller^2 is unique for a pair of two number larger an
ReplyDeleteThis solution works only when there is one repeated/missing number.
ReplyDelete@above: if array size is n=5 you can have only {1,2,3,4}
we have n+1 elements. if say n=5 we shud have 6 elements but only 1 to (6-1).
ReplyDeletee.g.,{1,2,3,4,5,4}
repeated number = sum of array elements - sum of 1 to n(5)
so, number = 19=15 = 4.
for{1,2,2,3,4,5} number = 17-15 = 2
Naren always you solution will give you the N+1 numbers. That is not the solution.
ReplyDeleteset s of size 5 will contain elements from 1 to 4(as mentioned in the question).
ReplyDeleteeg: s = {1,1,2,3,4}
so the number repeated is
sum(1,1,2,3,4)-sum(1 to 5)
= 11-10 = 1. -> looks correct.
now if the set is restructured as
s={1,1,1,1,1}
now the number repeated is
sum(1,1,1,1,1)-sum(1 to 5)
= 5-10 = -5 ???. -> looks wrong.
Ppl. read the question.
ReplyDeleteIt says that array size is n+1 and elements range from 1 to n
One element is doubled.
So n(n+1)/2 - Sum of all elements = Element doubled.
simple.
ReplyDeletey=xor of all the numbers from 1 to n
now
y= xor y and all the elements of the array(runs in O(n) time.
Finally we have our answer in y. :P
How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to n?
ReplyDeletesince the size of array is n + 1 and the array contains 1-n elements means , sum a[0...n] - sum(1..n) = duplicate no
ReplyDeleteCan someone explain the floating point part of the question? It doesn't even mention how many decimal places. Are we to assume a sequential set like:
ReplyDelete0,.1,.2,...,.9,1.0 or
0,.01,.02,...,.99,1.00 ?
Repeated No = Sum(all n+1 elements) - n!
ReplyDelete{1,2,3,4,5,6,7,7,8,9}
Repeated No = 52 - 45 => 7