LeetCode — Problem num — 136

Hi All, In this blog we will go through the problem of leetcode number 136.

Question -

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

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1]
Output: 1

Analysis —

• As we can see we have array of nums which are non-empty and all numbers will come twice expect one number so we need to find out how to check the one number which is not repeating and we will return the single element.
• Here in question they mention “You must implement a solution with a linear runtime complexity and use only constant extra space.” which means we can traverse once on that array and cannot use extra space. Anyways if we use extra space this problem will be easy to solve as we can use hashmap.
• So here we can try with XOR operator so this we all know in our college days when we were learning embedded code or labs this XOR operator works as below table

source: Google

• If two element are same i.e. 1–1 or 0–0 this will return as “0” and if they are different i.e. 1 and 0 this will return as “1”.
• Lets check example one it is [2,2,1] output will be 1 because 2^ 2 -> 0, 2 ^ 1 -> 1.

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

• Now lets check how we can perform with program

class Solution {
    public int singleNumber(int[] nums) {
      int number=0;
      for(int i=0;i<nums.length;i++){
          number = number^nums[i];
      }  
      return number;
    }
}

• So here we have taken variable “number” and assigned it as “0” because any number xor with 0 is number itself. ( 0 ^ n = n)
• And with one for loop we can check the number with nums length and the number with xor with nums[i] so that any nuber which is duplicate will cancel itself and return as “0”. And last single element will return as “number”. This will give you successful result and program is accepted.
• We have started this series with basic question we will go through multiple question and try to solve it in next blogs.

Happy Reading :)