Navigation

DSA math bits 11 min read

Math & Bit Manipulation Exercises: Answer Sheet

This is the answer sheet for the math & bit-manipulation exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and a common pitfall. Try the problems first — then check your work here.

Q1. Count set bits

Idea: Repeatedly clear the lowest set bit with n & (n - 1) and count how many times you can do it. The loop runs once per 1-bit, not once per bit position.

Complexity: O(k) time where k is the number of set bits, O(1) space.

int countSetBits(unsigned int n) {
    int count = 0;
    while (n) { n &= (n - 1); count++; }
    return count;
}

int countSetBits(int n) {
    int count = 0;
    while (n != 0) { n &= (n - 1); count++; }
    return count;
}

function countSetBits(n) {
  n = n >>> 0; // treat as unsigned 32-bit
  let count = 0;
  while (n !== 0) { n &= (n - 1); count++; }
  return count;
}

def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

Pitfall: In JavaScript a negative number’s bits include the sign bit; convert with n >>> 0 first or the loop misbehaves. In C++/Java, prefer the built-ins __builtin_popcount / Integer.bitCount in real code.

Q2. Power of two

Idea: A power of two has exactly one set bit, so n & (n - 1) is 0 — but you must exclude 0 and negatives with an explicit n > 0 check.

Complexity: O(1) time, O(1) space.

bool isPowerOfTwo(long long n) {
    return n > 0 && (n & (n - 1)) == 0;
}

boolean isPowerOfTwo(long n) {
    return n > 0 && (n & (n - 1)) == 0;
}

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

Pitfall: Dropping the n > 0 guard lets 0 pass (0 & -1 == 0) and lets negative numbers slip through. The guard is not optional.

Q3. Single number

Idea: XOR every element together. Identical values cancel (x ^ x == 0) and XOR with 0 is the identity, so only the unpaired value survives. No extra memory needed.

Complexity: O(n) time, O(1) space.

int singleNumber(const std::vector<int>& a) {
    int x = 0;
    for (int v : a) x ^= v;
    return x;
}

int singleNumber(int[] a) {
    int x = 0;
    for (int v : a) x ^= v;
    return x;
}

function singleNumber(a) {
  let x = 0;
  for (const v of a) x ^= v;
  return x;
}

def single_number(a):
    x = 0
    for v in a:
        x ^= v
    return x

Pitfall: This works only when the duplicates appear an even number of times and exactly one element is odd-count. If elements repeat three times, XOR no longer cancels them — that needs a different (bit-counting) approach.

Q4. Missing number

Idea: XOR all the indices 0..n together with all the array values. Every present number cancels with its index match, leaving only the missing one. (A sum-based version — n(n+1)/2 - sum — also works but can overflow.)

Complexity: O(n) time, O(1) space.

int missingNumber(const std::vector<int>& a) {
    int x = (int)a.size();              // start with n
    for (int i = 0; i < (int)a.size(); i++) {
        x ^= i;
        x ^= a[i];
    }
    return x;
}

int missingNumber(int[] a) {
    int x = a.length;                   // start with n
    for (int i = 0; i < a.length; i++) {
        x ^= i;
        x ^= a[i];
    }
    return x;
}

function missingNumber(a) {
  let x = a.length;                     // start with n
  for (let i = 0; i < a.length; i++) {
    x ^= i;
    x ^= a[i];
  }
  return x;
}

def missing_number(a):
    x = len(a)                          # start with n
    for i, v in enumerate(a):
        x ^= i
        x ^= v
    return x

Pitfall: Seeding x with n (the array length) is essential — it represents the top of the range 0..n that has no index of its own. Starting from 0 misses that endpoint.

Q5. Fast pow(x, n)

Idea: Binary exponentiation. Square the base and halve the exponent, multiplying the running result whenever the current exponent bit is 1. Handle a negative exponent by inverting the base and negating the exponent.

Complexity: O(log |n|) time, O(1) space.

double myPow(double x, int n) {
    long long e = n;                 // widen so -e can't overflow for INT_MIN
    if (e < 0) { x = 1 / x; e = -e; }
    double result = 1.0;
    while (e > 0) {
        if (e & 1) result *= x;
        x *= x;
        e >>= 1;
    }
    return result;
}

double myPow(double x, int n) {
    long e = n;                      // widen so -e can't overflow for INT_MIN
    if (e < 0) { x = 1 / x; e = -e; }
    double result = 1.0;
    while (e > 0) {
        if ((e & 1) == 1) result *= x;
        x *= x;
        e >>= 1;
    }
    return result;
}

function myPow(x, n) {
  let e = n;
  if (e < 0) { x = 1 / x; e = -e; }
  let result = 1;
  while (e > 0) {
    if (e % 2 === 1) result *= x;   // % avoids 32-bit bitwise pitfalls
    x *= x;
    e = Math.floor(e / 2);
  }
  return result;
}

def my_pow(x, n):
    e = n
    if e < 0:
        x = 1 / x
        e = -e
    result = 1.0
    while e > 0:
        if e & 1:
            result *= x
        x *= x
        e >>= 1
    return result

Pitfall: Negating n directly as a 32-bit int overflows for the most-negative value (-2^31). Widen the exponent to a 64-bit type (C++/Java) before negating. In JS, avoid >> for halving — it truncates to 32 bits; use Math.floor(e / 2).

Q6. Count primes below n

Idea: Sieve of Eratosthenes. Mark multiples of each prime starting from its square; count the numbers below n that stay unmarked.

Complexity: O(n log log n) time, O(n) space.

int countPrimes(int n) {
    if (n < 3) return 0;                 // no primes below 2
    std::vector<bool> composite(n, false);
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (!composite[i]) {
            count++;
            for (long long j = (long long)i * i; j < n; j += i)
                composite[(int)j] = true;
        }
    }
    return count;
}

int countPrimes(int n) {
    if (n < 3) return 0;                 // no primes below 2
    boolean[] composite = new boolean[n];
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (!composite[i]) {
            count++;
            for (long j = (long) i * i; j < n; j += i)
                composite[(int) j] = true;
        }
    }
    return count;
}

function countPrimes(n) {
  if (n < 3) return 0;                   // no primes below 2
  const composite = new Array(n).fill(false);
  let count = 0;
  for (let i = 2; i < n; i++) {
    if (!composite[i]) {
      count++;
      for (let j = i * i; j < n; j += i) composite[j] = true;
    }
  }
  return count;
}

def count_primes(n):
    if n < 3:
        return 0                         # no primes below 2
    composite = [False] * n
    count = 0
    for i in range(2, n):
        if not composite[i]:
            count += 1
            for j in range(i * i, n, i):
                composite[j] = True
    return count

Pitfall: The problem asks for primes strictly below n, so the array size is n and loops use < n. In C++/Java, i * i can overflow int for large i; compute it as a 64-bit value.

Q7. Add two integers without `+`

Idea: XOR adds bit-by-bit ignoring carries; AND-then-shift-left finds where carries go. Repeat until there is no carry left. This is exactly how a hardware adder works.

Complexity: O(1) — at most a fixed number of iterations (one per bit width).

int getSum(int a, int b) {
    while (b != 0) {
        unsigned int carry = (unsigned int)(a & b) << 1; // avoid signed-shift UB
        a = a ^ b;
        b = (int)carry;
    }
    return a;
}

int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

function getSum(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1; // JS bitwise is 32-bit, so this terminates
    a = a ^ b;
    b = carry;
  }
  return a;
}

def get_sum(a, b):
    mask = 0xFFFFFFFF
    while b & mask:
        carry = (a & b) << 1
        a = a ^ b
        b = carry
    a &= mask
    # reinterpret as signed 32-bit
    return a if a <= 0x7FFFFFFF else ~(a ^ mask)

Pitfall: Python integers are arbitrary precision, so a naive loop never terminates for negative inputs (the carry keeps producing higher bits). Mask to 32 bits each iteration and reinterpret the sign at the end. In C++, left-shifting a negative signed value is undefined behavior — shift through an unsigned type.

That’s the full answer sheet. Back to the math & bit-manipulation exercises, or revisit the section overview.