0

Suppose an array is given, all elements occur N times, but only one occur K time.

Examples:

N=3, K=1, A = [1,1,1,2,2,3,3,3,4,4,2,4,5]

N=2, K=1, A = [1,1,2,2,3,3,4]

I've just viewed the two threads below:

Number which occurs only once in the array; Using XOR operation, it seems easy to solve this problem when k is odd and n is even.

Given an array that contains all elements thrice except one. Find the element which occurs once. it's harder to find an O(N) of time complexity and O(1) of space complexity algorithm to solve this one.

Can any buddies to give some thoughts on this? Whether is it solvable or not?

Community
  • 1
  • 1
Allen Koo
  • 1,996
  • 3
  • 14
  • 15
  • 1
    Pretty sure this is a duplicate, but I can't find the exact question.. The idea is (assuming N%K!=0) to count modulo N for each bit (instead of counting modulo 2 for a regular xor), then the bits with a non-zero count give the resultant value. – Nabb Jul 18 '12 at 04:00
  • Thanks, I don't know how to name this question. Maybe I will search other keywords. – Allen Koo Jul 18 '12 at 05:53
  • @Nabb Your solution is not really O(N) time, O(1) space! Since you're using O(N.log R) time and O(log R) space where R is range of elements. – saeedn Jul 18 '12 at 07:01

1 Answers1

0

Is always N bigger than K ? 

if K<N {
until A is not empty {
 take 1st element and remove N times form array A

 catch exeption: element is only K times: return this element;
 }
}
M314
  • 925
  • 3
  • 13
  • 37
  • Thanks. I think I will suppose k < n first. Can you tell me more details about how to remove the 1st element N times from array A. – Allen Koo Jul 20 '12 at 05:22