gocool
BAN USER- 0of 0 votes
AnswersI have an array of size N integers from 0 to n-1. Exactly one of them occurs odd number of times(instead of some other integers). Find that number in O(N) running time and O(1) space complexity.
- gocool in United States
I am pretty sure i would have to use bitwise XOR. But doing that will just give the XOR of all distinct integers.| Report Duplicate | Flag | PURGE
LiveRamp Software Engineer / Developer Algorithm
I assume that you want to find two numbers such that index of the second number is greater than the first and their difference is minimum..(in the case given i suppose its 5 - 20 = -15.
We could use the dynamic programming approach since space is not an issue. You create another array - partner[i] denoting the index of the other element such that the difference is minimal(min a[i] - a[j] && partner[i] = j)
this takes O(n).
@nitin:
I am not sure how you interpret it. But this is what it is.
The question is that there is an array of size N and values range from 0 to N-1. Every integer occurs once except one that occurs odd number of times(instead of some of the integers - so atleast two of the numbers in the sequence from 0 to N-1 is missing). We find that number that occur odd number of times( > 1).
Replushililly, Area Sales Manager at ASAPInfosystemsPvtLtd
I am Graphic designer from Watertown. a professional within the graphic design and graphic arts industry assembles together images, typography ...
we could use a technique called reference counting. Assuming single linked list and we only have pointer to the head of each of them. We go through any one list and assign an integer to each node that keeps track of number of pointers to it.
- gocool January 31, 2013When we traverse the second time, we would hit a node whose count is already one. So, that is the common node. So we end travelling atmost O(n + m) possibly less as it is given that the list continues after they meet.