Find Subarray With Bitwise OR Closest to K

Find Subarray With Bitwise OR Closest to K - Problem

You are given an array nums and an integer k. You need to find a subarray of nums such that the absolute difference between k and the bitwise OR of the subarray elements is as small as possible.

In other words, select a subarray nums[l..r] such that |k - (nums[l] OR nums[l + 1] ... OR nums[r])| is minimum.

Return the minimum possible value of the absolute difference.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Perfect Match

$ Input: nums = [1,2,4,8], k = 6

› Output: 0

💡 Note: Subarray [2,4] has OR = 2|4 = 6, so |6-6| = 0 is the minimum possible difference

Example 2 — Close Match

$ Input: nums = [1,3,1,3], k = 2

› Output: 1

💡 Note: Subarray [1] has OR = 1, and |2-1| = 1. Subarray [3] has OR = 3, and |2-3| = 1. Both give minimum difference of 1

Example 3 — Single Element

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

› Output: 2

💡 Note: Only one subarray possible: [7] with OR = 7. Difference is |5-7| = 2

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array of integers and target k

Compute OR Values

Calculate OR for all possible subarrays

Find Minimum

Return minimum |k - OR| difference

Key Takeaway

🎯 Key Insight: OR operation only adds bits, so we can efficiently track unique OR values without redundant calculations

Asked in

G Google 35 M Microsoft 28 A Amazon 22

The key insight is that bitwise OR can only add bits, never remove them, so OR values only increase as we extend subarrays. The optimal approach uses bit manipulation to track unique OR values efficiently. Time: O(n × log(max_value)), Space: O(log(max_value))

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Optimization	O(n × log(max_value))	O(log(max_value))	Process each element once while maintaining all possible OR values
Bit Manipulation Optimization	O(n × log(max_value))	O(log(max_value))	Use bit patterns to avoid redundant OR calculations
Brute Force	O(n²)	O(1)	Check all possible subarrays and find the one with OR closest to k

Single Pass Optimization — Algorithm Steps

Initialize with empty OR set
For each element, extend all existing ORs and add element itself
Track minimum difference throughout the process

Visualization

Tap to expand

Step-by-Step Walkthrough

Add Element

Process next array element

Extend ORs

OR current element with all existing values

Update Min

Check new ORs against target k

Code -

solution.c — C

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

int solution(int* nums, int numsSize, int k) {
    int minDiff = INT_MAX;
    int currentOrs[32];
    int orCount = 0;
    
    for (int i = 0; i < numsSize; i++) {
        int newOrs[32];
        int newOrCount = 1;
        newOrs[0] = nums[i];
        
        for (int j = 0; j < orCount; j++) {
            int newOr = currentOrs[j] | nums[i];
            int found = 0;
            for (int p = 0; p < newOrCount; p++) {
                if (newOrs[p] == newOr) {
                    found = 1;
                    break;
                }
            }
            if (!found) {
                newOrs[newOrCount++] = newOr;
            }
        }
        
        for (int j = 0; j < newOrCount; j++) {
            int diff = abs(k - newOrs[j]);
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
        
        orCount = newOrCount;
        for (int j = 0; j < orCount; j++) {
            currentOrs[j] = newOrs[j];
        }
    }
    
    return minDiff;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n × log(max_value))

Single pass with at most log(max_value) unique OR values per position

⚡ Linearithmic

Space Complexity

O(log(max_value))

Set stores unique OR values, bounded by number of distinct bit patterns

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 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

Single Pass Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler