Algorithm that uses bit masking to generate all possible subsets from a given array with a chosen data type.
1) Template is used to give the flexibility of chooseing the data type.
2) Create 2D vector of size (1<<(array size)) = 2^(array size)
3) Loop on all masks of size (2^(array size))
4) In each mask iteration loop on the given array
5) if((mask >> i) & 1) is the i-th bit of this mask 1?
true: push in result vector of mask as index the array element.
false: continue
- Time Complexity : O(N * 2^N)
- Space Space : O(N * N)
- Trivial to iterate over all possible subsets of N-element, as a N-bit value represents a subset.
- Problem must have small constraints as Bitmasking takes up to exponential time.
Given a positive integer N, print count of set bits in it. Set Bits are the no. of bits that are 1.
Example 1 : Input : N = 6
Output : 2
Example 2 : Input : N = 8
Output : 1
- This algorithm is of fast approach as mentioned in code.
- Given a number N.
- Run the while loop till number is greater than 0.
- Do Bitwise AND operation of that number to its preceding number.
- Assign the result to that original number.
- Increment the counter by 1.
- Return the counter.
Time Complexity : O(n log n)
Space Complexity : O(1)
Given two positive integers X and Y. Let’s define W such that Y AND W = W. The task is to maximize the expression X XOR Y.
Example 1 : Input: X = 11 Y = 4 Output: 15
Example 2 : Input: X = 9 and Y = 13 Output: 13
- Take the two inputs X and Y, pass through the function (Maximize Expression) to maximize the expression.
- We initialize our result with A.
- Next we will consider the ith bit of W to be 1.
- Next step will invlove calculating the value of (Y and bitofW).
- We check if the bitofW satifies the expression- (Y and W=0).
- Finally we check if bitofW can maximize (X xor W).
- And thus, we return our ans.
Time Complexity : O(MAX)
Space Complexity : O(1)