Doubling for the Biggest OR

Medium

You are given an array of positive integers values and an integer doublings. In one operation you pick any element and multiply it by 2; you may do at most doublings operations in total. Return the largest possible bitwise OR of all elements after the operations.

Example 1

values=[5, 3], doublings=1 → 11

Doubling 5 gives 10 | 3 = 11. Doubling 3 is worse: 5 | 6 = 7.

Example 2

values=[1, 4, 2], doublings=3 → 35

All three doublings go to 4: 32 | 1 | 2 = 35.

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁹
1 ≤ doublings ≤ 15

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Bit Manipulation Array Prefix Sum

Similar problems

Studios for Recording Sessions Medium Best Binary Rows After Flips Medium Palindrome After a Few Fixes Medium Range XOR Lookups Medium Groups of Four at the Cinema Medium

Input

values=[5, 3], doublings=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 113 tests on the server, hidden ones included.