Single non-repeating number

1.4K

Let us suppose you are given an array of integers. The special thing about this array is that all numbers are repeated twice except one. Find the single non-repeating number.

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

Example 2:
Input: [4, 5, 5, 2, 2]
Output: 4

Problem statement:

You are given an array of all positive integers. All the integers are repeated exactly twice except one. We need to find that number with a linear time complexity and using the minimum space possible.

Brute Force Method:

When tackling such problems, it is always a good idea to find a working solution first and then try to optimize it. The most obvious solution would be to iterate through the entire array one element at a time. If we find that integer somewhere in between, it means it is occurring twice. If we reach the end of the array and no we don’t find any occurrence, it means that is the unique element, and hence the answer.

But, if you think about this method, it is very much time consuming. What if the unique element in the array is at the very end? We would have been wasting so much time to look for other elements in the array. This would end up in a worst time complexity of O(n^2). Certainly there is an efficient way to solve it.

Optimized Method:

We can reduce the time complexity, by using a hash-map for each integer, and the frequency of each element.

• iterate over each element and create a map to store how many times the element has occurred.
• Iterate over the hash-map and look for the integer that has the frequency ‘1’. The corresponding integer would be the single non repeated element.
• This would solve the problem in O(n) time with a space complexity of O(1).

Space Optimized Method:

A space optimized solution means not taking up extra space to evaluate the result. The above problem can be solved in O(1) extra space but it requires some mathematical magic of bitwise operators. Refer to “Some bitwise operations you should know” to read more about bitwise operators. We would be using 2 properties of XOR operator ( ^ ) or \oplus to solve this problem.

This implies that any integer when XOR’d with itself would give the result to be 0, and if any integer is XOR’d by 0 would give the result as the number itself. One must also know that XOR operator is commutative by nature.

Algorithm:

A step-wise approach would look like:

• Initialize a variable result that would store the XOR’d result of all integers.
• Iterate through the array from start to end.
• XOR the new element with the previous result.
• Once the loop completes, you would have the single non-repeating element. This approach would work because all the other elements in the array would have XOR’d to 0.

Code:

// method to find the unique number
public int singleNumber(int[] nums) {

  // variable to store the xor result of all integers
  int sing = nums[0];

  // start a loop for all elements
  for (int i = 1; i < nums.length; i++) {

    // xor the element with the previous result
    sing = sing ^ nums[i];
  }

  // return the result
  return sing;
}
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(1)

A working solution is available here.
The code is also available on Github.
A similar problem is available on Leetcode.

Video Explanation: