Skip to content

06. Bit Manipulation#

Theory#

Description#

Bit manipulation refers to using bitwise operators to work directly with the binary representations of numbers. These operations allow you to solve problems efficiently, often with a time complexity advantage compared to other methods. In many cases, bit manipulation can help reduce both time and space complexity, especially when working with binary data.

Common Bitwise Operators#

  1. AND (&): Sets a bit to 1 if both corresponding bits are 1.

    • Example: 1101 & 1011 = 1001 (binary)

  2. OR (|): Sets a bit to 1 if at least one of the corresponding bits is 1.

    • Example: 1101 | 1011 = 1111

  3. XOR (^): Sets a bit to 1 if the corresponding bits are different.

    • Example: 1101 ^ 1011 = 0110

  4. NOT (~): Flips all bits (inverts 0s to 1s and 1s to 0s).

    • Example: ~1101 = 0010 (assuming 4-bit representation)

  5. Left Shift (<<): Shifts bits to the left, equivalent to multiplying the number by 2.

    • Example: 1010 << 1 = 10100 (multiplies by 2)

  6. Right Shift (>>): Shifts bits to the right, equivalent to dividing the number by 2 (ignoring the remainder).

    • Example: 1010 >> 1 = 0101 (divides by 2)

Key Bit Manipulation Patterns#

  1. Check if a number is even or odd:

    • Use n & 1. If the result is 0, the number is even; if the result is 1, the number is odd.
    • Example:
      n = 5 → 5 & 1 = 1 → Odd
      n = 6 → 6 & 1 = 0 → Even

  2. Get the rightmost set bit:

    • To isolate the rightmost set bit (1) in a number, use n & (-n).
    • Example:
      n = 12 (binary 1100) → n & (-n) = 4 (binary 0100)

  3. Set the k-th bit:

    • To set (turn to 1) the k-th bit(0-indexing, right to left) of a number n, use n | (1 << k).
    • Example:
      n = 4 (binary 0100), set the 3rd bit: 4 | (1 << 3) = 4 | 8 = 12 (binary 1100)

  4. Clear the k-th bit:

    • To clear (turn to 0) the k-th bit, use n & ~(1 << k).
    • Example:
      n = 6 (binary 0110), clear the 2nd bit: 6 & ~(1 << 2) = 6 & ~4 = 6 & 11 = 2 (binary 0010)

  5. Toggle the k-th bit:

    • To flip (toggle) the k-th bit, use n ^ (1 << k). This changes a 1 to 0, or a 0 to 1.
    • Example:
      n = 6 (binary 0110), toggle the 2nd bit: 6 ^ (1 << 2) = 6 ^ 4 = 2 (binary 0010)

  6. Check if the k-th bit is set:

    • To check if the k-th bit is 1, use (n & (1 << k)) != 0. If the result is non-zero, the k-th bit is set.
    • Example:
      n = 6 (binary 0110), check if the 2nd bit is set: (6 & (1 << 2)) != 0 → True

  7. Count the number of set bits (Hamming Weight):

    • To count the number of set bits (1s) in a number, use the technique n = n & (n - 1) repeatedly. This removes the rightmost set bit in each step. Count how many times you can do this until n becomes 0.
    • Example:
      n = 13 (binary 1101):
      First step: n = 13 & 12 = 1101 & 1100 = 1100
      Second step: n = 12 & 11 = 1100 & 1011 = 1000
      Third step: n = 8 & 7 = 1000 & 0111 = 0000
      Total steps: 3 set bits.

  8. Power of 2 Check:

    • A number n is a power of 2 if it has exactly one set bit. Check if n & (n - 1) == 0 (and n > 0 to exclude 0).
    • Example:
      n = 8 (binary 1000), check if it's a power of 2:
      8 & (8 - 1) = 8 & 7 = 0 → True (8 is a power of 2).

Intuitive Applications of Bit Manipulation#

  1. Subset Generation:

    • each subset of a set can be represented as a binary number. For a set with n elements, there are \(2^n\) subsets, and each subset corresponds to a number between 0 and \(2^n - 1\).

    • Masking: Each number (mask) from 0 to \(2^n - 1\) is used to generate a subset. The \( i^{th} \) bit in the number indicates whether the i-th element is in the subset (1 for included, 0 for excluded). 

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
      def generate_subsets(nums):
n = len(nums)
subsets = []
for mask in range(1 << n):  # Loop over all subsets
    subset = [nums[i] for i in range(n) if mask & (1 << i)]  # Build subset
    subsets.append(subset)
return subsets

nums = [1, 2, 3]
subsets = generate_subsets(nums)

    • Example: For the set {1, 2, 3}, the subsets are:

      • 000 → {} (empty set)
      • 001 → {1}
      • 010 → {2}
      • 011 → {1,2}
      • 100 → {3}
      • 101 → {1, 3}
      • 110 → {2, 3}
      • 111 → {1, 2, 3}

  2. Efficient Swapping:

    • You can swap two numbers using XOR without needing a temporary variable: 
      1
2
3
          a = a ^ b
    b = a ^ b
    a = a ^ b
    • Example: If a = 5 and b = 3, the values of a and b will be swapped using this XOR trick.

Why Use Bit Manipulation?#

  1. Efficiency: Bitwise operations are generally faster because they directly manipulate individual bits, which is low-level and quick.
  2. Memory Optimization: You can use fewer resources (like using a bitmask instead of an array of booleans).
  3. Elegance: Many problems become simpler and cleaner when you think in terms of binary data and bitwise operations.

Problems at a glance#

LC Problem
136 1. Single Number ↗
260 2. Single Number III ↗
268 3. Missing Number ↗
191 4. Number of 1 Bits ↗
338 5. Counting Bits ↗
190 6. Reverse Bits ↗
231 7. Power of Two ↗
371 8. Sum of Two Integers ↗
477 9. Total Hamming Distance ↗
201 10. Bitwise AND of Numbers Range ↗
89 11. Gray Code ↗
1310 12. XOR Queries of a Subarray ↗
1542 13. Find Longest Awesome Substring ↗
3097 14. Shortest Subarray With OR at Least K II ↗
3171 15. Find Subarray With Bitwise OR Closest to K ↗
3022 16. Minimize OR of Remaining Elements Using Operations ↗
2939 17. Maximum Xor Product ↗

Problems#

1. Single Number (Leetcode:136)#

Problem Statement

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

1 <= nums.length <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
Each element appears twice except for one element which appears only once.

Code and Explanation 

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result
Explanation:
XOR cancels identical values: a ^ a = 0 and a ^ 0 = a. XOR-ing every element leaves only the unique number.

  1. Initialize result = 0.
  2. XOR each number into result.
  3. Pairs cancel out; the survivor is the single number.

Time: O(n) · Space: O(1)

1
2
3
4
5
6
7
8
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counts = {}
        for num in nums:
            counts[num] = counts.get(num, 0) + 1
        for num, count in counts.items():
            if count == 1:
                return num
Explanation:
Count occurrences with a hash map, then return the key with count 1. Correct and easy to read, but uses O(n) extra space unlike the XOR trick.

Time: O(n) · Space: O(n)

2. Single Number III (Leetcode:260)#

Problem Statement

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

Constraints:

2 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
Each integer in nums will appear twice, except for two integers which will appear once.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor_all = 0
        for num in nums:
            xor_all ^= num

        # Rightmost set bit separates the two unique numbers
        diff_bit = xor_all & (-xor_all)

        a = b = 0
        for num in nums:
            if num & diff_bit:
                a ^= num
            else:
                b ^= num
        return [a, b]
Explanation:
XOR all numbers to get xor_all = x ^ y (the two unique values). Any set bit in xor_all differs between x and y. Use diff_bit = xor_all & (-xor_all) to isolate one such bit, then partition the array and XOR each group separately.

  1. xor_all holds x ^ y.
  2. diff_bit splits numbers into two groups with different bits at that position.
  3. Each group's XOR yields one unique number.

Time: O(n) · Space: O(1)

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        counts = {}
        for num in nums:
            counts[num] = counts.get(num, 0) + 1
        return [num for num, c in counts.items() if c == 1]
Explanation:
Track frequencies in a hash map and collect keys that appear once. Straightforward, but requires O(n) extra space instead of the XOR partition trick.

Time: O(n) · Space: O(n)

3. Missing Number (Leetcode:268)#

Problem Statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]
Output: 2

Example 2:

Input: nums = [0,1]
Output: 2

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8

Constraints:

n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
All the numbers of nums are unique.

Code and Explanation 

1
2
3
4
5
6
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        result = len(nums)
        for i, num in enumerate(nums):
            result ^= i ^ num
        return result
Explanation:
XOR index i with nums[i] for all positions, then XOR with n. Complete pairs (i, nums[i]) cancel; the missing index/value survives in result.

  1. Start with result = n (the last index in [0..n]).
  2. XOR each index and value into result.
  3. The unmatched number is the missing one.

Time: O(n) · Space: O(1)

1
2
3
4
5
6
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        expected = n * (n + 1) // 2
        actual = sum(nums)
        return expected - actual
Explanation:
Sum all numbers from 0 to n using n*(n+1)/2, subtract the array sum. The difference is the missing number. Watch for integer overflow in languages with fixed-width integers (not an issue in Python).

Time: O(n) · Space: O(1)

4. Number of 1 Bits (Leetcode:191)#

Problem Statement

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

Example 1:

Input: n = 11
Output: 3
Explanation: The input binary string 1011 has a total of three set bits.

Example 2:

Input: n = 128
Output: 1

Example 3:

Input: n = 2147483645
Output: 30

Constraints:

0 <= n <= 2^31 - 1

Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1  # clears the rightmost set bit
            count += 1
        return count
Explanation:
n & (n - 1) removes the lowest set bit each iteration. Count how many removals until n becomes 0. Runs in O(number of set bits) time.

Time: O(k) where k = set bits · Space: O(1)

1
2
3
4
5
6
7
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        for _ in range(32):
            count += n & 1
            n >>= 1
        return count
Explanation:
Shift n right one bit at a time and add n & 1 to the count. Always checks all 32 bits regardless of how sparse the number is.

Time: O(32) · Space: O(1)

5. Counting Bits (Leetcode:338)#

Problem Statement

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1s in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]

Constraints:

0 <= n <= 10^5

Code and Explanation 

1
2
3
4
5
6
class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = dp[i >> 1] + (i & 1)
        return dp
Explanation:
For any i, dropping the last bit gives i >> 1. The set-bit count is that count plus whether the last bit is 1 (i & 1). Builds the answer bottom-up in one pass.

Time: O(n) · Space: O(n)

1
2
3
4
5
6
class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = dp[i & (i - 1)] + 1
        return dp
Explanation:
i & (i - 1) removes the lowest set bit from i. The result's popcount is one less than i's popcount. Same O(n) DP, different recurrence.

Time: O(n) · Space: O(n)

6. Reverse Bits (Leetcode:190)#

Problem Statement

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: n = 43261596
Output: 964176192

Example 2:

Input: n = 2147483644
Output: 1073741822

Constraints:

0 <= n <= 2^32 - 1

Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for _ in range(32):
            result = (result << 1) | (n & 1)
            n >>= 1
        return result
Explanation:
Read the lowest bit of n, append it to result, then shift n right. Repeat 32 times to reverse all bits.

  1. Extract n & 1, push into result.
  2. Shift result left and n right each step.
  3. After 32 iterations, bits are fully reversed.

Time: O(32) · Space: O(1)

1
2
3
4
5
6
7
8
class Solution:
    def reverseBits(self, n: int) -> int:
        n = ((n & 0x55555555) << 1) | ((n & 0xAAAAAAAA) >> 1)
        n = ((n & 0x33333333) << 2) | ((n & 0xCCCCCCCC) >> 2)
        n = ((n & 0x0F0F0F0F) << 4) | ((n & 0xF0F0F0F0) >> 4)
        n = ((n & 0x00FF00FF) << 8) | ((n & 0xFF00FF00) >> 8)
        n = ((n & 0x0000FFFF) << 16) | ((n & 0xFFFF0000) >> 16)
        return n
Explanation:
Reverse in stages: swap adjacent bits, then pairs, nibbles, bytes, and finally 16-bit halves. Each mask selects alternating groups to shift and merge. Classic O(1)-time bit-hack after fixed number of steps.

Time: O(1) · Space: O(1)

7. Power of Two (Leetcode:231)#

Problem Statement

Given an integer n, return true if it is a power of two. Otherwise, return false.

Example 1:

Input: n = 1
Output: true

Example 2:

Input: n = 16
Output: true

Example 3:

Input: n = 3
Output: false

Constraints:

-2^31 <= n <= 2^31 - 1

Follow up: Could you solve it without loops/recursion?

Code and Explanation 

1
2
3
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0
Explanation:
Powers of two have exactly one set bit. n & (n - 1) clears that bit; the result is 0 only when there was a single bit. Must also require n > 0 since 0 fails.

Time: O(1) · Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        count = 0
        while n:
            n &= n - 1
            count += 1
            if count > 1:
                return False
        return count == 1
Explanation:
Repeatedly clear the lowest set bit and count. A power of two clears exactly once. More general than the bit trick but equivalent for this problem.

Time: O(log n) · Space: O(1)

8. Sum of Two Integers (Leetcode:371)#

Problem Statement

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = 2, b = 3
Output: 5

Constraints:

-1000 <= a, b <= 1000

Code and Explanation 

1
2
3
4
5
6
7
8
class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF  # 32-bit mask
        while b:
            carry = (a & b) << 1
            a = (a ^ b) & MASK
            b = carry & MASK
        return a if a <= 0x7FFFFFFF else ~(a ^ MASK)
Explanation:
XOR gives sum without carry; (a & b) << 1 is the carry. Repeat until carry is 0. The mask simulates 32-bit overflow; the final line converts back to a signed Python int.

  1. a ^ b = bit-sum without carries.
  2. (a & b) << 1 = carry shifted left.
  3. Loop until no carry remains.

Time: O(1) per word size · Space: O(1)

1
2
3
4
5
class Solution:
    def getSum(self, a: int, b: int) -> int:
        if b == 0:
            return a
        return self.getSum(a ^ b, (a & b) << 1)
Explanation:
Same logic recursively: base case when carry is 0, otherwise recurse with XOR sum and shifted carry. Clean but uses call-stack depth proportional to carry chain length.

Time: O(1) per word size · Space: O(1) iterative equivalent; O(log n) stack depth here

9. Total Hamming Distance (Leetcode:477)#

Problem Statement

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

Example 1:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2:

Input: nums = [4,14,4]
Output: 4

Constraints:

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^9
The answer for the given input will fit in a 32-bit integer.

Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        hamming_distance = 0
        for i in range(32):
            ones = sum((num >> i) & 1 for num in nums)
            hamming_distance += ones * (len(nums) - ones)
        return hamming_distance
Explanation:
For each bit position, count how many numbers have a 1 (ones). Each pair with different bits at that position contributes 1: ones * (n - ones) pairs across the split. Sum over all 32 bits instead of checking every pair.

Time: O(32 · n) · Space: O(1)

1
2
3
4
5
6
7
8
9
class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        hamming_distance = 0
        mask = 1
        for i in range(32):
            zeros = sum(1 for num in nums if (num & mask) == 0)
            hamming_distance += zeros * (len(nums) - zeros)
            mask <<= 1
        return hamming_distance
Explanation:
Same idea as Approach 1, but uses a shifting mask instead of right-shifting each number. Count zeros at each bit, multiply by ones to get differing pairs at that position.

Time: O(32 · n) · Space: O(1)

10. Bitwise AND of Numbers Range (Leetcode:201)#

Problem Statement

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

Constraints:

0 <= left <= right <= 2^31 - 1

Code and Explanation 

1
2
3
4
5
6
7
8
class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        shift = 0
        while left != right:
            left >>= 1
            right >>= 1
            shift += 1
        return left << shift
Explanation:
AND over a range zeroes out any bit position where numbers differ. Those differing bits are exactly the trailing bits that change as you walk from left to right. Shift both right until equal — that value is the shared prefix — then shift back.

Time: O(log n) · Space: O(1)

1
2
3
4
5
class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        while left < right:
            right = right & (right - 1)
        return right
Explanation:
right & (right - 1) clears the lowest set bit of right. Keep clearing until right <= left. The surviving bits are those set in every number from left to the original right.

Time: O(log n) · Space: O(1)

11. Gray Code (Leetcode:89)#

Problem Statement

An n-bit gray code sequence is a sequence of 2^n integers where:

  • Every integer is in the inclusive range [0, 2^n - 1],
  • The first integer is 0,
  • An integer appears no more than once in the sequence,
  • The binary representation of every pair of adjacent integers differs by exactly one bit, and
  • The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

Example 1:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].

  • 00 and 01 differ by one bit
  • 01 and 11 differ by one bit
  • 11 and 10 differ by one bit
  • 10 and 00 differ by one bit

[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].

  • 00 and 10 differ by one bit
  • 10 and 11 differ by one bit
  • 11 and 01 differ by one bit
  • 01 and 00 differ by one bit

Example 2:

Input: n = 1
Output: [0,1]

Constraints:

1 <= n <= 16

Code and Explanation 

1
2
3
class Solution:
    def grayCode(self, n: int) -> List[int]:
        return [i ^ (i >> 1) for i in range(1 << n)]
Explanation:
The formula gray(i) = i ^ (i >> 1) converts binary index i to its Gray code. Adjacent indices differ in exactly one bit, so their Gray codes differ in exactly one bit too. Generates all 2^n values starting from 0.

Time: O(2^n) · Space: O(2^n)

12. XOR Queries of a Subarray (Leetcode:1310)#

Problem Statement

You are given an array arr of positive integers. You are also given the array queries where queries[i] = [lefti, righti].

For each query i compute the XOR of elements from lefti to righti (that is, arr[lefti] XOR arr[lefti + 1] XOR ... XOR arr[righti] ).

Return an array answer where answer[i] is the answer to the ith query.

Example 1:

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8]
Explanation:
The binary representation of the elements in the array are:
1 = 0001
3 = 0011
4 = 0100
8 = 1000
The XOR values for queries are:
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8

Example 2:
Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]

Constraints:

1 <= arr.length, queries.length <= 3 * 10^4
1 <= arr[i] <= 10^9
queries[i].length == 2
0 <= lefti <= righti < arr.length

Code and Explanation 

1
2
3
4
5
6
class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        prefix = [0]
        for num in arr:
            prefix.append(prefix[-1] ^ num)
        return [prefix[r + 1] ^ prefix[l] for l, r in queries]
Explanation:
Build prefix XOR where prefix[i] = arr[0] ^ ... ^ arr[i-1]. Subarray XOR [l..r] = prefix[r+1] ^ prefix[l] because XOR is self-inverse. Each query answered in O(1).

Time: O(n + q) · Space: O(n)

1
2
3
4
5
6
7
8
9
class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        answer = []
        for l, r in queries:
            curr = 0
            for i in range(l, r + 1):
                curr ^= arr[i]
            answer.append(curr)
        return answer
Explanation:
XOR each query range directly. Simple but O(n) per query; fine for small inputs, not for large constraint sizes.

Time: O(n · q) · Space: O(1) extra

13. Find Longest Awesome Substring (Leetcode:1542)#

Problem Statement

You are given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it a palindrome.

Return the length of the maximum length awesome substring of s.

Example 1:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2:

Input: s = "12345678"
Output: 1

Example 3:

Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

Constraints:

1 <= s.length <= 10^5
s consists only of digits.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def longestAwesome(self, s: str) -> int:
        mask = 0
        first_seen = {0: -1}
        ans = 0

        for i, ch in enumerate(s):
            mask ^= 1 << int(ch)

            if mask in first_seen:
                ans = max(ans, i - first_seen[mask])
            else:
                first_seen[mask] = i

            for d in range(10):
                target = mask ^ (1 << d)
                if target in first_seen:
                    ans = max(ans, i - first_seen[target])

        return ans
Explanation:
A substring can be rearranged into a palindrome iff at most one digit has odd frequency. Track parity of each digit (0–9) with a 10-bit mask. Prefixes with the same mask have even counts for all digits between them. Masks differing by one bit allow exactly one odd count. Store earliest index per mask.

Time: O(10 · n) · Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def longestAwesome(self, s: str) -> int:
        def can_form_palindrome(freq):
            odd = sum(1 for c in freq.values() if c % 2 == 1)
            return odd <= 1

        n = len(s)
        ans = 1
        for i in range(n):
            freq = {}
            for j in range(i, n):
                freq[s[j]] = freq.get(s[j], 0) + 1
                if can_form_palindrome(freq):
                    ans = max(ans, j - i + 1)
        return ans
Explanation:
Check every substring's digit frequencies; palindrome possible when at most one odd count. Correct but O(n² · 10) — useful to understand the condition before the bitmask optimization.

Time: O(n²) · Space: O(1)

14. Shortest Subarray With OR at Least K II (Leetcode:3097)#

Problem Statement

You are given an array nums of non-negative integers and an integer k.

An array is called special if the bitwise OR of all of its elements is at least k.

Return the length of the shortest special non-empty subarray of nums, or return -1 if no special subarray exists.

Example 1:

Input: nums = [1,2,3], k = 2
Output: 1
Explanation:
The subarray [3] has OR value of 3. Hence, we return 1.

Example 2:

Input: nums = [2,1,8], k = 10
Output: 3
Explanation:
The subarray [2,1,8] has OR value of 11. Hence, we return 3.

Example 3:

Input: nums = [1,2], k = 0
Output: 1
Explanation:
The subarray [1] has OR value of 1. Hence, we return 1.

Constraints:

1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 10^9
0 <= k <= 10^9

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = float('inf')

        for start in range(n):
            curr = 0
            for end in range(start, n):
                curr |= nums[end]
                if curr >= k:
                    ans = min(ans, end - start + 1)
                    break

        return -1 if ans == float('inf') else ans
Explanation:
For each start index, extend right while OR-ing elements. OR is monotonically non-decreasing, so once curr >= k, that start's shortest valid window is found — break early. Practical when distinct OR values per window are small (~30 bits).

Time: O(n · 30) amortized · Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = float('inf')
        states = []  # (or_value, earliest_start) for subarrays ending at prev index

        for r, num in enumerate(nums):
            new_states = [(num, r)]
            for or_val, start in states:
                new_states.append((or_val | num, start))

            seen = {}
            for or_val, start in new_states:
                if or_val not in seen or start < seen[or_val]:
                    seen[or_val] = start
            states = [(v, s) for v, s in seen.items()]

            for or_val, start in states:
                if or_val >= k:
                    ans = min(ans, r - start + 1)

        return -1 if ans == float('inf') else ans
Explanation:
For each ending index, track distinct OR values along with their earliest start index. When extending by one element, OR each prior state with the new value. Deduplicate keeping the earliest start (shortest window). At most ~30 distinct OR values per position.

Time: O(n · 30) · Space: O(30)

15. Find Subarray With Bitwise OR Closest to K (Leetcode:3171)#

Problem Statement

You are given an array nums and an integer k. You need to find a subarray of nums such that the absolute difference between k and the bitwise OR of the subarray elements is as small as possible. In other words, select a subarray nums[l..r] such that |k - (nums[l] OR nums[l + 1] ... OR nums[r])| is minimum.

Return the minimum possible value of the absolute difference.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,4,5], k = 3
Output: 0
Explanation:
The subarray nums[0..1] has OR value 3, which gives the minimum absolute difference |3 - 3| = 0.

Example 2:

Input: nums = [1,3,1,3], k = 2
Output: 1
Explanation:
The subarray nums[1..1] has OR value 3, which gives the minimum absolute difference |3 - 2| = 1.

Example 3:

Input: nums = [1], k = 10
Output: 9
Explanation:
There is a single subarray with OR value 1, which gives the minimum absolute difference |10 - 1| = 9.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^9

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        ans = float('inf')
        for i in range(len(nums)):
            curr = 0
            for j in range(i, len(nums)):
                curr |= nums[j]
                ans = min(ans, abs(curr - k))
                if curr > k:
                    break  # OR only increases; diff can only grow
        return ans
Explanation:
Try every subarray, tracking running OR. Once curr > k, extending further only increases OR (non-decreasing), so the absolute difference cannot improve — break inner loop early.

Time: O(n · 30) amortized · Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        ans = float('inf')
        ors = []

        for num in nums:
            ors = [num] + [o | num for o in ors]
            ors = list(dict.fromkeys(ors))

            for val in ors:
                ans = min(ans, abs(val - k))

        return ans
Explanation:
For subarrays ending at each index, maintain the small set (~30) of distinct OR values. Check each against k. Avoids redundant subarray scans when many extensions produce the same OR.

Time: O(n · 30) · Space: O(30)

16. Minimize OR of Remaining Elements Using Operations (Leetcode:3022)#

Problem Statement

You are given a 0-indexed integer array nums and an integer k.

In one operation, you can pick any index i of nums such that 0 <= i < nums.length - 1 and replace nums[i] and nums[i + 1] with a single occurrence of nums[i] & nums[i + 1], where & represents the bitwise AND operator.

Return the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.

Example 1:

Input: nums = [3,5,3,2,7], k = 2
Output: 3
Explanation: Let's do the following operations:
1. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [1,3,2,7].
2. Replace nums[2] and nums[3] with (nums[2] & nums[3]) so that nums becomes equal to [1,3,2].
The bitwise-or of the final array is 3.
It can be shown that 3 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k

Example 2:

Input: nums = [7,3,15,14,2,8], k = 4
Output: 2
Explanation: Let's do the following operations:
1. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [3,15,14,2,8].
2. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [3,14,2,8].
3. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [2,2,8].
4. Replace nums[1] and nums[2] with (nums[1] & nums[2]) so that nums becomes equal to [2,0].
The bitwise-or of the final array is 2.
It can be shown that 2 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.

Example 3:

Input: nums = [10,7,10,3,9,14,9,4], k = 1
Output: 15
Explanation: Without applying any operations, the bitwise-or of nums is 15.
It can be shown that 15 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.

Constraints:

1 <= nums.length <= 10^5
0 <= nums[i] < 2^30
0 <= k < nums.length

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minOrAfterOperations(self, nums: List[int], k: int) -> int:
        ans = 0
        for bit in range(29, -1, -1):
            mask = ans | (1 << bit)
            merges_needed = 0
            for num in nums:
                if (num & mask) != mask:
                    merges_needed += 1
                    if merges_needed > k:
                        break
            if merges_needed > k:
                ans |= (1 << bit)
        return ans
Explanation:
Build the answer bit-by-bit from high to low. For each bit, try to keep it 0 in the final OR. Count how many elements don't have all higher-or-equal bits set (merges_needed). Each such element needs at least one AND-merge to eliminate that bit. If more than k merges are required, the bit must stay 1 in the answer.

Time: O(30 · n) · Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minOrAfterOperations(self, nums: List[int], k: int) -> int:
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dfs(arr_tuple, ops_left):
            arr = list(arr_tuple)
            if ops_left == 0 or len(arr) == 1:
                result = 0
                for x in arr:
                    result |= x
                return result

            best = float('inf')
            for i in range(len(arr) - 1):
                new_arr = arr[:i] + [arr[i] & arr[i + 1]] + arr[i + 2:]
                best = min(best, dfs(tuple(new_arr), ops_left - 1))
            return best

        return dfs(tuple(nums), k)
Explanation:
Try every merge sequence recursively and take the minimum OR. Exponential — only for understanding or tiny arrays. The greedy bit approach scales to the full constraint.

Time: Exponential · Space: Exponential

17. Maximum Xor Product (Leetcode:2939)#

Problem Statement

Given three integers a, b, and n, return the maximum value of (a XOR x) * (b XOR x) where 0 <= x < 2^n.

Since the answer may be too large, return it modulo 10^9 + 7.

Note that XOR is the bitwise XOR operation.

Example 1:

Input: a = 12, b = 5, n = 4
Output: 98
Explanation: For x = 2, (a XOR x) = 14 and (b XOR x) = 7. Hence, (a XOR x) * (b XOR x) = 98.
It can be shown that 98 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2^n.

Example 2:

Input: a = 6, b = 7 , n = 5
Output: 930
Explanation: For x = 25, (a XOR x) = 31 and (b XOR x) = 30. Hence, (a XOR x) * (b XOR x) = 930.
It can be shown that 930 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2^n.

Example 3:

Input: a = 1, b = 6, n = 3
Output: 12
Explanation: For x = 5, (a XOR x) = 4 and (b XOR x) = 3. Hence, (a XOR x) * (b XOR x) = 12.
It can be shown that 12 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2^n.

Constraints:

0 <= a, b < 250
0 <= n <= 50

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int:
        MOD = 10**9 + 7
        x = 0
        for i in range(n - 1, -1, -1):
            bit = 1 << i
            prod_without = (a ^ x) * (b ^ x)
            prod_with = (a ^ (x | bit)) * (b ^ (x | bit))
            if prod_with > prod_without:
                x |= bit
        return ((a ^ x) % MOD) * ((b ^ x) % MOD) % MOD
Explanation:
Build x from high bit to low. At each bit, compare the product if we set that bit in x vs leave it unset. Higher bits dominate the product magnitude, so this greedy choice is optimal. Apply modulo only at the end.

Time: O(n) · Space: O(1)

1
2
3
4
5
6
7
class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int:
        MOD = 10**9 + 7
        best = 0
        for x in range(1 << n):
            best = max(best, (a ^ x) * (b ^ x))
        return best % MOD
Explanation:
Try every x in [0, 2^n). Correct and simple when n is small (e.g., n ≤ 20). Impractical for n = 50 but useful to verify the greedy approach on examples.

Time: O(2^n) · Space: O(1)