Python Challenge 5 - Single Numbers

The challenge difficulties starts from easy and ends at medium.

Single Numbers

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

  1. Your algorithm should have a linear runtime complexity.
  2. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1] Output: 1

Example 2:

Input: [4,1,2,1,2] Output: 4

Follow Up - Single Numbers II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

  1. Your algorithm should have a linear runtime complexity.
  2. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2] Output: 3

Example 2:

Input: [0,1,0,1,0,1,99] Output: 99

Follow up - Single Numbers III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example: Input: [1,2,1,3,2,5] Output: [3,5]

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
Solution
def single_numbers(A):
    '''
    Assumes A is a non-empty integer list where
    all items occur twice except for one.
    '''
    result = A[0]
    for i in range(1, len(A)):
        result ^= A[i]
    return result

This solution is sub-optimal in terms of space complexity because creating a set uses extra memory. While it should be possible to do better using bitwise operators, I can’t really wrap my head around the correct way to do so right now.

Solution
def single_number(A):
    '''
    Assumes A is a non-empty integer list where
    each item occurs thrice except for one.
    '''
    return  (3 * sum(set(A)) - sum(A)) // 2

Hints:
You need some kind of state machine to represent all the possible states.
That is, if the problem stated that all elements appears exactly k (k > 1) times and only one element appears p (p > 1, p mod k != 0)times, then you need to have a state machine to represent all k states.

A state machine is like a counter increment each time there is a change of state. Suppose there are 0 to k - 1 states. When an element appear k times, then the state machine resets the state back to state 0. Therefore, you need a mask depending on the binary form of k = k_m, k_m-1, … , k_1. The mask is used to prevent from counting over k. Then you can retrieve the element that appears exactly p times from the state variable k_p. This is possible because all other elements appears exactly k times, when its k times, the variable state k_1.

Then you have to figure how to change the variables in each state when there’s a 1 or a 0 for each input.

I’d like to point something out. These types of coding problems are typical in technical interviews at big-name tech companies and also in competitive coding. The stated difficulty should be interpreted in this context.

For this particular set of problems, finding an optimal solution (one in the required time/space complexity) is not “easy”. It requires familiarity with bit manipulation, which is considered a pretty advanced and non-intuitive topic in Computer Science.

So if you look at this problem and go “There is no way I could solve this… and it’s supposed to be easy?!”, then this is what I would suggest:

  • Forget about optimal solutions and complexity all together. Just try to find a solution as opposed to the best solution. For most problems, it is entirely possible to find a solution that uses only basic programming concepts such as loops, lists, dicts, etc. And even if you ultimately fail, you will learn a lot just by trying.

  • Once you have a working solution, go ahead and Google the problem. Read through other peoples solutions and discussion of the problem. Try to understand what the code is doing and what the high-level concepts are. Just as an example, let’s say people are talking about Quicksort in their solutions. Never heard of it? Try searching on Youtube. There’s a whole bunch of excellent videos from top-tier schools out there.

  • Use your newfound knowledge to improve your own solution.

Okay, so maybe this sounds like a lot of work. And it is. But you can get a lot out it, in terms of both skills and confidence as a programmer. So… just do it! Or at least try. :slight_smile:

Yes, the problem practices on bit manipulation.

Yes, having a naive non optimal solution is better than none. Trying to use basics structures is a good start.

Yes, be flexible and open to new ideas and suggestion. Sometimes, people give a well written comment in a form of a tutorial. Other resources also helps in learning.

There is always some point in time to you have to start to learn. Why not start now and start early! You can do it. Takes a lot of practice and study to build confidence. The confidence will come slowly but eventually.

1 Like

Yeah, that’s where I’m stuck. I need to take a step back and review bit manipulation and operators. I (more or less) get how masks work in the context of bit flags but not here.