codelessgenie blog

Maximum Bitwise OR Value of a Subsequence of Length K

Bitwise operations are fundamental in computer science, with applications ranging from low-level programming to algorithm optimization. Among these operations, the bitwise OR (|) is particularly useful for combining binary values, as it sets each bit to 1 if at least one of the corresponding bits of the operands is 1. A common problem in this domain is finding the maximum bitwise OR value of a subsequence of a given length ( K ) from an array of integers.

This blog explores the problem in detail, covering definitions, brute force and optimized approaches, best practices, and example implementations. By the end, you will understand how to efficiently solve this problem even for larger input sizes.

2026-07

Table of Contents#

  1. Understanding the Problem
  2. Brute Force Approach
  3. Dynamic Programming Approach
  4. Greedy Bit Manipulation Approach (Limitations)
  5. Best Practices
  6. Example Usage and Code
  7. Conclusion
  8. References

Understanding the Problem#

Key Definitions#

  • Subsequence: A subsequence is a sequence derived from an array by deleting some or no elements without changing the order of the remaining elements. For the purposes of bitwise OR, the order of elements in the subsequence does not matter (since OR is commutative and associative).
  • Bitwise OR: The bitwise OR operation (a | b) compares corresponding bits of two integers. If either bit is 1, the result bit is 1; otherwise, it is 0. For example, 3 | 5 (binary 011 | 101) equals 7 (binary 111).

Problem Statement#

Given an array nums of integers and an integer ( K ), find the maximum bitwise OR value of any subsequence of nums with exactly ( K ) elements.

Example#

For nums = [5, 1, 3] and ( K = 2 ):

  • Possible 2-length subsequences: [5,1] (OR=5), [5,3] (OR=7), [1,3] (OR=3).
  • The maximum OR is 7.

Brute Force Approach#

Idea#

Generate all possible combinations of ( K ) elements from the array, compute their bitwise OR, and track the maximum value.

Implementation#

In Python, this can be done using itertools.combinations to generate all ( K )-length subsequences. For each combination, compute the OR of its elements and update the maximum.

Code Snippet#

import itertools
 
def max_or_brute_force(nums, k):
    max_or = 0
    for combo in itertools.combinations(nums, k):
        current_or = 0
        for num in combo:
            current_or |= num
        if current_or > max_or:
            max_or = current_or
    return max_or

Time Complexity#

  • Generating combinations: ( O(\binom{n}{K}) ), where ( n ) is the array length.
  • Computing OR for each combination: ( O(K) ).
  • Total: ( O(\binom{n}{K} \cdot K) ).

Limitations#

This approach is infeasible for large ( n ) (e.g., ( n > 20 )) because ( \binom{n}{K} ) grows exponentially. For example, ( \binom{20}{10} = 184756 ), but ( \binom{30}{15} \approx 155 ) million, which is computationally prohibitive.

Dynamic Programming Approach#

Idea#

Track all possible OR values for subsequences of length ( j ) (where ( 0 \leq j \leq K )) using dynamic programming (DP). For each element in the array, update the possible OR values for subsequences of length ( j ) by considering whether to include the current element.

State Definition#

  • Let dp[j] be a set of all possible OR values for subsequences of length ( j ).

Transitions#

  • Initialize dp[0] = {0} (the OR of an empty subsequence is 0).
  • For each number num in nums, update dp[j] for ( j ) from ( K ) down to ( 1 ):
    • For each value val in dp[j-1], compute new_or = val | num.
    • Add new_or to dp[j] (to avoid duplicates, use a set).

Example Walkthrough#

Let nums = [5, 1, 3] and ( K = 2 ):

  1. Initialization: dp[0] = {0}, dp[1...2] = empty.
  2. Process 5:
    • For ( j=1 ): dp[0] has 0. new_or = 0 | 5 = 5. So dp[1] = {5}.
  3. Process 1:
    • For ( j=2 ): dp[1] has 5. new_or = 5 | 1 = 5. So dp[2] = {5}.
    • For ( j=1 ): dp[0] has 0. new_or = 0 | 1 = 1. So dp[1] = {5, 1}.
  4. Process 3:
    • For ( j=2 ): dp[1] has 5 and 1.
      • 5 | 3 = 7, 1 | 3 = 3. So dp[2] = {5, 7, 3}.
    • For ( j=1 ): dp[0] has 0. new_or = 0 | 3 = 3. So dp[1] = {5, 1, 3}.
  5. Result: max(dp[2]) = 7.

Time Complexity#

  • For each element in nums (( O(n) )), iterate over ( j ) from ( K ) down to ( 1 ) (( O(K) )).
  • For each dp[j-1], process up to ( B ) OR values (where ( B ) is the number of unique OR values, bounded by the number of possible OR values, which can be up to ( 2^{\text{bits}} )).
  • Total: ( O(n \cdot K \cdot B) \approx O(n \cdot K \cdot 32) ), which is feasible for ( n \leq 10^4 ) and ( K \leq 10^3 ).

Space Complexity#

  • ( O(K \cdot B) ), as each dp[j] stores up to ( B ) OR values.

Greedy Bit Manipulation Approach (Limitations)#

A common intuition is to greedily set the highest possible bits first. For example, start with the highest bit (e.g., 30th for 32-bit integers) and check if it can be set by selecting ( K ) elements. However, this approach often fails because the OR of multiple elements can set higher bits even if individual elements do not.

Example: nums = [1, 2], ( K=2 ). The maximum OR is ( 3 ) (1 | 2), but a greedy approach checking individual elements would not find this, as neither element has the 2nd bit set alone.

Thus, the greedy approach is not reliable for this problem.

Best Practices#

Edge Cases#

  • ( K = 1 ): The maximum OR is simply the maximum element in nums.
  • ( K = n ): The maximum OR is the OR of all elements in nums.
  • ( K = 0 ): Typically invalid (problem constraints usually require ( K \geq 1 )).

Optimizations for DP#

  • Use Sets for dp[j]: Avoid duplicate OR values to keep the size of dp[j] manageable.
  • Iterate ( j ) in Reverse: Update dp[j] from ( K ) down to ( 1 ) to prevent reusing the same element multiple times in the same subsequence.
  • Early Termination: If dp[K] contains the maximum possible OR (e.g., all bits set), terminate early.

Example Usage and Code#

DP Implementation#

def max_or_subsequence(nums, k):
    # Initialize dp: dp[j] is a set of OR values for subsequences of length j
    dp = [set() for _ in range(k + 1)]
    dp[0].add(0)  # Base case: 0 elements, OR is 0
    
    for num in nums:
        # Iterate j from k down to 1 to avoid reusing the same num in the same subset
        for j in range(min(k, len(dp)-1), 0, -1):
            # Update dp[j] by adding OR with values from dp[j-1]
            for val in dp[j-1]:
                new_or = val | num
                dp[j].add(new_or)
    
    return max(dp[k]) if dp[k] else 0  # dp[k] is empty if k > len(nums)

Test Cases#

# Test 1: Basic example
print(max_or_subsequence([5, 1, 3], 2))  # Output: 7
 
# Test 2: K=1 (max element)
print(max_or_subsequence([3, 1, 2], 1))  # Output: 3
 
# Test 3: K equals array length (OR of all elements)
print(max_or_subsequence([1, 2, 4, 8], 4))  # Output: 15 (1|2|4|8)
 
# Test 4: Larger array
print(max_or_subsequence([10, 20, 30, 40], 2))  # Output: 62 (30 | 40 = 62)

Conclusion#

The problem of finding the maximum bitwise OR of a ( K )-length subsequence can be efficiently solved using dynamic programming. The DP approach tracks all possible OR values for subsequences of varying lengths, ensuring we explore all combinations without explicitly generating them. For small to moderately sized arrays, this method is both time and space efficient.

While brute force works for tiny inputs, the DP approach is preferred for most practical scenarios. Always handle edge cases like ( K=1 ) or ( K=n ) separately for optimal performance.

References#