1

I was asked this question in an interview recently.

Given an int array where all but one numbers appear once and exactly one number appears 3 times. Find that number in O(1) space and O(n) time complexity.

How do i approach this question?

user2980096
  • 147
  • 7
  • Are there any constraints on what integers may appear in the array? – user2357112 Nov 26 '17 at 05:26
  • Integers are positive, no other constraints. – user2980096 Nov 26 '17 at 05:27
  • Are you allowed to mutate the input? – user2357112 Nov 26 '17 at 05:27
  • Yes, as long as you satisfy the space and time complexity. – user2980096 Nov 26 '17 at 05:28
  • If its of any help, I was also given a hint where i was asked to try implementing my own xor function. – user2980096 Nov 26 '17 at 05:29
  • Interesting. I've heard he famous interview problem where all of the numbers appear three times, except one that appears once. Answers to that question are plentiful online....maybe you could tweak a solution to that problem to solve the problem you are given. – Ray Toal Nov 26 '17 at 05:42
  • 3
    Any interviewer that uses an interview question like this is more interested in proving his own superiority over the candidate than he is in finding out whether the candidate is any good. That's a pretty good piece of evidence that this isn't somewhere that you want to work. – btilly Nov 26 '17 at 05:50
  • 1
    @user2980096 Did you see [this](https://stackoverflow.com/questions/8260232/algorithm-to-find-a-duplicate-entry-in-constant-space-and-on-time?noredirect=1&lq=1) link? I do not read it carefully but it shows an lower bound to find duplicate... – Bonje Fir Nov 26 '17 at 10:45

1 Answers1

1

Simply sort the array and find the answer.

Note: Since the array has integer values you can use Radix sort algorithm which has linear time-complexity. Moreover, you can use it as an in-place algorithm.

PS: The thrice is the illusion data and the original problem was the interviewee can think as simple as sorting problem. How much this expectation is fair is respect to the level of interview!

Bonje Fir
  • 787
  • 8
  • 25