### -synx-'s blog

By -synx-, history, 4 years ago, Given a list of n numbers in which all but one repeat exactly k times, but the remaining one appears less than k times (and at least once).
Find this number (which repeats less than k times).
Expected Complexity
Time  ≤ O(nlgk)
Memory  ≤ O(lgk) Comments (17)
 » Use quicksort to sort in nlogk and then traverse array to find element which occurs less than k times in O(n).
•  » » Storing the elements of list would require O(n) memory!
•  » » » 4 years ago, # ^ | ← Rev. 3 →   Use in place quicksort to do it in O(lgn)
•  » » » » You cant read the elemenets into an array, the memory complexity O(lgk) I mentioned is strict, it does not mean extra space complexity.
•  » » » » » Can you give me the source of the question ??
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   I am not sure but i think you can xor each number in base k to get the solution. It takes O(logk) memory. And O(n*logk) time complexity if you consider xor as constant time operation.
•  » » » » » » Yes, this was my intended idea. But the problem is at the end of xoring in base k, we will get the ans only if it repeats once. (however it can repeat [1, k) times)
•  » » » » » » » I think this may be done in O(klgk considering k
 » 4 years ago, # | ← Rev. 4 →   Hint: for k = 2 we have the classical 'xor all elements' problem. Xorring m-bit numbers is just adding vectors in . Can you generalize this?EDIT: I am assuming here that the number of bits is considered O(1).
•  » » Yes, it can be generalized to xor base k, but the issue that does not arise in k=2 case is that number is present exactly twice or exactly once, which greatly simplifies the problem (the answer is just xor of all numbers),but for general k, how do we retrieve the number which repeats greater than 1 time and less than k times?
•  » » » The number repeats 1 ≤ i < k times, so all positions in the final vector will have their value set to 0 (this bit is turned off in the required number) or to i (this bit is turned on in the required number).
•  » » » » Thank you, I understood your explanation! :)
 » For each bit store the value modulo k. Get the number, divide it by (n%k).
•  » » What if the coefficient of (n%k) is divisible by k, we wouldnt be able to retrieve in that case, right?
•  » » » n % k < k, it represents number of occurences of required number
•  » » » » lets say n=6, k=4,and list is [3, 3, 3, 3, 2, 2],how will your approach work?
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   bit 1 -> 4 -> 0(modulo k)bit 2 -> 6 -> 2(modulo k)num = 4, divide it by (6%4) -> answer is 2