Cancel bits, then move indices

Single number — XOR

Recognize it from — every value appears twice except one; find the unique. “All pairs plus one unique in a sorted array” can also be binary search on even/odd index — XOR is the linear fallback you name first.

What it actually does — XOR is commutative, associative, and x ^ x = 0, x ^ 0 = x. Pairing every duplicate with itself cancels those bits. Whatever remains is the unpaired number. You do not need extra memory and you do not sort.

int singleNumber(int[] a) {
    int x = 0;
    for (int v : a) x ^= v; // each duplicate cancels; the unique bits survive
    return x;
}

int singleNumber(int[] a) {
    if (a == null || a.length == 0) throw new IllegalArgumentException("empty");
    int x = 0;
    for (int v : a) x ^= v;
    return x; // if they said "appears 3 times except one," XOR is the wrong tool — counts or bit-mod-3
}

Example 1 — simple

[2, 2, 1].

Answer: 1.

Example 2 — every step

[4, 1, 2, 1, 2]. Running XOR, binary shown.

Answer: 4. The two 1s cancelled, the two 2s cancelled, 4 remained.

Count set bits — Kernighan n &= n-1

Recognize it from — Hamming weight, “how many 1-bits,” bit-check of a flag. Looping 32 times with (n >> i) & 1 is correct and slower to think about; Kernighan loops once per set bit.

What it actually does — in two’s complement, n - 1 flips everything from the lowest 1-bit through the trailing zeros. AND with n clears that lowest 1 and leaves the higher 1s. Repeat until n is 0. The iteration count is the popcount.

int bitCount(int n) {
    int c = 0;
    while (n != 0) {
        n &= n - 1; // drop the lowest set bit
        c++;
    }
    return c;
}
boolean testBit(int n, int k) {
    return (n & (1 << k)) != 0; // is bit k set? (k from the right, 0-based)
}

int hammingWeight(int n) {
    int c = 0;
    while (n != 0) {
        n &= n - 1;
        c++;
    }
    return c; // Integer.bitCount(n) exists; they often want the loop
}
boolean allPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0; // exactly one bit set
}

Example 1 — simple

n = 7 = 1112. Three set bits.

Answer: 3. Loop stops.

Example 2 — every step

n = 12 = 11002. Every unset of a 1-bit. Two set bits (not four — the trailing zeros are already 0).

Answer: 2. A 32-step shift loop would also return 2; it would iterate through the zeros too.

No extra named-IE card required for Kernighan. Do not invent a Job 10454435 bit prompt.

Rotate matrix 90° clockwise — transpose + reverse rows

Recognize it from — n×n matrix, rotate in place 90° clockwise. Anti-clockwise is transpose then reverse columns (ask). Spiral print is a different IO (walk layers). Search 2D is the next card.

What it actually does — the mapping is (i, j) → (j, n-1-i). Doing that with a temp matrix is the brute. In place: first swap across the diagonal (transpose), then reverse each row. Transpose sends (i,j) to (j,i); reversing the row sends (j,i) to (j, n-1-i).

void rotateCopy(int[][] m) {
    int n = m.length;
    int[][] t = new int[n][n];          // extra matrix — name this, then drop it
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            t[j][n - 1 - i] = m[i][j];  // the closed-form map
    for (int i = 0; i < n; i++)
        m[i] = t[i];
}

void rotate(int[][] m) {
    int n = m.length;
    for (int i = 0; i < n; i++) {                 // transpose: only j > i so you do not swap twice
        for (int j = i + 1; j < n; j++) {
            int t = m[i][j]; m[i][j] = m[j][i]; m[j][i] = t;
        }
    }
    for (int i = 0; i < n; i++) {                 // reverse each row
        for (int l = 0, r = n - 1; l < r; l++, r--) {
            int t = m[i][l]; m[i][l] = m[i][r]; m[i][r] = t;
        }
    }
}

Example 1 — simple

2×2: [[1, 2], [3, 4]] → [[3, 1], [4, 2]].

Answer: [[3, 1], [4, 2]].

Example 2 — every step

3×3. Every transpose swap, then every row reverse.

Answer: [[7, 4, 1], [8, 5, 2], [9, 6, 3]].

Search a 2D matrix — treat as a sorted array

Recognize it from — each row sorted, first of row i+1 greater than last of row i (one globally sorted sequence). Target present or not. Row-with-max-1s is a different walk (staircase from the top-right on a 0/1 row-sorted matrix). Search-II (columns also sorted, but not globally) is also a staircase, not this binary search.

What it actually does — flatten the index space in your head: cell k is m[k / cols][k % cols]. Binary search lo..hi on [0, rows*cols - 1]. Mid maps to a row and column; compare that value to the target with Integer.compare. You never allocate a 1D copy.

boolean searchMatrix(int[][] m, int target) {
    int rows = m.length, cols = m[0].length;
    int lo = 0, hi = rows * cols - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // overflow-safe mid
        int r = mid / cols, c = mid % cols;
        int v = m[r][c];
        if (v == target) return true;
        if (v < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

boolean searchMatrix(int[][] m, int target) {
    if (m == null || m.length == 0 || m[0].length == 0) return false;
    int rows = m.length, cols = m[0].length;
    int lo = 0, hi = rows * cols - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int r = mid / cols, c = mid % cols;
        int cmp = Integer.compare(m[r][c], target);
        if (cmp == 0) return true;
        if (cmp < 0) lo = mid + 1;
        else hi = mid - 1;
    }
    return false; // missing target — Ex2
}

Example 1 — simple

2×2: [[1, 3], [5, 7]], target 3. Flattened: 1, 3, 5, 7. Indices 0..3.

Answer: true, at (0, 1).

Example 2 — every step

3×4, find a missing value 13. Every mid mapped to (r, c).

Answer: false. 13 sits between 11 and 16 in the flattened order; the search never hits a cell equal to 13.

See also on this topic

Longest increasing path in a matrix is DFS + memo (graph/DP), not a rotate. It sits in chapter 05 if you need the Java card. Sudoku is constraint sets on a 9×9, not search-as-array. Job 10454435 still none.