Parity pattern in detail: how to recognize and use it

Parity is a pattern in coding patterns where we need to determine whether a number is odd or even. We can do it via modulo operator (%) or using bits:

Modulo:

x % 2

x % 2 == 0  // even
x % 2 == 1  // odd

Bits:

x & 1

x & 1 == 0  // even
x & 1 == 1  // odd

Considering "-" before number, the universal checking is:

x % 2 == 0 
x % 2 != 0 

(x & 1) == 0
(x & 1) != 0 

The main idea is: instead of using different number values, we can narrow the problem down to just two states: odd or even. For example:

nums = [7, 12, 3, 8, 10]

parity: [1,  0, 1, 0,  0] or parity [odd, even, odd, even, even]

Rules of the Parity pattern

1. For addition and subtraction, the rules are the same:

even ± even = even
odd  ± odd  = even

even ± odd  = odd
odd  ± even = odd

Remember the rule:

parity(a + b) == parity(a - b)

parity(result) = parity(a) XOR parity(b)

Simple example:

7 - 3 = 4
odd XOR odd = even

7 - 2 = 5
odd XOR even = odd

2. For multiplication the rule is:

even * anything = even

odd * odd = odd

How to recognize the Parity pattern

And the most important part: how can you recognize the Parity pattern during a coding interview? There are several clues in the problem description that should make you think about using the Parity pattern:

1. odd / even
2. need to do all numbers odd or even
3. + or - operations
4. the answer may depend only on the quantity odd / even

LeetCode problems for the Sliding Window pattern

905. Sort Array By Parity
922. Sort Array By Parity II
3151. Special Array I
3152. Special Array II
3467. Transform Array by Parity
3875. Construct Uniform Parity Array I