Home Arrays Single non-repeating number

Single non-repeating number

by nikoo28
0 comment

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).
Fig: Converting array to hash-map
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.

A \oplus A = 0
A \oplus 0 = A

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; }

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:
0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More