LeetCode #3022 — HARD

Minimize OR of Remaining Elements Using Operations

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

Solve on LeetCode
The Problem

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 operations.

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 <= 105
  • 0 <= nums[i] < 230
  • 0 <= k < nums.length
Patterns Used
🎯Greedy→⚡Bit Manipulation→

Roadmap

  1. Brute Force Baseline
  2. Core Insight
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Study Demo
  7. Complexity Analysis
Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Greedy · Bit Manipulation

Example 1

[3,5,3,2,7]
2

Example 2

[7,3,15,14,2,8]
4

Example 3

[10,7,10,3,9,14,9,4]
1

Related Problems

  • Maximum XOR After Operations (maximum-xor-after-operations)
  • Apply Operations on Array to Maximize Sum of Squares (apply-operations-on-array-to-maximize-sum-of-squares)
Step 02

Core Insight

What unlocks the optimal approach

  • From the most significant bit to the least significant bit, maintain the bits that will not be included in the final answer in a variable <code>mask</code>.
  • For a fixed bit, add it to <code>mask</code> then check if there exists some sequence of <code>k</code> operations such that <code>mask & answer == 0 </code> where <code>answer</code> is the bitwise-or of the remaining elements of <code>nums</code>. If there is no such sequence of operations, remove the current bit from <code>mask</code>. How can we perform this check?
  • Let <code>x</code> be the bitwise-and of all elements of <code>nums</code>. If <code>x AND mask != 0</code>, there is no sequence of operations that satisfies the condition in the previous hint. This is because even if we perform this operation <code>n - 1</code> times on the array, we will end up with <code>x</code> as the final element.
  • Otherwise, there exists at least one such sequence. It is sufficient to check if the number of operations in such a sequence is less than <code>k</code>. Let’s calculate the minimum number of operations in such a sequence.
  • Iterate over the array from left to right, if <code>nums[i] & mask != 0</code>, apply the operation on index <code>i</code>.
  • After iterating over all elements, let <code>x</code> be the bitwise-and of all elements of <code>nums</code>. If <code>x == 0</code>, then we have found the minimum number of operations. Otherwise, It can be proven that we need exactly one more operation so that <code>x == 0</code>.
Interview move: turn each hint into an invariant you can check after every iteration/recursion step.
Step 03

Algorithm Walkthrough

Iteration Checklist

  1. Define state (indices, window, stack, map, DP cell, or recursion frame).
  2. Apply one transition step and update the invariant.
  3. Record answer candidate when condition is met.
  4. Continue until all input is consumed.
Use the first example testcase as your mental trace to verify each transition.
Step 04

Edge Cases

Minimum Input
Single element / shortest valid input
Validate boundary behavior before entering the main loop or recursion.
Duplicates & Repeats
Repeated values / repeated states
Decide whether duplicates should be merged, skipped, or counted explicitly.
Extreme Constraints
Largest constraint values
Re-check complexity target against constraints to avoid time-limit issues.
Invalid / Corner Shape
Empty collections, zeros, or disconnected structures
Handle special-case structure before the core algorithm path.
Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3022: Minimize OR of Remaining Elements Using Operations
class Solution {
    public int minOrAfterOperations(int[] nums, int k) {
        int ans = 0, rans = 0;
        for (int i = 29; i >= 0; i--) {
            int test = ans + (1 << i);
            int cnt = 0;
            int val = 0;
            for (int num : nums) {
                if (val == 0) {
                    val = test & num;
                } else {
                    val &= test & num;
                }
                if (val != 0) {
                    cnt++;
                }
            }
            if (cnt > k) {
                rans += (1 << i);
            } else {
                ans += (1 << i);
            }
        }
        return rans;
    }
}
Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Press Step or Run All to begin.
Step 07

Complexity Analysis

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

Approach Breakdown

EXHAUSTIVE
O(2ⁿ) time
O(n) space

Try every possible combination of choices. With n items each having two states (include/exclude), the search space is 2ⁿ. Evaluating each combination takes O(n), giving O(n × 2ⁿ). The recursion stack or subset storage uses O(n) space.

GREEDY
O(n log n) time
O(1) space

Greedy algorithms typically sort the input (O(n log n)) then make a single pass (O(n)). The sort dominates. If the input is already sorted or the greedy choice can be computed without sorting, time drops to O(n). Proving greedy correctness (exchange argument) is harder than the implementation.

Shortcut: Sort + single pass → O(n log n). If no sort needed → O(n). The hard part is proving it works.
Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Using greedy without proof

Wrong move: Locally optimal choices may fail globally.

Usually fails on: Counterexamples appear on crafted input orderings.

Fix: Verify with exchange argument or monotonic objective before committing.

Related Problems
#861Score After Flipping Matrixmedium→#1386Cinema Seat Allocationmedium→#1558Minimum Numbers of Function Calls to Make Target Arraymedium→#2680Maximum ORmedium→#2708Maximum Strength of a Groupmedium→