Single Number | Leetcode 136 | 100 Days of Code Day 9

Welcome to Day 9 of Coderefer’s 100 Days of code where we will be solving problems from Coderefer DSA sheet each day and today we are solving a problem that comes under Easy Level Array Problem – Single Number Leetcode.

Lets quickly look at the problem Statement.

Problem Statement

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

Constraints

1. Implement solution with Linear runtime Complexity

2. Use constant Extra space.

3. Each element in the array appears twice except for one element which appears only once.

Eg:

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

Output: 4 (Since 4 appeared only once and remaining appeared atleast twice).

Solutions for Single Number Leetcode Problem

We will look at various solutions available for the problem.

Solution 1: Using Maps ( Violating given restriction – Constant Space)

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : nums) {
            if(map.containsKey(i)) {
                map.remove(i);
            } else {
                map.put(i,1);
            }
        }
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return -1;
    }
}

Time Complexity: O(N) since we are iterating through all the elements

Space Complexity: O(N) since we are using HashMap

We cannot answer this during our interview because we were given a constraint that we cannot use extra space. So lets look into another ways of approaching this problem.

Solution 2: Using Sorting

Now let us think the problem in a different way. If we sort the given array, then all the same elements fall adjacent to each other. Since each element in the array appears twice maximum, we can increment the iteration by 2. Here’s the code for the same.

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i = 1; i< nums.length; i+=2) {
            if(nums[i] != nums[i-1]) {
                return nums[i-1];
            }
        }
        return nums[nums.length - 1];
    }
}

Time Complexity: O(NlogN) as we are sorting Array and traversing through it

Space Complexity: O(1) As we are not using any extra space

This method can be explained while solving the problem. Are there any other ways to improve TC? Let us explore one more method.

Solution 3: Using Bitwise XOR Operator

XOR or Exclusive OR returns output as true only if both inputs are of opposite kind.

A B Y
0 0 0
0 1 1
1 0 1
1 1 0

Here are the outcomes we can derive by observing XOR Operator.

1. A ^ A = 0
2. A ^ B ^ A = B
3. (A ^ A ^ B) = (B ^ A ^ A) = (A ^ B ^ A) = B (=> Position doesn’t matter)

This implies that Any values repeated twice doesn’t impact at all on the output in the XOR. Hence if we XOR all values, we will be left with odd one, that is, Answer.

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

Time Complexity: O(N) as we are iterating through all the elements in an array

Space Complexity: O(1) as we are not using any additional space

Hope you enjoy gliding through these solution and kudos for making this far! Lets meet in the next interesting article tackling another problem!