These are the notes for DSA episode 78. After laundry day every sock in the basket has its twin except one: find the lonely one using only your two hands (constant extra memory). We count every number against every other (correct, then Time Limit Exceeded on 1,000,001 numbers), see why a HashMap is not allowed either, and invent the XOR trick: pairs cancel, one pass, one variable. Then power of two, where Math.log says 2²⁹ is not a power of two, fixed by n & (n - 1); and counting bits, from 32 checks per number to Kernighan's loop to the DP ans[i] = ans[i >> 1] + (i & 1). Three real bugs close it. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problem, in real life
| Laundry day | In code |
|---|---|
| The basket of socks | the array a |
| Every sock has a twin | every number appears twice |
| The lonely sock | the number that appears once |
| Only two hands, no table | O(1) extra memory |
| Pick up a sock that matches one in your hand: both go away | x ^= v: a pair cancels |
Chapati folding (power of two): every fold doubles the layers: 1, 2, 4, 8, 16. Six layers is impossible by folding alone.
Every word, from zero
- Bit: a single 0 or 1. An
intin Java has 32 bits; bitbis worth2^b.4 = 100,1 = 001,2 = 010. - Binary: writing a number in base 2, with bits.
- Set bit: a bit that is 1. Lowest set bit: the rightmost 1 (
12 = 1100: the bit worth 4). ^(XOR, exclusive or): bit by bit, 1 if the two bits differ.0^0 = 0, 0^1 = 1, 1^0 = 1, 1^1 = 0.&(AND): 1 only if both bits are 1.x & 1is the last bit (1 if odd).|(OR): 1 if either bit is 1. It turns bits on and never turns them off.>>(shift right): slide the bits right;i >> 1drops the last bit (22 → 11). For non-negativeiit isi / 2.<<(shift left): slide the bits left;1 << bhas only bitbset.- Two's complement: how Java stores negative ints;
-1is all 32 bits set,Integer.MIN_VALUEis only the top bit. - Constant extra memory, O(1): a fixed number of variables, no matter how big the input.
- Power of two:
1, 2, 4, 8, ...=2^p; in binary exactly one set bit. - Kernighan's method: count set bits with
x &= x - 1untilx == 0; one loop per set bit. - Hamming weight / popcount: the number of set bits. Hamming distance: the number of bits where two numbers differ (
bitCount(x ^ y)). - Floating point (
double): an approximate number;Math.logresults are rounded. - Operator precedence: which operator binds first. In Java
+and-bind tighter than==, which binds tighter than&,^,|.
Problem statements
1. Single Number (LeetCode 136). Every element of a appears twice except one. Return it in O(n) time and O(1) extra memory.
2. Power of Two (LeetCode 231). Return true if n == 2^p for some p ≥ 0.
3. Counting Bits (LeetCode 338). Return ans[0..n] where ans[i] is the number of 1 bits in i.
| Input | Answer |
|---|---|
{2, 2, 1} |
1 |
{4, 1, 2, 1, 2} |
4 |
{7} (edge: one number) |
7 |
{-3, 5, -3} (edge: negatives) |
5 |
isPow2(536870912) |
true (2²⁹) |
isPow2(0), isPow2(-8) |
false |
countBits(5) |
[0, 1, 1, 2, 1, 2] |
Single number, the obvious way: count every number
import java.util.*;
public class Main {
static int single(int[] a) {
for (int i = 0; i < a.length; i++) {
int count = 0;
for (int j = 0; j < a.length; j++)
if (a[j] == a[i]) count++;
if (count == 1) return a[i];
}
return -1;
}
public static void main(String[] args) {
System.out.println(single(new int[]{2, 2, 1}));
System.out.println(single(new int[]{4, 1, 2, 1, 2}));
System.out.println(single(new int[]{7}));
System.out.println(single(new int[]{-3, 5, -3}));
}
}
1
4
7
5
Correct on the examples and edge cases. Now 500,000 pairs and one lonely number at the end:
import java.util.*;
public class Main {
static int single(int[] a) {
for (int i = 0; i < a.length; i++) {
int count = 0;
for (int j = 0; j < a.length; j++)
if (a[j] == a[i]) count++;
if (count == 1) return a[i];
}
return -1;
}
public static void main(String[] args) {
int k = 500000, n = 2 * k + 1;
int[] big = new int[n];
for (int i = 0; i < k; i++) big[2 * i] = big[2 * i + 1] = i + 1;
big[n - 1] = 999999;
long t0 = System.nanoTime();
int x = single(big);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(n + " numbers: " + x + ", " + ms + " ms");
}
}
Time Limit Exceeded
Why is it slow?
Every one of the n numbers scans all n numbers: about 10⁶ × 10⁶ = 10¹² comparisons. A HashMap<Integer, Integer> of counts is O(n) time, but it stores up to 500,000 entries: O(n) extra memory, which the problem forbids. We want a running total where a pair cancels itself.
The key insight: XOR cancels pairs
| Rule | Why |
|---|---|
a ^ a = 0 |
every bit matches itself |
a ^ 0 = a |
XOR with 0 changes nothing |
a ^ b = b ^ a, (a ^ b) ^ c = a ^ (b ^ c) |
order and grouping don't matter |
So x = a[0] ^ a[1] ^ ... ^ a[n-1]: the twins cancel wherever they are, and only the lonely number is left.
By hand: 4, 1, 2, 1, 2
| Step | x in binary | x |
|---|---|---|
start, ^ 4 |
100 | 4 |
^ 1 |
101 | 5 |
^ 2 |
111 | 7 |
^ 1 (the 1s cancel) |
110 | 6 |
^ 2 (the 2s cancel) |
100 | 4 |
Single number in Java
import java.util.*;
public class Main {
static int single(int[] a) {
int x = 0;
for (int v : a) x ^= v;
return x;
}
public static void main(String[] args) {
System.out.println(single(new int[]{2, 2, 1}));
System.out.println(single(new int[]{4, 1, 2, 1, 2}));
System.out.println(single(new int[]{7}));
System.out.println(single(new int[]{-3, 5, -3}));
}
}
1
4
7
5
The million-and-one numbers that timed out:
1000001 numbers: 999999, 7 ms
The same solutions in C++
#include <bits/stdc++.h>
using namespace std;
// Single number: XOR cancels every pair.
int singleNumber(const vector<int>& a) {
int x = 0;
for (int v : a) x ^= v;
return x;
}
// Power of two: exactly one set bit.
bool isPow2(int n) { return n > 0 && (n & (n - 1)) == 0; }
// Kernighan: one loop per set bit.
int ones(unsigned x) { int c = 0; while (x) { x &= x - 1; c++; } return c; }
// Counting bits: reuse the answer for i >> 1.
vector<int> countBits(int n) {
vector<int> ans(n + 1, 0);
for (int i = 1; i <= n; i++) ans[i] = ans[i >> 1] + (i & 1);
return ans;
}
int main() {
cout << singleNumber({2, 2, 1}) << " " << singleNumber({4, 1, 2, 1, 2}) << " "
<< singleNumber({7}) << " " << singleNumber({-3, 5, -3}) << "\n";
for (int n : {1, 16, 6, 1024, 536870912, 0, -8}) cout << n << " " << boolalpha << isPow2(n) << "\n";
cout << ones(12) << " " << ones(7) << " " << ones(1024) << " " << ones((unsigned)-1) << " " << __builtin_popcount(12) << "\n";
for (int v : countBits(5)) cout << v << " ";
cout << "\n";
}
1 4 7 5
1 true
16 true
6 false
1024 true
536870912 true
0 false
-8 false
2 3 1 32 2
0 1 1 2 1 2
The same solutions in Python
from functools import reduce
from operator import xor
def single_number(a):
"""Every number twice except one: XOR cancels the pairs."""
x = 0
for v in a:
x ^= v
return x
def is_pow2(n):
"""A power of two has exactly one set bit."""
return n > 0 and (n & (n - 1)) == 0
def ones(x):
"""Kernighan: x & (x - 1) clears the lowest set bit (x >= 0)."""
c = 0
while x:
x &= x - 1
c += 1
return c
def count_bits(n):
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i >> 1] + (i & 1)
return ans
print(single_number([2, 2, 1]), single_number([4, 1, 2, 1, 2]), single_number([7]), single_number([-3, 5, -3]))
print(reduce(xor, [4, 1, 2, 1, 2]))
for n in [1, 16, 6, 1024, 536870912, 0, -8]:
print(n, is_pow2(n))
print(ones(12), ones(7), ones(1024), bin(12).count("1"))
print(count_bits(5))
1 4 7 5
4
1 True
16 True
6 False
1024 True
536870912 True
0 False
-8 False
2 3 1 2
[0, 1, 1, 2, 1, 2]
Python ints have no fixed width, so the Kernighan loop in Python is only for x ≥ 0 (for a negative number it would never reach 0); use bin(x).count("1") or x.bit_count() (Python 3.10+) instead.
Power of two
The obvious way: logarithms
import java.util.*;
public class Main {
static boolean isPow2(int n) {
if (n <= 0) return false;
double p = Math.log(n) / Math.log(2);
return p == Math.floor(p);
}
public static void main(String[] args) {
for (int n : new int[]{1, 16, 6, 1024, 536870912})
System.out.println(n + " " + isPow2(n));
System.out.println(Math.log(536870912) / Math.log(2));
}
}
1 true
16 true
6 false
1024 true
536870912 false
29.000000000000004
536870912 = 2²⁹, and it says false. Math.log works with rounded double values, so log(2²⁹) / log(2) comes out as 29.000000000000004, not 29. Never use floating point for an exact question about integers.
The insight: n & (n − 1) clears the lowest set bit
| Binary | Value | |
|---|---|---|
n |
1100 | 12 |
n - 1 |
1011 | 11 (the lowest 1 becomes 0, the zeros below become 1) |
n & (n - 1) |
1000 | 8 (only the lowest set bit is gone) |
16 |
10000 | one set bit |
16 & 15 |
00000 | 0: nothing left, so 16 is a power of two |
Subtracting 1 works like an odometer rolling back from 1200 to 1199: the last non-zero digit goes down, every zero after it becomes the largest digit (in binary, 1).
import java.util.*;
public class Main {
static boolean isPow2(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
public static void main(String[] args) {
for (int n : new int[]{1, 16, 6, 1024, 536870912, 0, -8})
System.out.println(n + " " + isPow2(n));
}
}
1 true
16 true
6 false
1024 true
536870912 true
0 false
-8 false
Counting bits
The obvious way: 32 checks per number
import java.util.*;
public class Main {
static int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 0; i <= n; i++)
for (int b = 0; b < 32; b++)
if (((i >> b) & 1) == 1) ans[i]++;
return ans;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(countBits(2)));
System.out.println(Arrays.toString(countBits(5)));
System.out.println(Arrays.toString(countBits(0)));
}
}
[0, 1, 1]
[0, 1, 1, 2, 1, 2]
[0]
Kernighan's method: one loop per set bit
import java.util.*;
public class Main {
static int ones(int x) {
int c = 0;
while (x != 0) {
x &= x - 1;
c++;
}
return c;
}
public static void main(String[] args) {
System.out.println(ones(12));
System.out.println(ones(7));
System.out.println(ones(1024));
System.out.println(ones(-1));
}
}
2
3
1
32
-1 is all 32 bits set in two's complement, so it needs 32 loops; 1024 needs only 1.
The DP: reuse the smaller answer
i >> 1 is i without its last bit, a smaller number whose count is already in the table; the dropped bit is i & 1.
| i | binary | i >> 1 | i & 1 | ans[i] |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 + 1 = 1 |
| 2 | 10 | 1 | 0 | 1 + 0 = 1 |
| 3 | 11 | 1 | 1 | 1 + 1 = 2 |
| 4 | 100 | 2 | 0 | 1 + 0 = 1 |
| 5 | 101 | 2 | 1 | 1 + 1 = 2 |
| 22 | 10110 | 11 | 0 | ans[11] = 3 |
import java.util.*;
public class Main {
static int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 1; i <= n; i++)
ans[i] = ans[i >> 1] + (i & 1);
return ans;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(countBits(2)));
System.out.println(Arrays.toString(countBits(5)));
System.out.println(Arrays.toString(countBits(0)));
}
}
[0, 1, 1]
[0, 1, 1, 2, 1, 2]
[0]
A race on 50 million numbers:
import java.util.*;
public class Main {
static int[] slow(int n) {
int[] ans = new int[n + 1];
for (int i = 0; i <= n; i++)
for (int b = 0; b < 32; b++)
if (((i >> b) & 1) == 1) ans[i]++;
return ans;
}
static int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 1; i <= n; i++)
ans[i] = ans[i >> 1] + (i & 1);
return ans;
}
public static void main(String[] args) {
int n = 50000000;
long t0 = System.nanoTime();
int[] a = slow(n);
long t1 = System.nanoTime();
int[] b = countBits(n);
long t2 = System.nanoTime();
System.out.println("32 checks: " + (t1 - t0) / 1000000 + " ms");
System.out.println("dp: " + (t2 - t1) / 1000000 + " ms");
System.out.println("same? " + Arrays.equals(a, b));
}
}
32 checks: 3348 ms
dp: 177 ms
same? true
Three real bugs
Bug 1: |= instead of ^=. OR never turns a bit off, so pairs can't cancel.
import java.util.*;
public class Main {
static int single(int[] a) {
int x = 0;
for (int v : a) x |= v;
return x;
}
public static void main(String[] args) {
System.out.println(single(new int[]{2, 2, 1}));
System.out.println(single(new int[]{4, 1, 2, 1, 2}));
}
}
3
7
Bug 2: forgetting n > 0. 0 & -1 = 0, and Integer.MIN_VALUE - 1 overflows to Integer.MAX_VALUE, which shares no bits with it.
import java.util.*;
public class Main {
static boolean isPow2(int n) {
return (n & (n - 1)) == 0;
}
public static void main(String[] args) {
System.out.println(isPow2(16));
System.out.println(isPow2(0));
System.out.println(isPow2(Integer.MIN_VALUE));
}
}
true
true
true
Bug 3: no brackets around i & 1. + binds tighter than &, so Java computes (ans[i >> 1] + i) & 1. No error, just wrong counts.
import java.util.*;
public class Main {
static int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 1; i <= n; i++)
ans[i] = ans[i >> 1] + i & 1;
return ans;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(countBits(5)));
}
}
[0, 1, 1, 0, 1, 0]
Complexity
| Problem | Obvious way | Time / space | Bit trick | Time / space |
|---|---|---|---|---|
| Single number | count each number | O(n²) / O(1): Time Limit Exceeded | XOR everything | O(n) / O(1) |
| Single number | HashMap of counts | O(n) / O(n) | ||
| Power of two | Math.log |
O(1), wrong for 2²⁹ | n > 0 && (n & (n - 1)) == 0 |
O(1) / O(1) |
| Counting bits | 32 checks per number | O(32·n) | ans[i >> 1] + (i & 1) |
O(n) / O(n) for the output |
| One number's bits | 32 checks | O(32) | Kernighan | O(number of set bits) |
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Count each number | Time Limit Exceeded | n × n comparisons | XOR everything once |
x \|= v |
3 and 7 instead of 1 and 4 |
OR never clears a bit | x ^= v |
Math.log(n) / Math.log(2) |
536870912 false |
29.000000000000004 |
n > 0 && (n & (n - 1)) == 0 |
No n > 0 |
isPow2(0) and isPow2(Integer.MIN_VALUE) are true |
0 has no set bits; MIN_VALUE − 1 overflows | check n > 0 first |
ans[i >> 1] + i & 1 |
[0, 1, 1, 0, 1, 0] |
+ binds tighter than & |
ans[i >> 1] + (i & 1) |
n & n - 1 == 0 |
error: bad operand types for binary operator '&' |
== binds tighter than & |
(n & (n - 1)) == 0 |
>> on a negative number in a loop while (x != 0) x >>= 1 |
never ends (-1 >> 1 == -1) |
>> copies the sign bit |
use >>> or Kernighan |
Mini project: two lonely socks
Now two socks have lost their twins (LeetCode 260). XOR everything: you get p ^ q, not zero because p != q. Its lowest set bit x & -x is a bit where p and q differ. Split all numbers by that bit and XOR each group: each group holds one lonely sock and complete pairs.
import java.util.*;
public class Sock {
// Mini project: two lonely socks. Every number twice except TWO (LeetCode 260).
static int[] twoSingles(int[] a) {
int x = 0;
for (int v : a) x ^= v; // x = p ^ q, not zero because p != q
int low = x & -x; // the lowest bit where p and q differ
int p = 0;
for (int v : a) if ((v & low) != 0) p ^= v; // split into two groups
return new int[]{p, x ^ p};
}
public static void main(String[] args) {
System.out.println(Arrays.toString(twoSingles(new int[]{1, 2, 1, 3, 2, 5})));
System.out.println(Arrays.toString(twoSingles(new int[]{-1, 0})));
}
}
[3, 5]
[-1, 0]
Practice
1. Missing Number (LeetCode 268). 0..n with one number missing. XOR every index and every value.
2. Number of 1 Bits (LeetCode 191). Kernighan.
3. Power of Four (LeetCode 342). A power of two whose one set bit is at an even position: n & 0x55555555.
4. Single Number II (LeetCode 137). Every number three times except one: count each bit mod 3.
5. Hamming Distance (LeetCode 461). The differing bits are the 1s of x ^ y.
Solutions
public class Main {
// Missing Number (LeetCode 268): XOR every index 0..n and every value; the pairs cancel.
static int missingNumber(int[] a) {
int x = a.length;
for (int i = 0; i < a.length; i++) x ^= i ^ a[i];
return x;
}
// Number of 1 Bits (LeetCode 191): Kernighan.
static int hammingWeight(int n) {
int c = 0;
while (n != 0) { n &= n - 1; c++; }
return c;
}
// Power of Four (LeetCode 342): one set bit, at an even position.
static boolean isPowerOfFour(int n) {
return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}
// Single Number II (LeetCode 137): every number three times except one. Count each bit mod 3.
static int singleNumberII(int[] a) {
int ans = 0;
for (int b = 0; b < 32; b++) {
int sum = 0;
for (int v : a) sum += (v >> b) & 1;
if (sum % 3 != 0) ans |= 1 << b;
}
return ans;
}
// Hamming distance (LeetCode 461): the differing bits are the 1s of x ^ y.
static int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); }
public static void main(String[] args) {
System.out.println(missingNumber(new int[]{3, 0, 1}));
System.out.println(missingNumber(new int[]{9, 6, 4, 2, 3, 5, 7, 0, 1}));
System.out.println(hammingWeight(11) + " " + hammingWeight(-3));
System.out.println(isPowerOfFour(16) + " " + isPowerOfFour(8) + " " + isPowerOfFour(1));
System.out.println(singleNumberII(new int[]{2, 2, 3, 2}) + " " + singleNumberII(new int[]{0, 1, 0, 1, 0, 1, -99}));
System.out.println(hammingDistance(1, 4));
}
}
2
8
3 31
true false true
3 -99
2
Quick quiz
int x = 6 ^ 3 ^ 6;
System.out.println(x);
A) 0 B) 3 C) 5 D) 6
Answer
B) 3. Order doesn't matter: 6 ^ 6 = 0, and 0 ^ 3 = 3.
Interview questions
- Why does XOR find the single number?
a ^ a = 0,a ^ 0 = a, and XOR is commutative and associative, so all pairs cancel. - Does it work with negative numbers? Yes: XOR works on the 32 bits, whatever they mean.
- What does
n & (n - 1)do? Clears the lowest set bit. - Why is
n > 0needed in the power-of-two check? 0 has no set bits andInteger.MIN_VALUEhas one, but neither is a power of two. - Why not
Math.log? Doubles are rounded:log(2²⁹)/log(2) = 29.000000000000004. - What is
x & -x? The lowest set bit on its own (two's complement:-x = ~x + 1). - How do you count bits for 0..n in O(n)?
ans[i] = ans[i >> 1] + (i & 1)(orans[i & (i - 1)] + 1). >>vs>>>?>>copies the sign bit (arithmetic shift);>>>fills with 0 (logical shift).
Glossary
| Term | Meaning |
|---|---|
| Bit | A single 0 or 1; bit b is worth 2^b |
| Set bit | A bit equal to 1 |
| Lowest set bit | The rightmost 1; x & -x |
XOR (^) |
1 where the bits differ; a ^ a = 0 |
AND (&) |
1 where both bits are 1 |
OR (\|) |
1 where either bit is 1 |
>> / << |
Shift bits right / left |
>>> |
Shift right, filling with zeros |
| Two's complement | Java's way of storing negative ints; -1 = all bits set |
| Power of two | 2^p; exactly one set bit |
n & (n - 1) |
n with its lowest set bit cleared |
| Kernighan's method | Count set bits by clearing the lowest one until 0 |
| Popcount / Hamming weight | Number of set bits (Integer.bitCount) |
| Hamming distance | Number of differing bits: bitCount(x ^ y) |
| O(1) extra memory | A fixed number of variables |
| Operator precedence | Which operator binds first; + before == before & |
Summary
- Single number: XOR everything; pairs cancel. O(n) time, O(1) memory.
- Power of two:
n > 0 && (n & (n - 1)) == 0, neverMath.log. n & (n - 1)clears the lowest set bit: power checks and Kernighan's bit count.- Counting bits:
ans[i] = ans[i >> 1] + (i & 1), one step per number. - Bit operators bind loosely: always bracket them.
- Next episode: math for coding: GCD, the sieve of Eratosthenes, fast power and modular arithmetic.