You have an array of number/characters. If there is a number which occurs exactly n/2 times.
and all other elements in the set/array are distinct, can you find the the repeating number?
Expected time complexity : O(n)
Expected space complexity : O(1)
What if the other members are not distinct?
Can we solve the problem in O(log n) time complexity? (distinct and / or not distinct)
Source : http://inder-gnu.blogspot.com/2009/08/number-occuring-n2-times.html
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)
-
▼
August
(13)
- ping.fm - better than friendfeed, just what I want
- Rope Escape
- [ALGO] Six Colored Balls
- svn:ignore
- Find if there is only one bit set in a number
- [PS] Catch the Fox
- Algorithms from "100 Interview Questions for Softw...
- All purpose problem solving algorithm
- [ALGO] Water jugs problem
- Find if number occurs exactly n/2 times in an array
- Dividing array into groups
- Sort on second key when, first key in a set is sorted
- Find if summation of numbers from two lists is giv...
-
▼
August
(13)
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 :)
4 comments:
We need 3 pointers :
ptr1 -> first element
ptr2 -> second element
ptr3 -> third element
while(end of array is reached) {
if(any one of ptr1/2/3's value is equal) {
then return the match
}
else
{
ptr1<-ptr2<-ptr3<-next element
}
}
Time complexity : O(n)
Space : O(1)
Another interesting solution could also be (got this from an interview discussion) :
1.> Make the input data circular (array / list - data storage / representation)
2.> Do a adjacency check - two a's together
3.> Do a distance = 1/2 check - two separated by one/two char
I've another soln, I havnt thought it through but I think it meets req.
1. Create an array of 10, its each index stores the count for number of times no from 0-9 appears.
2. Create a similar array to store character occurrences.
3. Now traverse the list zero to end and keep updating the counter corresponding to each character.
4. In the end you should have count for all, you can just traverse the list again to check if any of it is n/2.
@Bhavin
Solution will work for characters & digits - not for numbers / strings etc..
Post a Comment