Bit Manipulation and Math DSA Problems

➤ Java Bean with Examples
➤ How to Code a Game
➤ Array Programs in Java
➤ Java Inline Thread Creation
➤ Java Custom Exception
➤ Hibernate vs JDBC
➤ Object Relational Mapping
➤ Check Oracle DB Size
➤ Check Oracle DB Version
➤ Generation of Computers
➤ XML Pros & Cons
➤ Git Analytics & Its Uses
➤ Top Skills for Cloud Professional
➤ How to Hire Best Candidates
➤ Scrum Master Roles & Work
➤ CyberSecurity in Python
➤ Protect from Cyber-Attack
➤ Solve App Development Challenges
➤ Top Chrome Extensions for Twitch Users
➤ Mistakes That Can Ruin Your Test Metric Program

Bit Manipulation and Math DSA Problems | Also see:- Bit Magic, Basic Mathematics

Table of Contents

Minimum Flips to Make a OR b Equals to c

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation. Problem Link:- 1318. Solution. Another similar question: 2220 & it’s duplicate 461

Input: a = 2, b = 6, c = 5 Output: 3 Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

If the current bit of c is 1 then either the current bit of a or b should be 1 if both are 0 then we have to do 1 flip. If the current bit of c is 0 and the current bit of a or b is 1 then we have to make 1 flip but if both of them are 1 then we have to do 2 flips.

public class Test {
    public static void main(String[] args) {
        int a = 2, b = 6, c = 5;
        System.out.println(minimumFlips(a, b, c));
    }

    private static int minimumFlips(int a, int b, int c) {
        int count = 0;
        while (a > 0 || b > 0 || c > 0) {
            boolean ai = (a & 1) == 1;
            boolean bi = (b & 1) == 1;
            boolean ci = (c & 1) == 1;
            if (ci) {
                if (!ai && !bi) {
                    count++;
                }
            } else {
                if (ai && bi) {
                    count += 2;
                } else if (ai || bi) {
                    count++;
                }
            }
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        return count;
    }
}

Sum of Two Integers Without + and – Operators

Given two integers a and b, return the sum of the two integers without using the operators + and -. Problem Link:- 371. Solution

Input: a = 1, b = 2
Output: 3

Input: a = 2, b = 3
Output: 5

public class Test {
    public static void main(String[] args) {
        int a = 2, b = 6;
        System.out.println(sum(a, b));
    }

    private static int sum(int a, int b) {
        while (b != 0) {
            int carry = a & b;
            a = a ^ b;
            b = carry << 1; // carry * 2
        }
        return a;
    }
}

Add Binary

Given two binary strings a and b, return their sum as a binary string. Problem: 67. Solution

Input: a = “11”, b = “1”
Output: “100”

Input: a = “1010”, b = “1011”
Output: “10101”

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (i >= 0)
                sum += a.charAt(i--) - '0';
            if (j >= 0)
                sum += b.charAt(j--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0)
            sb.append(carry);
        return sb.reverse().toString();
    }
}

Reverse Bits

Reverse bits of a given 32-bit unsigned integer. Problem Link:- 190

Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 whose binary representation is 00111001011110000010100101000000.

public class Test {
    public static void main(String[] args) {
        int n = 2;
        System.out.println(reverseBit(n));
    }

    private static int reverseBit(int n) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            ans <<= 1;
            ans = ans | (n & 1);
            n >>= 1;
        }
        return ans;
    }
}

Get, Set, and Clear the ith Bit

Problem Link:- Bit Manipulation

class Solution {
    static void bitManipulation(int num, int i) {
        i = i - 1;
        System.out.print((num >> i) & 1);
        System.out.print(" ");
        System.out.print(num | (1 << i));
        System.out.print(" ");
        System.out.print(num & ~(1 << i));
    }
}

Set the rightmost unset bit

Given a non-negative number n. The problem is to set the rightmost unset bit in the binary representation of n. Problem Link:- Set the rightmost unset bit

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

class Solution {
    static int setBit(int n) {
        int temp = n;
        int i = 0;
        while((temp & 1) == 1){
            i++;
            temp >>= 1;
        }
        return (n | (1 << i));
    }
}

Divide two integers without using multiplication, division, and mod operator

Problem Link:- 29. Solution

public class Test {
    public static void main(String[] args) {
        int dividend = 7, divisor = -3;
        System.out.println(divide(dividend, divisor));
    }

    private static int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE; // Handling overflow case
        }

        if (dividend == 0) {
            return 0;
        }
        if (divisor == 0) {
            throw new ArithmeticException("Divisor cannot be zero");
        }

        // Determine the sign of the result
        boolean negative = (dividend < 0) ^ (divisor < 0);
        long dividendL = Math.abs((long) dividend);
        long divisorL = Math.abs((long) divisor);
        int result = 0;

        while (dividendL >= divisorL) {
            long tempDivisor = divisorL, multiple = 1;
            while (dividendL >= (tempDivisor << 1)) {
                tempDivisor <<= 1;
                multiple <<= 1;
            }
            dividendL -= tempDivisor;
            result += multiple;
        }

        return negative ? -result : result;
    }
}

Find the XOR of numbers from L to R

You are given two integers L and R, your task is to find the XOR of elements of the range [L, R]. Problem Link:- Find XOR of numbers from L to R. Solution

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

Expected Time Complexity: O(1).
Expected Auxiliary Space: O(1).

public class Test {
    public static void main(String[] args) {
        System.out.println(findXOR(4, 8));
    }

    public static int findXOR(int l, int r) {
        return xor(l - 1) ^ xor(r);
    }

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

Bitwise AND of Numbers Range

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive. Problem: 201. Solution.

Input: left = 5, right = 7
Output: 4

Input: left = 0, right = 0
Output: 0

Input: left = 1, right = 2147483647
Output: 0

To solve this problem, you can use bitwise operations to progressively strip off the bits that differ between left and right. The idea is to keep shifting left and right to the right until they become equal, keeping track of the number of shifts. Then, shift the result back to the left the same number of times to obtain the bitwise AND of the range.

class Test {
    public static void main(String[] args) {
        System.out.println(rangeBitwiseAnd(5, 7)); // Output: 4
        System.out.println(rangeBitwiseAnd(0, 0)); // Output: 0
        System.out.println(rangeBitwiseAnd(1, 2147483647)); // Output: 0
    }

    public static int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left != right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }
}

Prime Factorization using Sieve

Problem Link:- Prime Factorization using Sieve

import java.util.ArrayList;
import java.util.List;

public class Test {
    static boolean[] isPrime;
    static int limit = 1000000; // You can set this limit as required

    public static void main(String[] args) {
        sieve();
        int N = 100;
        List<Integer> primeFactors = findPrimeFactors(N);
        System.out.println("Prime factors of " + N + " are: " + primeFactors);
    }

    // Function to compute all prime numbers up to the limit using the Sieve of Eratosthenes
    static void sieve() {
        isPrime = new boolean[limit + 1];
        for (int i = 2; i <= limit; i++) {
            isPrime[i] = true;
        }
        for (int i = 2; i * i <= limit; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= limit; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    // Function to find prime factors of N using the precomputed prime numbers
    static List<Integer> findPrimeFactors(int N) {
        List<Integer> primeFactors = new ArrayList<>();
        for (int i = 2; i <= N; i++) {
            while (isPrime[i] && N % i == 0) {
                primeFactors.add(i);
                N /= i;
            }
        }
        return primeFactors;
    }
}

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

Others

Single Number II

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it. Problem: 137.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Input: nums = [2,2,3,2]
Output: 3

Input: nums = [0,1,0,1,0,1,99]
Output: 99

The key idea behind this approach is to use bitwise operations to count the number of times each bit (0 or 1) appears in the binary representation of all numbers in the array. By counting the bits, we can identify the bits that belong to the number that appears exactly once.

Steps:

  1. Initialize ones and twos: These two integers will help keep track of the bits that appear once and twice respectively.
  2. Iterate through the array:
  • For each number in the array:
    • Update ones to include the bits that appear the first time.
    • Update twos to include the bits that appear the second time.
    • Clear the bits in ones and twos that appear the third time.
public class SingleNumber {
    public static void main(String[] args) {
        int[] nums1 = {2, 2, 3, 2};
        int[] nums2 = {0, 1, 0, 1, 0, 1, 99};

        System.out.println(singleNumber(nums1)); // Output: 3
        System.out.println(singleNumber(nums2)); // Output: 99
    }

    public static int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
}

Explanation:

  1. Variables:
  • ones: Keeps track of bits that have appeared once.
  • twos: Keeps track of bits that have appeared twice.
  1. Bitwise Operations:
  • Update ones: ones = (ones ^ num) & ~twos
    • ones ^ num: XORing ones with num adds the current bits to ones.
    • & ~twos: ANDing with ~twos clears the bits that have appeared twice.
  • Update twos: twos = (twos ^ num) & ~ones
    • twos ^ num: XORing twos with num adds the current bits to twos.
    • & ~ones: ANDing with ~ones clears the bits that have appeared once.
  1. End Result: After processing all numbers, ones will contain the bits of the number that appears exactly once.

Example Walkthrough:
For nums = [2, 2, 3, 2]:

  • Initialization: ones = 0, twos = 0
  • First Iteration (num = 2):
  • ones = (0 ^ 2) & ~0 = 2
  • twos = (0 ^ 2) & ~2 = 0
  • Second Iteration (num = 2):
  • ones = (2 ^ 2) & ~0 = 0
  • twos = (0 ^ 2) & ~0 = 2
  • Third Iteration (num = 3):
  • ones = (0 ^ 3) & ~2 = 1
  • twos = (2 ^ 3) & ~1 = 0
  • Fourth Iteration (num = 2):
  • ones = (1 ^ 2) & ~0 = 3
  • twos = (0 ^ 2) & ~3 = 0

Finally, ones contains 3, which is the number that appears exactly once.

This approach is both time-efficient (O(n)) and space-efficient (O(1)), making it ideal for large input sizes.

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Leave a Comment

Your email address will not be published. Required fields are marked *