2 JavaScript Advanced Level Bit Manipulation Interview Questions & Answers
Below is a list of our JavaScript Advanced Level Bit Manipulation interview questions. Click on any interview question to view our answer advice and answer examples. You may view 5 answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.
1. Find two singlet numbers.
This interview question concentrates on using JavaScript maps and manipulation.
You are given an array of 32-bit integers. Every number in the array occurs twice except two distinct numbers which occur exactly one time. For example, in an array [1, 2, 5, 1, 3, 5, 2, 4], 1, 2 and 5 occurs twice but two numbers 3 and 4 occur exactly once in the array. You have to implement a function that finds and returns the numbers in the given array which occurs one time.
NOTE- You need to return the required numbers in an array of length 2. The numbers can be in any order.
/*Example*/
Given- [1, 2, 5, 1, 3, 5, 2, 4]
Expected output- [3, 4] or [4, 3]
Given- [100, 48, 73, 48, 73, 41, 100, 15, 16, 16]
Expected output- [41, 15]Solution:
Approach I (using maps):
We can iterate over all the numbers and find their number of occurrences. We will store all the counts on a map. The numbers will be the keys in the map and their number of occurrences will be the values. After iterating over the array, we will find elements in the map with an occurrence equal to 1.
For example, if the given array is [1, 2, 5, 1, 3, 5, 2, 4], the resultant map will be-
{
1 -> 2 // 1 occurs two times
2 -> 2 // 2 occurs two times
5 -> 2 // 5 occurs two times
3 -> 1 // 3 occurs one time
4 -> 1 // 4 occurs one time
}
/**
* @param {number[]} array
* @return {[number, number]}
*/
function findSingletNumbers(array) {
const occurrences = new Map()
for (const num of array) {
const prevCount = occurrences.get(num) || 0
occurrences.set(num, prevCount + 1)
}
const result = []
for (const key of occurrences.keys()) {
if (occurrences.get(key) === 1) {
result.push(key)
}
}
return result
}Time complexity - O(n)
Space complexity - O(n)
Approach II (using bit-manipulation):
Note- all bit positions are 0-indexed from least significant to most significant. Thus the least significant bit is 0 and the most significant bit is 31 (in 32-bit integer).
There are two observations are two be made while xor-ing numbers.
First— the bitwise xor of a number with itself is 0.
More formally,
a ^ a = 0, for every integer a
Second— if some bit position is 1 in xor of two numbers, then that bit position must be 0 in one number and 1 in the other number
More formally,
xxx1xxx
xxx0xxx
xxx1xxx
Now, let the array be the given array.
Let firstNumber and secondNumber are two required numbers.
We will xor all the numbers in the array. The result after XORing all numbers will be xor of firstNumber and secondNumber. It is because the other numbers will vanish by XORing them with themselves as they occur twice. But firstNumber and secondNumber will not vanish as they occur once.
Let xorOfNumbers = firstNumber ^ secondNumber such that xorOfNumbers = xor( of all numbers in array)
Next, we will find the least-significant set bit of xorOfNumbers. This can easily be done using—
leastSignificantBitNumber = xorOfNumbers & (-xorOfNumbers)
Let the ith bit of xorOfNumbers be the least-significant set bit. That is, all the bits from 0 to i - 1 will be 0 in xorOfNumbers.
Let the ith bit of firstNumber is 1. Then, from the second observation, the ith bit in secondNumber will be 0.
Now, we can make two exclusive partitions of the array with one having numbers with the ith bit equal to 1 and the other partition having numbers with the ith bit equal to 0. We will take xor of both the partitions separately. The resultant xor will be our required numbers. Here’s why:
Let firstPartition represent the numbers with the ith bit equal to 1 and the secondPartition represent the numbers with the ith bit equal to 0.
firstNumber belongs to firstPartition
secondNumber belongs to secondPartition
If a repeating number belongs to one partition, then its duplicate also belongs to the same partition.
firstPartition = a, a, b, b, …., firstNumber
secondPartition = p, p, q, q, …., secondNumber
Thus, taking xor of numbers firstPartition will vanish other numbers except for the firstNumber and taking xor of numbers secondPartition will vanish other numbers except for the secondNumber.
/**
* @param {number[]} array
* @return {[number, number]}
*/
function findSingletNumbers(array) {
let xorOfNumbers = 0
for (const num of array) {
xorOfNumbers = xorOfNumbers ^ num
}
const leastSignificantBitNumber = xorOfNumbers & (-xorOfNumbers)
let firstNumber = 0
let secondNumber = 0
for (const num of array) {
if (num & leastSignificantBitNumber) {
// num belongs to firstPartition
firstNumber = firstNumber ^ num
} else {
// num belongs to secondPartition
secondNumber = secondNumber ^ num
}
}
return [firstNumber, secondNumber]
}Time complexity - O(n)
Space complexity - O(1)
Written by S. Kumar on May 22nd, 2021
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