Find repeating element in array
I felt this question deserves a post of its own. So here it is :
Q5. In an array from 1 to n, one number is present twice. How to do you determine which one?
There are multiple answers - all correct. We would, obviously, aim for the optimized one - benchmark parameters being time & space complexity
Source : Algorithms from 100 Interview Questions for Software Developers
skip to main |
skip to sidebar
"Gebo" means to "give and take". This is my attempt to share the knowledge & experience with the community. Focus on Puzzles, Algorithms, Problem Solving, Java & other Technical Discussions.
About Me
Search Gebo
Share & Subscribe
Books & Knowledge Base @ Amazon
Links
|
| Buttons reused from http://www.webfruits.it/freebies.htm and http://mysocialbuttons.com/ |
Archive
-
▼
2009
(26)
-
▼
September
(9)
- Walk the bridge, in pairs as fast a possible
- Find jar with the contaminated pills
- Algorithms from "100 Interview Questions for Softw...
- Algorithms from "100 Interview Questions for Softw...
- Find the bulb for the switch
- Find direction of rotation
- Pay for 7 days using 1 7-segment gold bar and 2 cuts
- [Probability] Divide 100 marbles into two piles
- Find the poisoned wine barrel
-
▼
September
(9)
Labels / Tag
algorithms
(15)
amazon
(3)
antivirus
(1)
arithmetic series
(1)
array
(5)
backtracking
(1)
bash
(1)
basics
(1)
binary trees
(1)
brindavan garden
(1)
bulb
(1)
C++
(1)
callback
(1)
clam
(1)
clamav
(1)
clock
(1)
CLRS
(2)
cormen
(3)
data structures
(1)
duplicate
(1)
easymock
(1)
education
(1)
excel
(1)
freshclam
(1)
hanoi
(1)
hashing
(1)
httpclient
(1)
humor
(1)
induction
(1)
interview question
(9)
irrational
(1)
Java
(5)
jmockit
(1)
learning
(1)
level_easy
(1)
linux
(3)
logger
(1)
macro
(1)
madhur
(2)
mathematics
(5)
matrix
(1)
microsoft
(6)
mock
(2)
mockito
(2)
mysore
(1)
networking
(1)
OCW
(1)
odd man out
(1)
oocalc
(1)
OOTB
(1)
pattern
(1)
Persistent
(1)
probability
(2)
problem
(1)
problem solving
(17)
proxy
(1)
proxy selector
(1)
puzzle
(5)
quote
(1)
randomized
(1)
recurrsion
(2)
repeating
(1)
resolution
(1)
reverse
(1)
riddle
(5)
road trip
(1)
script
(1)
search
(2)
shell
(1)
shell script
(1)
socks
(1)
solaris
(1)
solved
(1)
sort
(3)
stock
(1)
strategy
(1)
subversion
(1)
summation
(1)
svn
(1)
switch
(1)
tanwani
(2)
TDD
(2)
technology
(2)
theorem
(1)
timer
(1)
todo
(1)
travel
(1)
trees
(1)
tutorial
(1)
unimodal
(1)
unit test
(2)
walk the bridge
(1)
warmup
(1)
water jugs
(1)
windows
(1)
xkcd joke
(1)
© Madhur Kumar Tanwani
All material on this page, is free to use as long as references to the original source is maintained and credits are given to this website as one of the sources. Few clicks on the Ads on this page will help too :)
All material on this page, is free to use as long as references to the original source is maintained and credits are given to this website as one of the sources. Few clicks on the Ads on this page will help too :)
10 comments:
The best solution I could get had the worst case time comparison of n(n-1)/2
I tried applying the mergesort kinda logic as well. Anything better?
Solution :
Find summation of the elements in the array - lets say this is 'x'
Since we know the numbers are from 1 to n, the summation of first 'n' natural numbers is n(n+1)/2 - lets say this is 'y'.
The number that is repeating is
x - y
Time complexity : O(n)
Space complexity : O(1)
A tougher variant of this problem has been solved on Inder's blog : http://inder-gnu.blogspot.com/2007/03/finding-missing-integer.html
From the problem statement I did not realize that the values were constrained from 1 to n.
My bad!
I think its a fair thing.
I assumed that "In an array from 1 to n" meant and array containing elements from '1' to 'n'.
This problem and its variants in multiple places, wee of this type :
* Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?
Your variation is also interesting. I feel following solutions should work in that case :
Solution 1:
1.> Sort the array - (n log n)
2.> Iterate over the array and find the repeating element - O(n)
Overall order O(n log n)
In this case, we might be able to optimize and find the repeating element at the time of sorting itself (while sorting / placing the repeating element, if we encounter the same element, we know the repeating element)
Solution 2:
1.> Iterate over the array
2.> For each element, find if the element repeats in the remaining array
Overall order O(n^2)
Anything better that's possible??
Use a hash. When hash collision happens, it is a duplicate. Time O(n).
Using xor operator is a better solution. Using sum, may cause overflow.
@spsneo
I can think of XOR being helpful if the elements are in sorted order. But that would make the solution a O(n log(n)) solution for unsorted array.
Can you please explain how XOR will help for unsorted arrays?
xor operation is associative and commutative. So it doesn't matter whether the array is sorted or not. It works.
How will XOR give you answer? It will only be correct if all the numbers occur twice except for one number. In that case applying XOR will 'cancel' equal numbers giving us the 'lonely' number... Please tell me if this is wrong.
Post a Comment