FastPrep
Problem

Kth Largest Subarray Bitwise OR

Learn this problem
Uber logoUberFULLTIMEOA
See Uber hiring insights

Problem statement

You are given an integer array nums and an integer k. Consider every non-empty contiguous subarray of nums, and compute the bitwise OR of the elements in that subarray.

Return the k-th largest value among all subarray bitwise OR values. If the same OR value is produced by multiple subarrays, each occurrence is counted separately.

Function

kthLargestSubarrayOr(nums: int[], k: long) → int

Examples

Example 1

nums = [1, 2, 3]k = 5return = 2

The subarray OR values are 1, 3, 3, 2, 3, 3. In descending order they are 3, 3, 3, 3, 2, 1, so the 5th largest value is 2.

Example 2

nums = [5, 1]k = 2return = 5

The OR values are 5, 5, and 1. The 2nd largest occurrence is still 5.

Constraints

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109
  • 1 <= k <= nums.length * (nums.length + 1) / 2

More Uber problems

drafts saved locally
public int kthLargestSubarrayOr(int[] nums, long k) {
  // write your code here
}
nums[1, 2, 3]
k5
expected2
checking account