DSA / 5 min read
Day 12 of 60 Days of DSA: Bitwise Manipulation-II
Essential Problem-Solving Patterns: Combinations, Contributions, and Bits
Day 12 of 60 Days of DSA: Bitwise Manipulation-II
Essential Problem-Solving Patterns: Combinations, Contributions, and Bits
In this article, we’re going to dig deep into more bit manipulation interview questions. If you have missed part I, do read it here
We’re going to see bit manipulation with different concepts like the contribution technique, logical reasoning.
We’re going to see 3 sets of problems today
- Single Number
- Subarray with Bitwise OR
Problem 1:
Problem Description
Given an array of integers, every element appears thrice except for one, which occurs once.
Find that element that does not appear thrice.
NOTE: Your algorithm should have a linear runtime complexity.
Could you implement it without using extra memory?
Example Input
Input 1:
A = [1, 2, 4, 3, 3, 2, 2, 3, 1, 1]
Input 2:
A = [0, 0, 0, 1]
Example Output
Output 1:
4
Output 2:
1
Example Explanation
4 occurs exactly once in Input 1.
1 occurs exactly once in Input 2.
Intuition
- It’s mentioned that we can’t use the extra space, thus we can’t use HashMap.
- If we use sorting, the complexity would go as high as O(nlogn)
To do it in O(n) complexity, we can use bit manipulation
The approach is to count each bit at a particular position
1. If the bit count at position n of all numbers is a multiple of 3, then the number which does not appear multiple times will have 0 at the 0th bit position
2. If the bit count at a particular position is not a multiple of 3, it means that a single number is contributing to the position, thus the bit will be 1 at the nth position
Example — [1, 2, 2, 1, 2, 3, 1]
Binary format of each number
1 | 01
2 | 10
3 | 11
So we count all 1’s at position 0 = 4 (3 from 1 and 1 from 3)
2nd position = 4 (3 from 2 and 1 from 3)
Thus, we can say at both positions the count is not a multiple of, 3 which deduces the number to have 1 at both bits, making it 11 =3
Code (In JavaScript)
function singleNumber2(A){
let num =0;
for(let i=0; i<32; i++){
let count =0;
for(let j = 0; j<A.length; j++){
count += (A[j] >> i) & 1;
}
num += count%3 == 0 ? 0: (1<<i);
}
return num;
}Complexities
- Time Complexity — O(n)
Where n is the size of the array, as the first loop runs for constant time O(n*32) = O(n)
- Space Complexity — O(1)
As asked in the question
Problem 2:
Problem Description
You are given a binary array A of length N where each element is either 0 or 1. Your task is to count the number of subarrays where the bitwise OR of all the elements in the subarray is 1.
Example Input:
Input 1:
A = [0, 0, 1, 1, 0]
Input 2:
A = [0, 0, 0]
Example Output
Output 1:
11
Output 2:
0
Example Explanation
Explanation 1:
The only subarrays with OR = 1 are
[0, 0, 1], [0, 0, 1, 1], [1], [1], [1, 1], [1, 0], [1, 1, 0], [0, 0, 1, 1, 0], [0, 1], [0, 1, 1], [0, 1, 1, 0]
Explanation 2:
There is no subarray, whose bitwise OR is 0.
Intuition (How to think)
To count a subarray with bitwise OR as 1, only 1 value out of all the elements needs to be 1
So if we count the total number of arrays with all zeroes and subtract it from the total number of subarrays
We’ll get the count of the subarrays where bitwise OR is 1
Code (In JavaScript)
function subArrayWithOr(A){
let n = A.length;
let count =0, subarraysWithZeroes = 0;
for(let i=0; i<n; i++){
if(A[i] == 0){
count++;
}else{
subarraysWithZeroes += (count * (count+1))/2;
count =0;
}
}
let totalSubArrays = (n*(n+1))/2;
subarraysWithZeroes += (count * (count+1))/2;
let subarraysWith1 = totalSubArrays - subarraysWithZeroes;
return subarraysWith1;
}Complexities
- Time Complexity- O(n)
- Space Complexity — O(1)
Do you want to solve more with us?
Then follow this series and share your progress in the comments.
If the topics are difficlt for you to understand, then you can refer to the notes on my GitHub.
Here’s the Code link
At Dev Simplified, We Value Your Feedback 📊
👉 Let us know how you’re finding this series so far. It motivates us to write and provide valuable content for you.
👉 Follow us to not miss any updates.