Problem

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 _theminimum possible value of the bitwise _OR of the remaining elements of nums after applyingat most k operations.

Examples

Example 1

1
2

Input: nums = [3,5,3,2,7], k = 2
Output: 3

Example 2

1
2

Input: nums = [7,3,15,14,2,8], k = 4
Output: 2

Example 3

1
2

Input: nums = [10,7,10,3,9,14,9,4], k = 1
Output: 15

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] < 2^30
  • 0 <= k < nums.length

Solution

Method 1 – Greedy Bitmasking

Intuition

The goal is to minimize the OR of the array after up to k operations, where each operation merges two adjacent elements using AND. Since AND can only reduce bits, and OR accumulates bits, we want to merge elements that have overlapping bits set, especially those contributing most to the OR. Greedily merging the pairs with the most overlap can help minimize the final OR.

Approach

  1. Use recursion with memoization to try all possible merges up to k times.
  2. For each possible pair, merge and recurse, keeping track of the minimum OR.
  3. Use bitmasking to compute OR and AND efficiently.
  4. Prune branches where k operations are exhausted or array is reduced to one element.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int minimizeOR(vector<int>& nums, int k) {
        function<int(vector<int>, int)> dfs = [&](vector<int> arr, int rem) {
            if (rem == 0 || arr.size() == 1) {
                int ans = 0;
                for (int x : arr) ans |= x;
                return ans;
            }
            int res = INT_MAX;
            for (int i = 0; i < arr.size() - 1; ++i) {
                vector<int> nxt = arr;
                nxt[i] = arr[i] & arr[i+1];
                nxt.erase(nxt.begin() + i + 1);
                res = min(res, dfs(nxt, rem - 1));
            }
            return res;
        };
        return dfs(nums, k);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func minimizeOR(nums []int, k int) int {
    var dfs func([]int, int) int
    dfs = func(arr []int, rem int) int {
        if rem == 0 || len(arr) == 1 {
            ans := 0
            for _, x := range arr {
                ans |= x
            }
            return ans
        }
        res := 1<<31 - 1
        for i := 0; i < len(arr)-1; i++ {
            nxt := make([]int, len(arr))
            copy(nxt, arr)
            nxt[i] = arr[i] & arr[i+1]
            nxt = append(nxt[:i+1], nxt[i+2:]...)
            v := dfs(nxt, rem-1)
            if v < res {
                res = v
            }
        }
        return res
    }
    return dfs(nums, k)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int minimizeOR(int[] nums, int k) {
        return dfs(nums, k);
    }
    private int dfs(int[] arr, int rem) {
        if (rem == 0 || arr.length == 1) {
            int ans = 0;
            for (int x : arr) ans |= x;
            return ans;
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length - 1; ++i) {
            int[] nxt = new int[arr.length - 1];
            for (int j = 0, idx = 0; j < arr.length; ++j) {
                if (j == i) nxt[idx++] = arr[i] & arr[i+1];
                else if (j != i+1) nxt[idx++] = arr[j];
            }
            res = Math.min(res, dfs(nxt, rem - 1));
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun minimizeOR(nums: IntArray, k: Int): Int {
        fun dfs(arr: List<Int>, rem: Int): Int {
            if (rem == 0 || arr.size == 1) return arr.reduce { a, b -> a or b }
            var res = Int.MAX_VALUE
            for (i in 0 until arr.size - 1) {
                val nxt = arr.toMutableList()
                nxt[i] = arr[i] and arr[i+1]
                nxt.removeAt(i+1)
                res = minOf(res, dfs(nxt, rem - 1))
            }
            return res
        }
        return dfs(nums.toList(), k)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def minimizeOR(nums: list[int], k: int) -> int:
    def dfs(arr: list[int], rem: int) -> int:
        if rem == 0 or len(arr) == 1:
            ans = 0
            for x in arr:
                ans |= x
            return ans
        res = 2**31 - 1
        for i in range(len(arr)-1):
            nxt = arr[:]
            nxt[i] = arr[i] & arr[i+1]
            nxt.pop(i+1)
            res = min(res, dfs(nxt, rem-1))
        return res
    return dfs(nums, k)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn minimize_or(nums: Vec<i32>, k: i32) -> i32 {
        fn dfs(arr: Vec<i32>, rem: i32) -> i32 {
            if rem == 0 || arr.len() == 1 {
                arr.iter().fold(0, |acc, &x| acc | x)
            } else {
                let mut res = i32::MAX;
                for i in 0..arr.len()-1 {
                    let mut nxt = arr.clone();
                    nxt[i] = arr[i] & arr[i+1];
                    nxt.remove(i+1);
                    res = res.min(dfs(nxt, rem-1));
                }
                res
            }
        }
        dfs(nums, k)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    minimizeOR(nums: number[], k: number): number {
        function dfs(arr: number[], rem: number): number {
            if (rem === 0 || arr.length === 1) {
                let ans = 0;
                for (const x of arr) ans |= x;
                return ans;
            }
            let res = Number.MAX_SAFE_INTEGER;
            for (let i = 0; i < arr.length - 1; ++i) {
                const nxt = arr.slice();
                nxt[i] = arr[i] & arr[i+1];
                nxt.splice(i+1, 1);
                res = Math.min(res, dfs(nxt, rem - 1));
            }
            return res;
        }
        return dfs(nums, k);
    }
}

Complexity

  • ⏰ Time complexity: O(n^k * n)
    • For each operation, we try all possible pairs, and there are up to k operations, so the recursion tree can be very large for big k and n.
  • 🧺 Space complexity: O(n + k)
    • Due to recursion stack and array copies for each call.