How to Answer: Find a singlet number.
Advice and answer examples written specifically for a JavaScript Advanced Level Bit Manipulation job interview.
2. Find a singlet number.
This interview question concentrates on using JavaScript maps and manipulation.
You are given an array of integers nums of length n. All the numbers appear three times except one number i.e n - 1 number appears thrice and 1 number appears once. Your task is to find a single number. Every number is a 32-bit integer.
/*Example*/
Given:-nums = [1, 2, 2, 2]
Expected output: 1
Given: nums = [2, 3, 4, 2, 4, 4, 2]
Expected output: 3Solution:
Approach I (check every bit):
There are a total of 32 bits in the given integers. The rightmost bit (least significant bit) is the 0th bit, and the leftmost bit (most significant bit) is the 31st bit. A bit is known as a set if its value is 1, and it is known as reset if its value is 0.
We will iterate over each bit and each number. For the ith bit, we will count the numbers in which it is set. If the ith bit is set in a number that appears thrice, the count will be increased by 3. If it is set in a number that appears once, its count will be increased by 1.
After iterating over each number, if the ith bit is set in the desired number (the number which appears once), the value of count will give remainder 1 when divided by 3 (e.g 1, 4, 7, 10, ...); and if the ith bit is reset in the desired number, the value of cout will be divisible by 3. For example, take array [2, 3, 4, 2, 4, 4, 2]
bit position 3 2 1 0
2 => 0010 0 0 1 0
3 => 0011 0 0 1 1
4 => 0100 0 1 0 0
2 => 0010 0 0 1 0
4 => 0100 0 1 0 0
4 => 0100 0 1 0 0
2 => 0010 0 0 1 0
count = 0 3 4 1 (count for ith bit)
rem = 0 0 1 1 (remainder when divided by 3)
The bits with remainder = 1 are set in the number which appears only once.
So, we will check the count for every bit from 0 to 31. For each bit, we will loop over each number. To check if the ith bit is set in a number, we will use bitmasks. For ith bit, the bitMask = 1 << i. So if i = 2, bitMask is 100 (1 is shifted left by 2 places). Then we will take bitwise AND of bitMask with the number. If the result is non-zero, then the ith bit is set in the number, otherwise, it is not.
/**
* @param {number[]} nums
* @return {number}
*/
function singleNumber(nums) {
let res = 0
for (let i = 0; i < 32; i++) {
let count = 0
for (const num of nums) {
const bitMask = 1 << i
const hasSetBit = (bitMask & num) !== 0
if (hasSetBit) count++
}
count %= 3
res = res | (count << i)
}
return res
}Time complexity- O(32 * n) = O(n)
Space complexity- O(1)
Approach II (bit sets):
Let’s interpret the xor operation in a new way. Say we have an expression set ^ val. This expression performs:-
1. Add val to the set if it not already there (which is essentially num ^ 0 = num)
2. Remove val from the set if it is already present in the set (which is essentially num ^ num = 0)
Let ones and twos be the two sets (integers actually) that keep track of the numbers which appear once and twice respectively. We will iterate over each number. Let num be the current number. We will add it either to ones using ones ^ num. or to twos using twos ^ num.
1. We add num to ones only if it is not already present in twos. We will do it using ones = (ones ^ num) & ~twos.
2. And we add num to twos only if it is not already present in ones. We will do it using twos = (twos ^ num) & ~ones
Now, let’s see what the negation operator (~) does. Let us consider:-
ones = (ones ^ num) & ~twos
To understand this, we will focus on individual bits instead of the whole number. The ith bit is set when a num has ith bit set and it appears for the first time. When num appears the second time, the ith bit is reset in ones (and is set in twos). When the number appears third, we don’t take any action because it is already there in twos. For the ith bit
----------------------------------------------------------------------
situation ith bit ith bit ith bit ith bit in ones after evaluation
in ones in num in twos
----------------------------------------------------------------------
bit not in 0 1 0 (0 ^ 1) & ~0 = 1 & 1 = 1
ones, also
not in twos
----------------------------------------------------------------------
bit not in 0 1 1 (0 ^ 1) & ~1 = 1 & 0 = 0
ones, but ith bit is not set again (the num
already in twos appeared for third time)
----------------------------------------------------------------------
bit already 1 1 x (1 ^ 1) & ~x = 0 & x = 0
in ones the bit is removed from ones
irrespective of twos
----------------------------------------------------------------------
So we can see that the bit (hence the number) is added to ones if it is not already present in twos and it is removed from ones if it is already there. The same is true for twos. After the loop, ones will contain the number which appears exactly once, that is, our desired number.
/**
* @param {number[]} nums
* @return {number}
*/
function singleNumber(nums) {
let ones = 0
let twos = 0
for (const num of nums) {
ones = (ones ^ num) & ~twos
twos = (twos ^ num) & ~ones
}
return ones
}Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021