Bit Manipulation¶

/*QUESTION:-
Given a 32-bit unsigned integer num and an integer i, perform the following operations on the number:
1. Get the ith bit.
2. Set the ith bit.
3. Clear the ith bit.

Note: The bits are indexed from 1 instead of 0 (1-based indexing).

Example:
Input: 70, 3
Output: 1 70 66
Explanation:
- The bit at the 3rd position from the least significant bit (LSB) is 1. (1 0 0 0 1 1 0)
- The value of the given number after setting the 3rd bit is 70.
- The value of the given number after clearing the 3rd bit is 66. (1 0 0 0 0 1 0)

Approach:
1. Subtract 1 from i to adjust the index to 0-based.
2. To get the ith bit, perform a bitwise AND operation between num and (1 << i). If the result is non-zero, the ith bit is set; otherwise, it is cleared.
3. To set the ith bit, perform a bitwise OR operation between num and (1 << i).
4. To clear the ith bit, perform a bitwise AND operation between num and the complement of (1 << i).

CODE:*/
void bitManipulation(int num, int i) {
    i = i - 1; // Adjusting index to 0-based

    // Get the ith bit
    if (num & (1 << i))
        cout << 1 << " ";
    else
        cout << 0 << " ";

    // Set the ith bit
    int set = num | (1 << i);
    cout << set << " ";

    // Clear the ith bit
    int clear = num & (~(1 << i));
    cout << clear;
}

/*QUESTION:
Given a number N and a bit number K, check if the Kth index bit of N is set or not. A bit is called set if it is 1. The position of the set bit '1' should be indexed starting with 0 from the least significant bit (LSB) side in the binary representation of the number.

Example:
Input: N = 4, K = 0
Output: No
Explanation: The binary representation of 4 is 100, in which the 0th index bit from the LSB is not set. So, return false.

Approach:
1. Perform a bitwise AND operation between N and (1 << K).
2. If the result is non-zero, it means the Kth index bit is set (1); otherwise, it is not set (0).

CODE:*/
bool checkKthBit(int n, int k) {
    if (n & (1 << k))
        return true;
    return false;
}

/*
QUESTION:-
Given a positive integer N, determine whether it is odd or even.

Example 1:

Input:
N = 1
Output:
odd
Explanation:
The number 1 is odd.

APPROACH:
To determine whether a positive integer N is odd or even, we can check the least significant bit (LSB) of N. 
If the LSB is 1, the number is odd. If the LSB is 0, the number is even.
We can use the bitwise AND operation with 1 (N & 1) to check the LSB.
If the result is 1, we return "odd". If the result is 0, we return "even".


CODE*/

string oddEven(int N){
    if(N&1)
        return "odd";
    return "even";
}

// Time Complexity: O(1)
// Space Complexity: O(1)

/*
QUESTION:-
Given an integer n, return true if it is a power of two. Otherwise, return false.

Example 1:
Input: n = 1
Output: true
Explanation: 2^0 = 1

Example 2:
Input: n = 16
Output: true
Explanation: 2^4 = 16
*/

/*
APPROACH:
An integer n is a power of two if it has only one bit set (i.e., it is a power of 2).
To check if a number has only one bit set, we can use the bitwise AND operation with (n-1).
If the result is 0, then it is a power of two; otherwise, it is not.

1. If n is less than or equal to 0, return false.
2. Perform the bitwise AND operation between n and (n-1).
3. If the result is 0, return true; otherwise, return false.
*/

bool isPowerOfTwo(int n) {
    if(n <= 0)
        return false;
    if(n & (n-1))
        return false;
    return true;
}

// Time Complexity: O(1)
// Space Complexity: O(1)

/*
QUESTION:
Given a non-negative number N, set the rightmost unset bit in its binary representation. If there are no unset bits, leave the number as it is.

Example:
Input: N = 6
Output: 7
Explanation:
The binary representation of 6 is 110.
After setting the rightmost unset bit, it becomes 111 which is 7.

Input: N = 15
Output: 15
Explanation:
The binary representation of 15 is 1111.
Since there are no unset bits, it remains the same.

APPROACH:
To set the rightmost unset bit in the binary representation of N, we can follow these steps:
1. Check if N+1 is a power of 2. If it is, then N already has all bits set, so return N.
2. Otherwise, perform the bitwise OR operation between N and (N+1). This will set the rightmost unset bit.
3. Return the result.

1. Check if N+1 is a power of 2 by using the isPowerOfTwo function.
2. If it is, return N as it already has all bits set.
3. Otherwise, perform the bitwise OR operation between N and (N+1) and return the result.

CODE:*/
bool isPowerOfTwo(int n) {
    if(n <= 0)
        return false;
    if(n & (n-1))
        return false;
    return true;
}

int setBit(int N)
{
    if(isPowerOfTwo(N+1))
        return N;

    int ans = (N | (N+1));
    return ans;
}

// Time Complexity: O(1)
// Space Complexity: O(1)

/*
QUESTION:
Given two numbers a and b, swap their values without using a temporary variable and return them.

Example:
Input: a = 13, b = 9
Output: 9 13
Explanation: After swapping, the values become 9 and 13.

APPROACH:
To swap two numbers a and b without using a temporary variable, we can use the XOR (^) operation.
1. Set a = a XOR b, which XORs the binary representations of a and b and stores the result in a.
2. Set b = a XOR b, which XORs the new value of a (after step 1) with the original value of b, and stores the result in b.
3. Set a = a XOR b, which XORs the new value of a (after step 1) with the new value of b (after step 2), and stores the result in a.
4. The values of a and b are swapped.

CODE:*/
pair<int, int> get(int a, int b){
    a = a^b;
    b = a^b; 
    a = a^b;
    return {a, b};
}

// Time Complexity: O(1)
// Space Complexity: O(1)

/*
QUESTION:
Given two integers dividend and divisor, find the quotient after dividing dividend by divisor without using multiplication, division, and mod operator.

Example:
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 gives a quotient of 3 and remainder of 1.

APPROACH:
To divide two integers without using multiplication, division, and mod operator, we can use a bitwise shifting approach.
1. Initialize a variable ans as 0 to store the quotient.
2. Check if the dividend and divisor have different signs to determine the sign of the quotient.
3. Take the absolute values of the dividend and divisor to work with positive numbers.
4. Iterate while the absolute value of the dividend is greater than or equal to the absolute value of the divisor:
    a. Initialize a variable q as 1 to represent the current quotient digit.
    b. Iterate while the absolute value of the dividend is greater than the absolute value of the divisor left-shifted by q:
        i. Increment q.
    c. Add (1 << (q - 1)) to the quotient ans.
    d. Subtract the absolute value of the divisor left-shifted by (q - 1) from the absolute value of the dividend.
5. Return the quotient ans, considering the sign based on the step 2.

CODE:*/

int divideTwoInteger(int dividend, int divisor) {
    if (dividend == divisor)
        return 1;

    bool isNegative = ((dividend < 0 && divisor >= 0) || (dividend >= 0 && divisor < 0));

    int ans = 0;
    int a = abs(dividend);
    int b = abs(divisor);

    while (a >= b) {
        // at each stage we will find the greatest power of 2 which is smaller than the dividend
        int q = 1;
        while (a > (b << q))
            q++;
        ans += (1 << (q - 1));
        a -= (b << (q - 1));
    }

    return (isNegative) ? -ans : ans;
}

// Time Complexity: O(log n), where n is the absolute value of the dividend
// Space Complexity: O(1)

/*
QUESTION:
You are given a number N. Find the total count of set bits for all numbers from 1 to N (both inclusive).

Example:
Input: N = 4
Output: 5
Explanation:
For numbers from 1 to 4:
- For 1: 0 0 1 = 1 set bit
- For 2: 0 1 0 = 1 set bit
- For 3: 0 1 1 = 2 set bits
- For 4: 1 0 0 = 1 set bit
Therefore, the total set bits is 5.

APPROACH:
The approach to solve this problem is based on the observation that the count of set bits in the binary representation of a number `n` can be determined by the following formula:
countSetBits(n) = countSetBits(pow(2, x - 1) * x) + (n - pow(2, x) + 1) + countSetBits(n - pow(2, x))

CODE:*/
int countSetBits(int n) {
    if (n <= 1)
        return n;
    int x = log2(n); // Find the greatest power of 2 less than n
    return (pow(2, x - 1) * x) + (n - pow(2, x) + 1) + countSetBits(n - pow(2, x));
}

// Time Complexity: O(log(n))
// Space Complexity: O(log(n))

/*
QUESTION:
A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0. Given two integers start and goal, return the minimum number of bit flips required to convert start to goal.

Example:
Input: start = 10, goal = 7
Output: 3
Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps:
- Flip the first bit from the right: 1010 -> 1011.
- Flip the third bit from the right: 1011 -> 1111.
- Flip the fourth bit from the right: 1111 -> 0111.
It can be shown that we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.

APPROACH:
To find the minimum number of bit flips required to convert start to goal, we can iterate over each bit position from right to left and compare the corresponding bits in start and goal. If they are different, we increment a counter. Finally, we return the counter.

CODE:*/
int minBitFlips(int start, int goal) {
    int i = 0;
    int cnt = 0;
    while (i < 32) {
        int startbit = (start >> i) & 1;
        int goalbit = (goal >> i) & 1;
        if (startbit != goalbit)
            cnt++;
        i++;
    }
    return cnt;
}

// Time Complexity: O(log n), where n is the maximum value between start and goal
// Space Complexity: O(1)

/*
QUESTION:
Given an array of N positive integers where all numbers occur an even number of times except one number which occurs an odd number of times. Find the exceptional number.

Example:
Input: N = 7, Arr[] = {1, 2, 3, 2, 3, 1, 3}
Output: 3
Explanation: Number 3 occurs three times, which is an odd number of times, while all other numbers occur an even number of times.

APPROACH:
To find the exceptional number, we can use the bitwise XOR operation. XORing a number with itself results in 0, so XORing all the numbers in the array will cancel out the even occurrences, leaving only the exceptional number in the result.

CODE:*/
int getOddOccurrence(int arr[], int n) {
    int xr = 0;
    for (int i = 0; i < n; i++) {
        xr = xr ^ arr[i];
    }
    return xr;
}

// Time Complexity: O(n), where n is the number of elements in the array
// Space Complexity: O(1)

/*
Question:
You are given two integers L and R, your task is to find the XOR of elements of the range [L, R].

Example:

Input:
L = 4, R = 8
Output:
8
Explanation:
4 ^ 5 ^ 6 ^ 7 ^ 8 = 8
*/

/*
Approach:
The XOR of a range [L, R] can be calculated by XORing the XORs of the individual numbers in the range [1, L-1] and [1, R].
We can observe a pattern in the XOR values based on the remainders of the numbers divided by 4.
Using this pattern, we can calculate the XOR of a given number n by applying some conditions.

1. If n % 4 == 0, the XOR value is n.
2. If n % 4 == 1, the XOR value is 1.
3. If n % 4 == 2, the XOR value is n+1.
4. If n % 4 == 3, the XOR value is 0.

By calculating the XOR values for L-1 and R separately using the above pattern, we can XOR them to get the final result.

Code:
*/

int calculateXOR(int n) {
    if (n % 4 == 0)
        return n;
    if (n % 4 == 1)
        return 1;
    if (n % 4 == 2)
        return n + 1;
    if (n % 4 == 3)
        return 0;
}

int findXOR(int L, int R) {
    int uptol = calculateXOR(L - 1);
    int uptor = calculateXOR(R);
    return uptor ^ uptol;
}

/*
Complexity Analysis:
- The time complexity is O(1) as the calculations are based on simple arithmetic operations.
- The space complexity is O(1) as no extra space is required.
*/

/*
QUESTION:
Given a number N, find its unique prime factors in increasing order.

Example:
Input: N = 100
Output: 2 5
Explanation: 2 and 5 are the unique prime factors of 100.

APPROACH:
To find the unique prime factors of a number N, we can iterate from 2 to sqrt(N) and check if each number divides N.
1. Initialize an empty vector `ans` to store the prime factors.
2. Iterate from 2 to sqrt(N):
   - If `i` divides `N` (i.e., N % i == 0):
     - Add `i` to `ans`.
     - Divide `N` by `i` until it is no longer divisible by `i`.
3. If `N` is still greater than 1, it means that `N` itself is a prime factor. Add it to `ans`.
4. Return `ans`.

CODE:*/
vector<int> AllPrimeFactors(int n) {
    vector<int> ans;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ans.push_back(i);
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        ans.push_back(n);
    return ans;
}

// Time Complexity: O(sqrt(N))
// Space Complexity: O(1) (excluding the space required for the output vector)

/*
QUESTION:
Given an integer N, print all the divisors of N in ascending order.

Example:
Input: 20
Output: 1 2 4 5 10 20
Explanation: 20 is completely divisible by 1, 2, 4, 5, 10, and 20.

APPROACH:
To print all the divisors of a number N, we can iterate from 1 to sqrt(N) and check if each number divides N.
1. Initialize an empty vector `temp` to store the divisors greater than sqrt(N).
2. Iterate from 1 to sqrt(N):
   - If `i` divides `N` (i.e., N % i == 0):
     - Print `i`.
     - If N/i != i, it means N/i is a divisor. Add it to `temp`.(we are checking N/i != i because 6*6 = 36 so our divisor should be 1 time 6)
3. Reverse the elements in `temp` vector.
4. Print all the elements in `temp`.
5. The divisors of N will be printed in ascending order.

CODE:*/
void print_divisors(int n) {
    vector<int> temp;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cout << i << " ";
            if (n / i != i)
                temp.push_back(n / i);
        }
    }
    reverse(temp.begin(), temp.end());
    for (auto it : temp)
        cout << it << " ";
}

// Time Complexity: O(sqrt(N))
// Space Complexity: O(sqrt(N)) (excluding the space required for the output vector)

/*
QUESTION:
Given an integer n, return the number of prime numbers that are strictly less than n.

Example:
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, which are 2, 3, 5, and 7.

APPROACH:
To count the number of prime numbers less than a given number n, we can use the Sieve of Eratosthenes algorithm.
1. Create a boolean vector `primes` of size n+1 and initialize all elements to true. This vector will be used to mark numbers as prime or not.
2. Initialize a variable `cnt` to count the number of primes.
3. Iterate from 2 to n-1:
   - If primes[i] is true (i.e., i is a prime number), increment `cnt`.
   - Mark all multiples of i as false in the `primes` vector, as they are not prime.
4. Return `cnt`, which will be the count of prime numbers less than n.

CODE:*/
int countPrimes(int n) {
    vector<bool> primes(n + 1, true);
    int cnt = 0;
    for (long long i = 2; i < n; i++) {
        if (primes[i]) {
            cnt++;
            for (long long j = i * i; j <= n; j += i) {
                primes[j] = false;
            }
        }
    }
    return cnt;
}

// Time Complexity: O(n log log n)
// Space Complexity: O(n)

/*
QUESTION:
Given a positive number N, compute its prime factorization using the concept of Sieve.

Example:
Input: N = 12246
Output: 2 3 13 157
Explanation: The prime factorization of 12246 is 2 * 3 * 13 * 157.

APPROACH:
To compute the prime factorization of a number N, we can use the concept of Sieve.
1. Create a boolean vector `prime` of size N+1 and initialize all elements to true. This vector will be used to mark numbers as prime or not.
2. Create an empty vector `ans` to store the prime factors of N.
3. Iterate from 2 to sqrt(N):
   - If prime[i] is true (i.e., i is a prime number):
     - While N is divisible by i, add i to the `ans` vector and divide N by i.
     - Mark all multiples of i as false in the `prime` vector, as they are not prime.
4. If N is greater than 1, it means N is a prime number itself, so add N to the `ans` vector.
5. Return the `ans` vector, which will contain the prime factors of N.

CODE:*/
vector<int> findPrimeFactors(int n) {
    vector<bool> prime(n + 1, true);
    vector<int> ans;

    for (int i = 2; i * i <= n; i++) {
        if (prime[i]) {
            while (n % i == 0) {
                ans.push_back(i);
                n /= i;
            }
            for (long long j = (long long)i * i; j <= n; j += i) {
                prime[j] = false;
            }
        }
    }
    if (n > 1)
        ans.push_back(n);
    return ans;
}

// Time Complexity: O(N log(log N))
// Space Complexity: O(N)

/*
QUESTION:
Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Example:
Input: x = 2.00000, n = 10
Output: 1024.00000

APPROACH:
To calculate x raised to the power n, we can use the concept of binary exponentiation.
1. If n is 0, return 1, as any number raised to the power 0 is 1.
2. Initialize a variable res to 1 to store the result.
3. If n is negative, set isNegative flag to true and make n positive.
4. Iterate until n becomes 0:
   - If the least significant bit of n is 1 (i.e., n is odd), multiply res by x.
   - Update x to x^2 by multiplying it with itself.
   - Right-shift n by 1 to remove the least significant bit.
5. If isNegative is true, return 1/res; otherwise, return res.

CODE:*/
double myPow(double x, int n) {
    if (n == 0)
        return 1;
    double res = 1;
    bool isNegative = (n < 0);
    n = abs(n);
    while (n > 0) {
        if (n & 1) { // Check if n is odd
            res = res * x;
        }
        x = x * x; // Update x to x^2
        n = n >> 1; // Right-shift n by 1
    }
    return (isNegative) ? 1 / res : res;
}

// Time Complexity: O(log(n))
// Space Complexity: O(1)