Facebook Pixel

782. Transform to Chessboard

HardBit ManipulationArrayMathMatrix
Leetcode Link

Problem Description

You have an n x n binary grid called board containing only 0s and 1s. Your goal is to transform this grid into a valid chessboard pattern through a series of moves.

In each move, you can:

  • Swap any two complete rows with each other, OR
  • Swap any two complete columns with each other

A chessboard board is defined as a grid where no two adjacent cells (horizontally or vertically adjacent) have the same value. In other words, 0s and 1s must alternate in all four directions, creating a checkerboard pattern like:

0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

or

1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1

The problem asks you to find the minimum number of moves needed to transform the given board into a valid chessboard. If it's impossible to achieve a chessboard pattern through any number of row and column swaps, return -1.

Key observations about valid chessboards:

  • There can only be two distinct row patterns in the entire board, and they must be complements of each other (if one row is "0101", the other must be "1010")
  • The same property applies to columns
  • For even-sized boards (n = 2k), each row and column must have exactly k ones and k zeros
  • For odd-sized boards (n = 2k+1), each row and column must have either k ones and k+1 zeros, or k+1 ones and k zeros
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that row and column swaps don't change the internal pattern of any row or column - they only change positions. This means if we can't form a chessboard with the existing row and column patterns, no amount of swapping will help.

Let's think about what makes a valid chessboard. In any valid chessboard, there are exactly two types of rows: one pattern and its complement. For example, if one row is "0101", then all other rows must be either "0101" or "1010". The same applies to columns.

Why is this true? Consider any valid chessboard - if we fix a row pattern, the row directly below it must have the opposite pattern (to ensure no vertical adjacencies of same values). The row below that must match the first row again, and so on. This creates an alternating pattern of just two row types.

Since swapping rows/columns only rearranges them without changing their content, we first need to verify that our board contains exactly two row patterns (and they're complements) and exactly two column patterns (also complements). If not, it's impossible to form a chessboard.

Once we know a chessboard is possible, the problem reduces to counting how many rows and columns are already in their correct positions. We can use bit manipulation to represent each row/column as a number, making comparisons efficient.

For the minimum swaps calculation:

  • If n is even, we have two valid target patterns: starting with 0 ("0101...") or starting with 1 ("1010..."). We calculate swaps needed for both and take the minimum.
  • If n is odd, there's only one valid pattern based on the count of 0s and 1s. The pattern with more positions must occupy the majority slots.

The beauty of this approach is recognizing that we can solve rows and columns independently - the minimum total swaps equals the sum of minimum row swaps and minimum column swaps. This works because row swaps don't affect column patterns and vice versa.

Learn more about Math patterns.

Solution Approach

The solution uses bit manipulation and state compression to efficiently represent and compare row/column patterns.

Step 1: Extract and Validate Patterns

First, we extract the pattern of the first row and first column as our reference patterns:

  • rowMask: represents the first row as a bitmask where bit i is set if board[0][i] == 1
  • colMask: represents the first column as a bitmask where bit i is set if board[i][0] == 1

We then calculate their complements:

  • revRowMask = mask ^ rowMask where mask = (1 << n) - 1 gives us all bits set
  • revColMask = mask ^ colMask

Step 2: Verify Board Validity

For each row and column in the board:

  • Convert it to a bitmask representation (curRowMask and curColMask)
  • Check if each row matches either rowMask or revRowMask
  • Check if each column matches either colMask or revColMask
  • If any row/column doesn't match one of the two patterns, return -1

While checking, we also count:

  • sameRow: number of rows matching rowMask
  • sameCol: number of columns matching colMask

Step 3: Calculate Minimum Swaps

The helper function f(mask, cnt) calculates the minimum swaps needed for a dimension (row or column):

For odd n:

  • Check if the count of 1s and the count of matching patterns are valid (difference of 1 from half)
  • Determine the target pattern based on which bit value appears more frequently
  • Use magic numbers 0xAAAAAAAA (binary: ...10101010) and 0x55555555 (binary: ...01010101) to count mismatched positions
  • If the pattern has n//2 ones, target should be "10101...", count mismatches with 0xAAAAAAAA
  • Otherwise, target should be "01010...", count mismatches with 0x55555555

For even n:

  • Verify exactly half the bits are 1s and exactly half the rows/columns match the pattern
  • Calculate swaps needed for both possible targets:
    • cnt0: swaps to achieve "10101..." pattern
    • cnt1: swaps to achieve "01010..." pattern
  • Return the minimum of the two

Step 4: Combine Results

The total minimum moves is the sum of:

  • t1: minimum swaps needed for rows
  • t2: minimum swaps needed for columns

If either dimension is impossible to arrange (t1 == -1 or t2 == -1), return -1.

The key optimization is using bit manipulation for pattern matching and counting, which reduces the complexity from checking each element to simple bitwise operations. The magic numbers 0xAAAAAAAA and 0x55555555 act as masks for alternating bit patterns, allowing us to count positions that need swapping with a single bit_count() operation.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with a 4×4 board:

Input board:
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

Step 1: Extract Reference Patterns

First row: [0, 1, 1, 0] → rowMask = 0110 (binary) = 6 First column: [0, 1, 1, 0] → colMask = 0110 (binary) = 6

Calculate complements (with mask = 1111 = 15):

  • revRowMask = 15 ^ 6 = 1001 (binary) = 9 → pattern [1, 0, 0, 1]
  • revColMask = 15 ^ 6 = 1001 (binary) = 9 → pattern [1, 0, 0, 1]

Step 2: Validate Board Patterns

Check each row:

  • Row 0: [0, 1, 1, 0] = 6 ✓ matches rowMask
  • Row 1: [1, 0, 0, 1] = 9 ✓ matches revRowMask
  • Row 2: [1, 0, 0, 1] = 9 ✓ matches revRowMask
  • Row 3: [0, 1, 1, 0] = 6 ✓ matches rowMask

Count: sameRow = 2 (rows matching rowMask)

Check each column:

  • Col 0: [0, 1, 1, 0] = 6 ✓ matches colMask
  • Col 1: [1, 0, 0, 1] = 9 ✓ matches revColMask
  • Col 2: [1, 0, 0, 1] = 9 ✓ matches revColMask
  • Col 3: [0, 1, 0, 1] = 6 ✓ matches colMask

Count: sameCol = 2 (columns matching colMask)

Step 3: Calculate Minimum Swaps

For rows (n = 4 is even):

  • rowMask = 0110 has 2 ones ✓ (exactly n/2)
  • sameRow = 2 ✓ (exactly n/2)
  • Target pattern 1: 1010 (0xAAAA masked to 4 bits)
    • XOR: 0110 ^ 1010 = 1100 → 2 bits different → need 1 swap
  • Target pattern 2: 0101 (0x5555 masked to 4 bits)
    • XOR: 0110 ^ 0101 = 0011 → 2 bits different → need 1 swap
  • Minimum row swaps = min(1, 1) = 1

For columns (same calculation):

  • colMask = 0110 has 2 ones ✓
  • sameCol = 2 ✓
  • Both target patterns give 1 swap needed
  • Minimum column swaps = 1

Step 4: Final Result

Total minimum moves = 1 (rows) + 1 (columns) = 2

After 2 swaps, we can achieve:

Final board (one possible arrangement):
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

This example shows how:

  1. We validate that only two complementary patterns exist
  2. We use bit manipulation to efficiently compare patterns
  3. We calculate swaps independently for rows and columns
  4. The magic numbers help us quickly count mismatched positions

Solution Implementation

1class Solution:
2    def movesToChessboard(self, board: List[List[int]]) -> int:
3        def calculate_min_swaps(pattern_mask: int, same_count: int) -> int:
4            """
5            Calculate minimum swaps needed to form alternating pattern.
6          
7            Args:
8                pattern_mask: Bit representation of the row/column pattern
9                same_count: Count of rows/columns matching the first row/column
10          
11            Returns:
12                Minimum swaps needed, or -1 if impossible
13            """
14            ones_count = pattern_mask.bit_count()
15          
16            if n & 1:  # Odd board size
17                # For odd n, difference between 0s and 1s must be exactly 1
18                if abs(n - 2 * ones_count) != 1 or abs(n - 2 * same_count) != 1:
19                    return -1
20              
21                # Check which pattern to use based on ones count
22                if ones_count == n // 2:
23                    # Pattern starts with 0 (0xAAAA... represents 1010...)
24                    return n // 2 - (pattern_mask & 0xAAAAAAAA).bit_count()
25                else:
26                    # Pattern starts with 1 (0x5555... represents 0101...)
27                    return (n + 1) // 2 - (pattern_mask & 0x55555555).bit_count()
28            else:  # Even board size
29                # For even n, must have equal 0s and 1s
30                if ones_count != n // 2 or same_count != n // 2:
31                    return -1
32              
33                # Try both patterns and choose minimum
34                swaps_pattern_0 = n // 2 - (pattern_mask & 0xAAAAAAAA).bit_count()
35                swaps_pattern_1 = n // 2 - (pattern_mask & 0x55555555).bit_count()
36                return min(swaps_pattern_0, swaps_pattern_1)
37      
38        n = len(board)
39        all_bits_mask = (1 << n) - 1  # Mask with all n bits set to 1
40      
41        # Create bit masks for first row and first column
42        first_row_mask = 0
43        first_col_mask = 0
44        for i in range(n):
45            first_row_mask |= board[0][i] << i
46            first_col_mask |= board[i][0] << i
47      
48        # Create inverted masks (complement patterns)
49        inverted_row_mask = all_bits_mask ^ first_row_mask
50        inverted_col_mask = all_bits_mask ^ first_col_mask
51      
52        # Count rows/columns matching the first row/column pattern
53        rows_matching_first = 0
54        cols_matching_first = 0
55      
56        # Validate board and count matching patterns
57        for i in range(n):
58            current_row_mask = 0
59            current_col_mask = 0
60          
61            # Build bit masks for current row and column
62            for j in range(n):
63                current_row_mask |= board[i][j] << j
64                current_col_mask |= board[j][i] << j
65          
66            # Each row/column must match either the first pattern or its inverse
67            if (current_row_mask not in (first_row_mask, inverted_row_mask) or 
68                current_col_mask not in (first_col_mask, inverted_col_mask)):
69                return -1
70          
71            # Count matches with first pattern
72            rows_matching_first += (current_row_mask == first_row_mask)
73            cols_matching_first += (current_col_mask == first_col_mask)
74      
75        # Calculate minimum swaps for rows and columns
76        row_swaps = calculate_min_swaps(first_row_mask, rows_matching_first)
77        col_swaps = calculate_min_swaps(first_col_mask, cols_matching_first)
78      
79        # Return total swaps or -1 if impossible
80        if row_swaps == -1 or col_swaps == -1:
81            return -1
82        return row_swaps + col_swaps
83
1class Solution {
2    private int boardSize;
3
4    public int movesToChessboard(int[][] board) {
5        boardSize = board.length;
6      
7        // Create a mask with all bits set to 1 for the board size
8        int fullMask = (1 << boardSize) - 1;
9      
10        // Build bit masks for the first row and first column
11        int firstRowMask = 0;
12        int firstColMask = 0;
13        for (int i = 0; i < boardSize; ++i) {
14            firstRowMask |= board[0][i] << i;  // Set bit i if board[0][i] is 1
15            firstColMask |= board[i][0] << i;  // Set bit i if board[i][0] is 1
16        }
17      
18        // Calculate reverse masks (flip all bits)
19        int reverseRowMask = fullMask ^ firstRowMask;
20        int reverseColMask = fullMask ^ firstColMask;
21      
22        // Count rows matching the first row pattern and columns matching the first column pattern
23        int rowsMatchingFirst = 0;
24        int colsMatchingFirst = 0;
25      
26        // Check each row and column
27        for (int i = 0; i < boardSize; ++i) {
28            int currentRowMask = 0;
29            int currentColMask = 0;
30          
31            // Build bit masks for current row and column
32            for (int j = 0; j < boardSize; ++j) {
33                currentRowMask |= board[i][j] << j;  // Build mask for row i
34                currentColMask |= board[j][i] << j;  // Build mask for column i
35            }
36          
37            // Each row must match either the first row or its reverse
38            if (currentRowMask != firstRowMask && currentRowMask != reverseRowMask) {
39                return -1;
40            }
41          
42            // Each column must match either the first column or its reverse
43            if (currentColMask != firstColMask && currentColMask != reverseColMask) {
44                return -1;
45            }
46          
47            // Count rows/columns matching the first pattern
48            rowsMatchingFirst += currentRowMask == firstRowMask ? 1 : 0;
49            colsMatchingFirst += currentColMask == firstColMask ? 1 : 0;
50        }
51      
52        // Calculate minimum moves for rows and columns
53        int rowMoves = calculateMinimumMoves(firstRowMask, rowsMatchingFirst);
54        int colMoves = calculateMinimumMoves(firstColMask, colsMatchingFirst);
55      
56        // Return -1 if either is impossible, otherwise return sum
57        return rowMoves == -1 || colMoves == -1 ? -1 : rowMoves + colMoves;
58    }
59
60    private int calculateMinimumMoves(int mask, int countMatchingFirst) {
61        int onesCount = Integer.bitCount(mask);
62      
63        if (boardSize % 2 == 1) {
64            // For odd board size, validate constraints
65            if (Math.abs(boardSize - onesCount * 2) != 1 || 
66                Math.abs(boardSize - countMatchingFirst * 2) != 1) {
67                return -1;
68            }
69          
70            // Choose pattern based on number of ones
71            if (onesCount == boardSize / 2) {
72                // Pattern should start with 0 (even positions should be 0)
73                // 0xAAAAAAAA has 1s at odd positions (1010...1010)
74                return boardSize / 2 - Integer.bitCount(mask & 0xAAAAAAAA);
75            }
76            // Pattern should start with 1 (odd positions should be 0)
77            // 0x55555555 has 1s at even positions (0101...0101)
78            return (boardSize / 2 + 1) - Integer.bitCount(mask & 0x55555555);
79        } else {
80            // For even board size, validate constraints
81            if (onesCount != boardSize / 2 || countMatchingFirst != boardSize / 2) {
82                return -1;
83            }
84          
85            // Calculate moves for both possible target patterns
86            // Pattern 1: 0101... (even positions are 0)
87            int movesPattern1 = boardSize / 2 - Integer.bitCount(mask & 0xAAAAAAAA);
88            // Pattern 2: 1010... (odd positions are 0)
89            int movesPattern2 = boardSize / 2 - Integer.bitCount(mask & 0x55555555);
90          
91            return Math.min(movesPattern1, movesPattern2);
92        }
93    }
94}
95
1class Solution {
2public:
3    int n; // board size
4  
5    int movesToChessboard(vector<vector<int>>& board) {
6        n = board.size();
7        int fullMask = (1 << n) - 1; // mask with all n bits set to 1
8      
9        // Create bitmasks for the first row and first column
10        int firstRowMask = 0, firstColMask = 0;
11        for (int i = 0; i < n; ++i) {
12            firstRowMask |= board[0][i] << i; // build mask from first row
13            firstColMask |= board[i][0] << i; // build mask from first column
14        }
15      
16        // Get the reverse patterns (flip all bits)
17        int reverseRowMask = fullMask ^ firstRowMask;
18        int reverseColMask = fullMask ^ firstColMask;
19      
20        // Count rows that match the first row pattern and columns that match the first column pattern
21        int rowsMatchingFirst = 0, colsMatchingFirst = 0;
22      
23        // Validate that all rows and columns follow one of two patterns
24        for (int i = 0; i < n; ++i) {
25            int currentRowMask = 0, currentColMask = 0;
26          
27            // Build masks for current row and column
28            for (int j = 0; j < n; ++j) {
29                currentRowMask |= board[i][j] << j; // build mask for row i
30                currentColMask |= board[j][i] << j; // build mask for column i
31            }
32          
33            // Each row must match either the first row or its reverse
34            if (currentRowMask != firstRowMask && currentRowMask != reverseRowMask) {
35                return -1;
36            }
37          
38            // Each column must match either the first column or its reverse
39            if (currentColMask != firstColMask && currentColMask != reverseColMask) {
40                return -1;
41            }
42          
43            // Count how many rows/columns match the first pattern
44            rowsMatchingFirst += (currentRowMask == firstRowMask);
45            colsMatchingFirst += (currentColMask == firstColMask);
46        }
47      
48        // Calculate minimum moves for rows and columns
49        int rowMoves = calculateMinimumMoves(firstRowMask, rowsMatchingFirst);
50        int colMoves = calculateMinimumMoves(firstColMask, colsMatchingFirst);
51      
52        // If either is impossible, return -1; otherwise return total moves
53        return (rowMoves == -1 || colMoves == -1) ? -1 : rowMoves + colMoves;
54    }
55  
56private:
57    int calculateMinimumMoves(int patternMask, int patternCount) {
58        int onesCount = __builtin_popcount(patternMask); // count number of 1s in the mask
59      
60        if (n & 1) { // odd board size
61            // For odd n, we need either (n+1)/2 ones or n/2 ones
62            // Also need either (n+1)/2 or n/2 rows/columns matching the pattern
63            if (abs(n - onesCount * 2) != 1 || abs(n - patternCount * 2) != 1) {
64                return -1;
65            }
66          
67            // Determine which checkerboard pattern to target based on ones count
68            if (onesCount == n / 2) {
69                // Target pattern starts with 0 (even positions should be 0)
70                // 0xAAAAAAAA has 1s in odd positions (1010...1010)
71                return n / 2 - __builtin_popcount(patternMask & 0xAAAAAAAA);
72            }
73            // Target pattern starts with 1 (odd positions should be 0)
74            // 0x55555555 has 1s in even positions (0101...0101)
75            return (n + 1) / 2 - __builtin_popcount(patternMask & 0x55555555);
76          
77        } else { // even board size
78            // For even n, must have exactly n/2 ones and n/2 matching rows/columns
79            if (onesCount != n / 2 || patternCount != n / 2) {
80                return -1;
81            }
82          
83            // Calculate moves for both possible target patterns
84            // Pattern 1: starts with 0 (0101...)
85            int movesPattern0 = n / 2 - __builtin_popcount(patternMask & 0xAAAAAAAA);
86            // Pattern 2: starts with 1 (1010...)
87            int movesPattern1 = n / 2 - __builtin_popcount(patternMask & 0x55555555);
88          
89            // Return minimum moves needed
90            return min(movesPattern0, movesPattern1);
91        }
92    }
93};
94
1let n: number; // board size
2
3function movesToChessboard(board: number[][]): number {
4    n = board.length;
5    const fullMask = (1 << n) - 1; // mask with all n bits set to 1
6  
7    // Create bitmasks for the first row and first column
8    let firstRowMask = 0;
9    let firstColMask = 0;
10    for (let i = 0; i < n; i++) {
11        firstRowMask |= board[0][i] << i; // build mask from first row
12        firstColMask |= board[i][0] << i; // build mask from first column
13    }
14  
15    // Get the reverse patterns (flip all bits)
16    const reverseRowMask = fullMask ^ firstRowMask;
17    const reverseColMask = fullMask ^ firstColMask;
18  
19    // Count rows that match the first row pattern and columns that match the first column pattern
20    let rowsMatchingFirst = 0;
21    let colsMatchingFirst = 0;
22  
23    // Validate that all rows and columns follow one of two patterns
24    for (let i = 0; i < n; i++) {
25        let currentRowMask = 0;
26        let currentColMask = 0;
27      
28        // Build masks for current row and column
29        for (let j = 0; j < n; j++) {
30            currentRowMask |= board[i][j] << j; // build mask for row i
31            currentColMask |= board[j][i] << j; // build mask for column i
32        }
33      
34        // Each row must match either the first row or its reverse
35        if (currentRowMask !== firstRowMask && currentRowMask !== reverseRowMask) {
36            return -1;
37        }
38      
39        // Each column must match either the first column or its reverse
40        if (currentColMask !== firstColMask && currentColMask !== reverseColMask) {
41            return -1;
42        }
43      
44        // Count how many rows/columns match the first pattern
45        rowsMatchingFirst += currentRowMask === firstRowMask ? 1 : 0;
46        colsMatchingFirst += currentColMask === firstColMask ? 1 : 0;
47    }
48  
49    // Calculate minimum moves for rows and columns
50    const rowMoves = calculateMinimumMoves(firstRowMask, rowsMatchingFirst);
51    const colMoves = calculateMinimumMoves(firstColMask, colsMatchingFirst);
52  
53    // If either is impossible, return -1; otherwise return total moves
54    return (rowMoves === -1 || colMoves === -1) ? -1 : rowMoves + colMoves;
55}
56
57function calculateMinimumMoves(patternMask: number, patternCount: number): number {
58    // Count number of 1s in the mask
59    const onesCount = countBits(patternMask);
60  
61    if (n & 1) { // odd board size
62        // For odd n, we need either (n+1)/2 ones or n/2 ones
63        // Also need either (n+1)/2 or n/2 rows/columns matching the pattern
64        if (Math.abs(n - onesCount * 2) !== 1 || Math.abs(n - patternCount * 2) !== 1) {
65            return -1;
66        }
67      
68        // Determine which checkerboard pattern to target based on ones count
69        if (onesCount === Math.floor(n / 2)) {
70            // Target pattern starts with 0 (even positions should be 0)
71            // 0xAAAAAAAA has 1s in odd positions (1010...1010)
72            return Math.floor(n / 2) - countBits(patternMask & 0xAAAAAAAA);
73        }
74        // Target pattern starts with 1 (odd positions should be 0)
75        // 0x55555555 has 1s in even positions (0101...0101)
76        return Math.floor((n + 1) / 2) - countBits(patternMask & 0x55555555);
77      
78    } else { // even board size
79        // For even n, must have exactly n/2 ones and n/2 matching rows/columns
80        if (onesCount !== n / 2 || patternCount !== n / 2) {
81            return -1;
82        }
83      
84        // Calculate moves for both possible target patterns
85        // Pattern 1: starts with 0 (0101...)
86        const movesPattern0 = n / 2 - countBits(patternMask & 0xAAAAAAAA);
87        // Pattern 2: starts with 1 (1010...)
88        const movesPattern1 = n / 2 - countBits(patternMask & 0x55555555);
89      
90        // Return minimum moves needed
91        return Math.min(movesPattern0, movesPattern1);
92    }
93}
94
95// Helper function to count number of set bits in a number
96function countBits(num: number): number {
97    let count = 0;
98    while (num) {
99        count += num & 1;
100        num >>>= 1; // unsigned right shift
101    }
102    return count;
103}
104

Time and Space Complexity

Time Complexity: O(n²)

The algorithm iterates through the board multiple times:

  • First loop (lines 20-23): Iterates through n elements to build rowMask and colMask - O(n)
  • Second loop (lines 26-37): Contains a nested loop where for each of n rows, we iterate through n columns to build curRowMask and curColMask - O(n²)
  • The helper function f() performs bit operations that take O(1) time since the bit count operations on a fixed-size integer are constant time
  • All other operations (XOR, comparisons, bit shifts) are O(1)

The dominant operation is the nested loop that processes the entire n×n board, resulting in O(n²) time complexity.

Space Complexity: O(1)

The algorithm uses only a fixed amount of extra space:

  • Integer variables: mask, rowMask, colMask, revRowMask, revColMask, sameRow, sameCol, curRowMask, curColMask - all store single integers regardless of input size
  • The helper function f() uses a few local integer variables (ones, cnt0, cnt1)
  • No additional data structures that scale with input size are created

Since the space usage doesn't grow with the input size n, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Understanding of Swap Counting

Pitfall: A common misconception is thinking that we need to count actual swap operations between misplaced rows/columns. For example, if row 0 should be at position 2 and row 2 should be at position 0, counting this as one swap.

Why it's wrong: The actual insight is that we only need to count how many rows/columns are in the wrong position relative to a target alternating pattern. Since we can swap any two rows/columns, the minimum number of swaps equals half the number of misplaced rows/columns (each swap fixes two positions).

Solution: Count the number of rows that should start with 0 but currently start with 1 (or vice versa). The number of swaps needed is exactly this count divided by 2.

2. Misunderstanding the Magic Numbers for Bit Patterns

Pitfall: Using 0xAAAAAAAA and 0x55555555 without considering the actual board size. These constants represent 32-bit patterns, but the board might be smaller.

Why it's wrong: For a board of size n < 32, we only care about the least significant n bits. The higher bits in these magic numbers don't affect the result due to the masking operation, but it's important to understand that:

  • 0xAAAAAAAA & pattern_mask effectively checks positions 1, 3, 5, 7... (odd positions)
  • 0x55555555 & pattern_mask effectively checks positions 0, 2, 4, 6... (even positions)

Solution: The code correctly handles this by only setting bits up to position n-1 in the pattern masks. The AND operation naturally limits the comparison to valid bit positions.

3. Confusion About Which Pattern to Target

Pitfall: Not understanding when to target pattern "0101..." vs "1010..." for odd-sized boards.

Why it's wrong: For odd n, one pattern will have more 1s than 0s. The board must match this constraint - if there are more 1s in the board, we must target the pattern with more 1s.

Solution:

if ones_count == n // 2:
    # We have fewer 1s, so pattern should be "01010..." (starts with 0)
    # Check positions that should be 1 (odd positions: 1, 3, 5...)
    return n // 2 - (pattern_mask & 0xAAAAAAAA).bit_count()
else:
    # We have more 1s, so pattern should be "10101..." (starts with 1)
    # Check positions that should be 1 (even positions: 0, 2, 4...)
    return (n + 1) // 2 - (pattern_mask & 0x55555555).bit_count()

4. Off-by-One Errors in Swap Calculation

Pitfall: Incorrectly calculating the number of swaps from the number of mismatched positions.

Why it's wrong: When we count positions that need to be 1 but are currently 0, we're identifying which rows need to be swapped. But remember: each swap fixes two positions simultaneously.

Solution: The formula target_ones - actual_ones_in_target_positions gives us the exact number of swaps needed. For example:

  • If we need 4 positions to be 1 (n//2 for even n)
  • And only 2 of those positions currently have 1
  • We need 4 - 2 = 2 swaps to fix this

5. Not Validating Board Feasibility Early

Pitfall: Attempting to calculate swaps without first verifying that the board can form a valid chessboard pattern.

Why it's wrong: A board might have the correct number of 0s and 1s but still be impossible to transform into a chessboard if the row/column patterns don't meet the requirements.

Solution: The code correctly validates that:

  1. There are exactly two distinct row patterns (and they're complements)
  2. There are exactly two distinct column patterns (and they're complements)
  3. The count of each pattern type is correct (n/2 for even n, or differs by 1 for odd n)

Only after these validations does it proceed to calculate swaps.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More