LeetCode Problem

Approach - 1 || Brute Force Approach

In brute force approach , simply use a map

• create a map

• iterate through the given array and store the appearence of the elements in map

• again iterate through array and check which element appears < 3 times

• return that element

//Java Code
class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : nums){
            map.put(i, map.getOrDefault(i, 0)+1);
        }
        for(int i : nums){
            if(map.get(i) < 3) return i;
        }
        return -1;
    }
}

//C++ Code
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> countMap;
        for (int num : nums) {
            countMap[num]++;
        }
        for (auto it : countMap) {
            if (it.second < 3) {
                return it.first;
            }
        }
        return -1;
    }
};

# Python Code
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count_map = {}
        for num in nums:
            count_map[num] = count_map.get(num, 0) + 1
        for num, count in count_map.items():
            if count < 3:
                return num
        return -1

Approach - 2 || Slightly Optimized Approach || Using Bit

This solution is based on the concept of bitwise manipulation and is designed to find the single number in the array that appears exactly once while all other numbers appear three times.

Here's the approach behind it:

1. Iterating over each bit position (0 to 31):

   • The outer loop runs from 0 to 31, representing each bit position in an integer (assuming 32-bit integers).

2. Counting the number of set bits:

   • For each bit position, the inner loop iterates through all elements in the nums array.

   • It checks if the bit at the current position is set for each number using bitwise AND operation: (nums[j] & (1 << i)).

   • If the bit is set, it increments the count cnt.

3. Determining the single number:

   • After counting the set bits for each bit position, if the count cnt modulo 3 equals 1, it means that the single number has a set bit at that position.

   • In such cases, the bit at that position is set in the result ans using bitwise OR operation: ans |= (1 << i).

4. Returning the result:

   • After iterating over all bit positions, the final value of ans contains the bits of the single number that appear once in the array.

   • The function returns ans, which represents the single number that appears exactly once.

// Java Code
class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i = 0; i < 32; i++){
            int cnt = 0;
            for(int j = 0; j < nums.length; j++){
                if((nums[j] & (1 << i)) != 0) cnt++;
            }
            if(cnt % 3 == 1) ans |= (1<<i);
        }
        return ans;
    }
}

// C++ Code
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i = 0; i < 32; i++){
            int cnt = 0;
            for(int j = 0; j < nums.size(); j++){
                if((nums[j] & (1 << i)) != 0) cnt++;
            }
            if(cnt % 3 == 1) ans |= (1 << i);
        }
        return ans;
    }
};

# Python Code
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            cnt = 0
            for num in nums:
                if (num & (1 << i)) != 0:
                    cnt += 1
            if cnt % 3 == 1:
                ans |= (1 << i)
        return ans

Approach - 3 || More Optimized || Sorting

Below are the steps for this approach -

1. Sort the array nums in non-decreasing order.

2. Iterate through the array with a step of 3, comparing each element with its previous element.

3. If the current element is not equal to its previous element, return the previous element because it indicates the single number.

4. If no single number is found in steps 2 and 3, return the last element of the array.

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

// C++ Code
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i = 1; i < nums.size(); i += 3){
            if(nums[i] != nums[i - 1]) return nums[i - 1];
        }
        return nums[nums.size() - 1];
    }
};

# Python Code
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(0, len(nums), 3):
            if nums[i] != nums[i - 1]:
                return nums[i - 1]
        return nums[-1]

Approach - 4 || Optimal Approach || Concept of Bucket

This solution uses bitwise operations to find the single number.

• ones represents the bits that appear once.

• twos represents the bits that appear twice.

During each iteration:

• Update ones by performing XOR operation between ones and the current number, excluding the bits that also appear in twos.

• Update twos by performing XOR operation between twos and the current number, excluding the bits that also appear in ones.

At the end of the loop, the value of ones represents the single number.

// Java Code
class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0;
        int twos = 0;
        for(int i = 0; i < nums.length; i++){
            ones = ones ^ nums[i] & ~twos;
            twos = twos ^ nums[i] & ~ones;
        }
        return ones;
    }
}

// C++ Code
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
};

# Python Code
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones = 0
        twos = 0
        for num in nums:
            ones = (ones ^ num) & ~twos
            twos = (twos ^ num) & ~ones
        return ones

That's it !
Thanks for the reading the entire blog.

Connect me on X - @DexterIfti