Shortest Subarray With OR at Least K I - Practice Coding Problems

Shortest Subarray With OR at Least K I - Problem

You are given an array nums of non-negative integers and an integer k.

An array is called special if the bitwise OR of all of its elements is at least k.

Return the length of the shortest special non-empty subarray of nums, or return -1 if no special subarray exists.

Input & Output

Example 1 — Basic Case

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

› Output: 1

💡 Note: Element 2 by itself has OR = 2 ≥ 2, so minimum length is 1. Element 3 also works with OR = 3 ≥ 2.

Example 2 — Need Multiple Elements

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

› Output: 3

💡 Note: No single element ≥ 10. [2,1] gives OR = 3 < 10. Need all three: [2,1,8] gives OR = 2|1|8 = 11 ≥ 10.

Example 3 — No Solution

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

› Output: -1

💡 Note: Maximum possible OR is 1|2 = 3 < 5, so no subarray can achieve OR ≥ 5.

Constraints

1 ≤ nums.length ≤ 50
0 ≤ nums[i] ≤ 50
0 ≤ k ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,8,16,4] and target k=10

Process

Check subarrays: OR of [8,16] = 24 ≥ 10

Output

Minimum length is 2

Key Takeaway

🎯 Key Insight: Bitwise OR only increases as we add elements, so we can stop expanding once we reach the target

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is that bitwise OR only increases (never decreases) as we add more elements. The optimal approach checks all possible subarrays by trying each starting position and expanding until OR ≥ k. Best approach is brute force with early termination - Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Check all possible subarrays and find the shortest one with OR ≥ k
Sliding Window	O(n²)	O(1)	Use variable-size window that expands until OR ≥ k, then shrinks to find minimum

Brute Force — Algorithm Steps

For each starting position i
For each ending position j ≥ i
Calculate OR of subarray nums[i...j]
If OR ≥ k, update minimum length

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Subarrays

Try all possible starting and ending positions

Calculate OR

For each subarray, compute bitwise OR of all elements

Track Minimum

Keep the shortest length where OR ≥ 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 minLen = INT_MAX;
    
    for (int i = 0; i < numsSize; i++) {
        int currentOr = 0;
        for (int j = i; j < numsSize; j++) {
            currentOr |= nums[j];
            if (currentOr >= k) {
                int len = j - i + 1;
                if (len < minLen) {
                    minLen = len;
                }
                break;
            }
        }
    }
    
    return minLen == INT_MAX ? -1 : minLen;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            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²)

Nested loops iterate through all n² subarray combinations

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses a few variables to track OR and minimum length

✓ Linear Space

12.9K Views

Medium Frequency

~15 min Avg. Time

542 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

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler