Minimize OR of Remaining Elements Using Operations

Minimize OR of Remaining Elements Using Operations - 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 the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.

Input & Output

Example 1 — Basic Case

$ Input: nums = [7,3,15,14], k = 1

› Output: 15

💡 Note: We can merge adjacent elements using AND. For instance, merge 3&15=3, resulting in [7,3,14]. The OR of this array is 7|3|14 = 15.

Example 2 — Multiple Operations

$ Input: nums = [10,7,10,3,9], k = 2

› Output: 7

💡 Note: First operation: merge 10&7=2, getting [2,10,3,9]. Second operation: merge 10&3=2, getting [2,2,9]. Final OR: 2|2|9 = 11. Actually, better strategy gives OR = 7.

Example 3 — No Operations Needed

$ Input: nums = [5], k = 2

› Output: 5

💡 Note: Array has only one element, so no operations can be performed. The OR is simply 5.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ k ≤ nums.length - 1
1 ≤ nums[i] ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [7,3,15,14] with k=1 operations allowed

AND Operation

Merge adjacent pairs using bitwise AND

Minimize OR

Choose merge that gives smallest OR of remaining elements

Key Takeaway

🎯 Key Insight: AND operations can only clear bits, so strategic merging of adjacent elements minimizes the final OR value

Asked in

G Google 15 M Meta 12 A Amazon 8

The key insight is that AND operations can only reduce bits, making strategic adjacent merges crucial for minimizing the final OR. The greedy approach works well by always choosing merges that result in the smallest OR value. Best approach achieves Time: O(k × n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Priority Queue Approach	O(k × n²)	O(n)	Use priority queue to always merge the pair that minimizes the resulting OR
Brute Force - Try All Operation Sequences	O(n^k × n)	O(k)	Try every possible sequence of k operations and find minimum OR
Optimized Bit Analysis	O(k × n × log(max(nums)))	O(n)	Analyze bit patterns to determine optimal merging strategy

Greedy - Priority Queue Approach — Algorithm Steps

Calculate initial OR of the array
For each adjacent pair, compute OR after merging
Use priority queue to select best merge
Repeat until k operations done

Visualization

Tap to expand

Step-by-Step Walkthrough

Evaluate Merges

For each adjacent pair, calculate resulting OR if merged

Choose Best

Select merge that produces minimum OR value

Repeat

Continue until k operations completed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int calculateOR(int* arr, int size) {
    int result = 0;
    for (int i = 0; i < size; i++) {
        result |= arr[i];
    }
    return result;
}

int solution(int* nums, int numsSize, int k) {
    int* arr = (int*)malloc(numsSize * sizeof(int));
    memcpy(arr, nums, numsSize * sizeof(int));
    int arrSize = numsSize;
    
    for (int op = 0; op < k; op++) {
        if (arrSize <= 1) break;
        
        int bestOR = INT_MAX;
        int bestIdx = -1;
        
        // Try merging each adjacent pair
        for (int i = 0; i < arrSize - 1; i++) {
            int mergedVal = arr[i] & arr[i + 1];
            int* tempArr = (int*)malloc((arrSize - 1) * sizeof(int));
            int tempSize = 0;
            
            for (int j = 0; j < i; j++) tempArr[tempSize++] = arr[j];
            tempArr[tempSize++] = mergedVal;
            for (int j = i + 2; j < arrSize; j++) tempArr[tempSize++] = arr[j];
            
            int tempOR = calculateOR(tempArr, tempSize);
            if (tempOR < bestOR) {
                bestOR = tempOR;
                bestIdx = i;
            }
            
            free(tempArr);
        }
        
        // Perform the best merge
        if (bestIdx != -1) {
            int mergedVal = arr[bestIdx] & arr[bestIdx + 1];
            int* newArr = (int*)malloc((arrSize - 1) * sizeof(int));
            int newSize = 0;
            
            for (int j = 0; j < bestIdx; j++) newArr[newSize++] = arr[j];
            newArr[newSize++] = mergedVal;
            for (int j = bestIdx + 2; j < arrSize; j++) newArr[newSize++] = arr[j];
            
            free(arr);
            arr = newArr;
            arrSize = newSize;
        }
    }
    
    int result = calculateOR(arr, arrSize);
    free(arr);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × n²)

For k operations, each requiring O(n) to find best merge and O(n) to calculate OR

⚠ Quadratic Growth

Space Complexity

O(n)

Priority queue stores at most n-1 potential merges

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Priority Queue Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler