We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimize OR of Remaining Elements Using Operations

Number: 3261

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an integer array nums and an integer k, you may perform at most k operations. In one operation you choose an index i (0 <= i < nums.length-1) and replace nums[i] and nums[i+1] with a single number equal to (nums[i] & nums[i+1]) (bitwise AND). After performing some or no operations, the final array is a partition of the original array into contiguous segments whose value is the bitwise AND of the numbers in the segment. The task is to choose the operations (i.e. choose a segmentation with at least n-k segments) so that the bitwise OR of all segment values is minimized.

Key Insights

  • Merging two adjacent numbers is equivalent to taking the AND of a contiguous segment; the order of mergers does not affect the final value.
  • The final array is obtained by partitioning the original array into segments where each segment’s value equals the AND of all its elements.
  • The bitwise AND of a segment never turns a 0 bit back into 1, so the only effect is to possibly “turn off” some bits.
  • For any given bit position, to ensure that it does not appear in the final OR, every segment’s AND must have that bit off – which happens if each segment has at least one number with that bit equal to 0.
  • We are allowed at most k operations which implies the final number of segments must be at least n – k.
  • A greedy segmentation (cut as soon as the cumulative AND meets “good” criteria) maximizes the number of segments, which is exactly what is needed in the feasibility check.

Space and Time Complexity

Time Complexity: O(n * B) where B is the number of bits (≈31) so roughly O(31*n).
Space Complexity: O(1) (apart from input storage)

Solution

We can reframe the problem by noting that merging corresponds to partitioning the array into contiguous segments. Each segment’s value is the AND of its elements, and the final answer is the bitwise OR of these segment values. To minimize this OR, we would like to “turn off” as many bits as possible.

For each bit position, if we want the final OR to have a 0 in that position, then every segment must have a 0 in that bit – i.e. each segment’s AND must not include that bit. A segment’s AND will be 0 in a bit position if at least one element in the segment does not have that bit set.

We use a bit‐DP (greedy “bit by bit” selection) strategy:

  1. Process bits from the most significant (30) down to 0.
  2. Try to avoid “allowing” the current bit (i.e. keep it 0) if possible. In other words, assume that the final OR does not include that bit.
  3. Check if it is possible to partition the array into segments (using a greedy scan) where in each segment the cumulative AND does not have any “forbidden” bits (bits that we wish to be 0 in the final answer). A forbidden bit is a bit that is 0 in the candidate mask.
  4. If the segmentation requirement can be met with at least n-k segments then we can leave the current bit as 0; otherwise, we are forced to “allow” it (set it to 1 in our candidate answer) so that the constraint is looser.
  5. The feasibility check uses a greedy approach: iterate over nums while maintaining the cumulative AND. When the cumulative AND does not have any bit outside the candidate mask (i.e. (current & ~candidate) == 0), then a segment can be formed and the cumulative AND is reset; this greedy method maximizes the segment count.
  6. Finally, the candidate mask built in this way is the minimum possible OR.

Data structures used include a simple integer mask for tracking the candidate bits and a variable to maintain the cumulative AND during the greedy segmentation.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with line-by-line comments.

# Python solution

def minimizeOr(nums, k):
    n = len(nums)
    # Define maximum mask for 31-bit numbers (all ones)
    ALL_ONES = (1 << 31) - 1

    # Function to check if it is possible to partition nums into segments
    # with at least (n - k) segments such that for every segment,
    # the cumulative AND does not have any bits outside candidate_mask.
    def feasible(candidate_mask):
        seg_count = 0
        curr_and = ALL_ONES
        for num in nums:
            curr_and &= num  # update cumulative AND for current segment
            # If the current segment's AND does not include any forbidden bits
            if (curr_and & ~candidate_mask) == 0:
                seg_count += 1  # we can cut here
                curr_and = ALL_ONES  # reset for next segment
        return seg_count >= n - k

    ans = 0
    # Process bits from most significant (30) down to 0.
    for bit in range(30, -1, -1):
        # Try to keep bit = 0 if possible; candidate remains ans.
        # If not feasible, we set this bit to 1.
        if not feasible(ans):
            ans |= (1 << bit)
        else:
            # Even if feasible, we try to see if we can avoid setting the current bit.
            # We check feasibility with candidate = ans (which excludes current bit if not set)
            # If not feasible, then we have already forced this bit.
            pass
    return ans

# Example usage:
print(minimizeOr([3,5,3,2,7], 2))  # Expected output 3
print(minimizeOr([7,3,15,14,2,8], 4))  # Expected output 2
print(minimizeOr([10,7,10,3,9,14,9,4], 1))  # Expected output 15
← Back to All Questions