Count set bits in an integerEasy2 approaches
Problem
Return the number of 1 bits in the binary form of a non-negative integer (its Hamming weight).
Example 1
Input: n = 11 (1011) Output: 3
Also asked as: number of 1 bits · count total set bits
1. Kernighan’s trick
Time O(set bits)Space O(1)
`n & (n - 1)` clears the lowest set bit; count how many times you can do it.
function countSetBits(n) { let count = 0; while (n) { n &= n - 1; count++; } return count;}2. Shift and mask
Time O(32)Space O(1)
Check the last bit, shift right, repeat 32 times.
function countSetBits(n) { let count = 0; for (let i = 0; i < 32; i++) count += (n >>> i) & 1; return count;}Find the two non-repeating elements (all others appear twice)Medium1 approach
Problem
Every element appears exactly twice, except two elements that appear once. Return those two, in O(n) time and O(1) space.
Example 1
Input: [1, 2, 1, 3, 2, 5] Output: [3, 5]
Also asked as: Find the two non-repeating elements in an array of repeating elements
1. XOR everything, split by a differing bit
Time O(n)Space O(1)
XOR of the whole array = x ^ y. Any set bit in it differs between x and y — partition the array by that bit and XOR each group separately.
function twoNonRepeating(a) { const xorAll = a.reduce((acc, v) => acc ^ v, 0); const bit = xorAll & -xorAll; // lowest set bit let x = 0, y = 0; for (const v of a) (v & bit) ? (x ^= v) : (y ^= v); return [x, y];}Count bits to flip to convert A to BEasy1 approach
Problem
Return how many bits must be flipped to turn integer a into integer b — the number of positions where their bits differ.
Example 1
Input: a = 10 (1010), b = 20 (10100) Output: 4
Also asked as: Count number of bits to be flipped to convert A to B
1. Popcount of A XOR B
Time O(bits)Space O(1)
A ^ B has a 1 exactly where the bits differ.
function bitsToFlip(a, b) { let x = a ^ b, count = 0; while (x) { x &= x - 1; count++; } return count;}Count total set bits in all numbers from 1 to nMedium1 approach
Problem
Return the total number of 1 bits across the binary forms of every integer from 1 to n. Aim for better than looping over each number.
Example 1
Input: n = 4 Output: 5
1 (1) + 10 (1) + 11 (2) + 100 (1).
Also asked as: Count total set bits in all numbers from 1 to n
1. Per-bit contribution
Time O(log n)Space O(1)
For bit position b, the bit cycles with period 2^(b+1): 2^b zeros then 2^b ones. Count full cycles × 2^b plus the partial remainder.
function countTotalSetBits(n) { let total = 0; for (let b = 0; (1 << b) <= n; b++) { const period = 1 << (b + 1); const full = Math.floor((n + 1) / period) * (1 << b); const rem = Math.max(0, ((n + 1) % period) - (1 << b)); total += full + rem; } return total;}Check whether a number is a power of two / find the position of its only set bitEasy1 approach
Problem
(1) Return true if n is a power of two. (2) If n has exactly one set bit, return that bit's position (counting from 1 at the rightmost bit); otherwise return −1.
Example 1
Input: n = 16 Output: power of two: true; position 5
Example 2
Input: n = 12 Output: false; −1
Also asked as: Program to find whether a no is power of two · Find position of the only set bit
1. n & (n − 1)
Time O(log n)Space O(1)
A power of two has exactly one set bit, so n & (n−1) clears it to 0. The bit position is log2(n), or count right shifts until you reach 1.
const isPowerOfTwo = (n) => n > 0 && (n & (n - 1)) === 0;
function onlySetBitPosition(n) { if (!isPowerOfTwo(n)) return -1; let pos = 1; while (!(n & 1)) { n >>= 1; pos++; } return pos; // 1-indexed}Copy set bits in a given range from one number to anotherEasy1 approach
Problem
For every bit position from l to r (1-indexed from the right) that is set in y, set the same bit in x. Return the new x.
Example 1
Input: x = 44 (101100), y = 3 (000011), l = 1, r = 5 Output: 47 (101111)
Also asked as: Copy set bits in a range
1. Build a range mask and OR
Time O(1)Space O(1)
mask = bits [l..r] set. result = x | (y & mask) — copies y’s bits in that range into x.
function copyBitsInRange(x, y, l, r) { let mask = 0; for (let i = l; i <= r; i++) mask |= (1 << (i - 1)); // 1-indexed positions return x | (y & mask);}Divide two integers without *, / or %Medium1 approach
Problem
Divide dividend by divisor without using multiplication, division or mod, and truncate the result toward zero. Clamp the result to the 32-bit signed range.
Example 1
Input: dividend = 10, divisor = 3 Output: 3
Example 2
Input: dividend = 7, divisor = -3 Output: -2
Also asked as: Divide two integers without using multiplication, division and mod operator
1. Repeated doubling of the divisor
Time O(log² n)Space O(1)
Subtract the largest shifted copy of the divisor (divisor << k) that still fits; add 2^k to the quotient. Handle signs and the INT_MIN edge case.
function divide(dividend, divisor) { const INT_MAX = 2 ** 31 - 1, INT_MIN = -(2 ** 31); if (dividend === INT_MIN && divisor === -1) return INT_MAX; const neg = (dividend < 0) !== (divisor < 0); let a = Math.abs(dividend), b = Math.abs(divisor), q = 0; while (a >= b) { let temp = b, multiple = 1; while (a >= (temp << 1)) { temp <<= 1; multiple <<= 1; } a -= temp; q += multiple; } return neg ? -q : q;}Square a number without *, / or pow()Easy1 approach
Problem
Return n² without using multiplication, division or pow().
Example 1
Input: n = 5 Output: 25
Example 2
Input: n = -4 Output: 16
Also asked as: Calculate square of a number without using *, / and pow()
1. n² = sum of the first n odd numbers
Time O(n)Space O(1)
1 + 3 + 5 + … + (2n−1) = n². Add n odd numbers.
function square(n) { n = Math.abs(n); let result = 0; for (let i = 0; i < n; i++) result += 2 * i + 1; return result;}O(log n) via bit shifts: square(n) = (square(n>>1) << 2) + (n odd ? (n<<1) - 1 : 0).
Power set of a setEasy1 approach
Problem
Return all 2^n subsets of a set of distinct elements, including the empty set.
Example 1
Input: [a, b, c] Output: [], [a], [b], [c], [a,b], [a,c], [b,c], [a,b,c]
Also asked as: Power Set
1. Bitmask enumeration
Time O(2ⁿ · n)Space O(1) extra
Every subset ↔ a number 0..2ⁿ−1; bit j set means element j is included.
function powerSet(arr) { const n = arr.length, res = []; for (let mask = 0; mask < (1 << n); mask++) { const subset = []; for (let j = 0; j < n; j++) if (mask & (1 << j)) subset.push(arr[j]); res.push(subset); } return res;}Single NumberEasy1 approach
Problem
Every element appears twice except one. Return that one, in O(n) time and O(1) space.
Example 1
Input: [4, 1, 2, 1, 2] Output: 4
1. XOR everything
Time O(n)Space O(1)
x ^ x = 0 and x ^ 0 = x, so every pair cancels and the single value remains.
const singleNumber = (nums) => nums.reduce((x, n) => x ^ n, 0);Counting BitsEasy1 approach
Problem
For every i from 0 to n, return the number of 1 bits in i's binary form. Aim for O(n) overall.
Example 1
Input: n = 5 Output: [0, 1, 1, 2, 1, 2]
1. DP on i >> 1
Time O(n)Space O(n) output
i has the same bits as i >> 1 plus its lowest bit.
function countBits(n) { const res = new Array(n + 1).fill(0); for (let i = 1; i <= n; i++) res[i] = res[i >> 1] + (i & 1); return res;}Also valid: res[i] = res[i & (i − 1)] + 1 (drop the lowest set bit).
Reverse BitsEasy1 approach
Problem
Reverse the order of the bits of a 32-bit unsigned integer and return the result as an unsigned integer.
Example 1
Input: 43261596 (00000010100101000001111010011100) Output: 964176192 (00111001011110000010100101000000)
1. Shift out, shift in
Time O(32)Space O(1)
Take the lowest bit of n 32 times, appending it to the result. ">>> 0" keeps the result unsigned in JavaScript.
function reverseBits(n) { let res = 0; for (let i = 0; i < 32; i++) { res = (res << 1) | (n & 1); n >>>= 1; } return res >>> 0;}Sum of Two Integers (no + or -)Medium1 approach
Problem
Return a + b without using the + or − operators.
Example 1
Input: a = 1, b = 2 Output: 3
Example 2
Input: a = -2, b = 3 Output: 1
1. XOR for sum, AND-shift for carry
Time O(32)Space O(1)
a ^ b adds without carrying; (a & b) << 1 is the carry. Repeat until there is no carry. JavaScript 32-bit ints make negatives work too.
function getSum(a, b) { while (b !== 0) { const carry = (a & b) << 1; a = a ^ b; b = carry; } return a;}