Thursday, July 18, 2024
HomeProgrammingSingle Number | Leetcode 136 | 100 Days of Code Day 9

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

-

Home » 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!

Vamsi Tallapudi
Vamsi Tallapudi
Architect Technology at Cognizant | Full Stack Engineer | Technical Blogger | AI Enthusiast

LEAVE A REPLY

Please enter your comment!
Please enter your name here

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

LATEST POSTS

3 Sum | Leetcode #15 | 100 Days of Code Day 10

Today we are going to solve 3 Sum - our first Medium Level Array problem from Coderefer DSA Sheet. If you are new to this...

Best Time to Buy and Sell Stock – Day 7 | 100 Days of Code

Welcome to Day 7 of 100 Days of Code where today we solve yet another most frequently asked easy array problem called - Best Time...

Contains Duplicate – Day 8 | 100 Days of Code

Welcome to Day 8 of 100 Days of Code and today we are going to solve yet another easy-level problem - Contains Duplicate as part...

Two Sum – Day 6 | 100 Days of Code

Welcome to Day 6 of 100 Days of Code where we solve the most frequently asked Easy level Array problem - Two Sum. Let us...

Follow us

1,358FansLike
10FollowersFollow
397SubscribersSubscribe

Most Popular