sendtonirav
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
tech-queries.blogspot.com/2011/06/get-maximum-sum-from-coins-in-line.html
- sendtonirav April 09, 2014Comment hidden because of low score. Click to expand.
0
of 0 vote
Find one occurrence where two consecutive numbers are the same, that's the non-unique number. O(n) comparisons.
The only case where there won't be any pair of the non-unique number (with n/2 occurrences) will be when they are all on all odd or all even positions in the array.
Eg [1,100,2,100,3,100,4] OR [100,1,100,2,100,30]. In this case just compare the first and the third number, if they are the same first number is the non-unique number else the second one is. 1 more comparison.
So worst case will be n+1 comparisons, which is O(n)
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
codepad.org/Q9pcHDPj
- sendtonirav May 15, 2014