Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
From the most significant bit to the least significant bit, maintain the bits that will not be included in the final answer in a variable <code>mask</code>.
For a fixed bit, add it to <code>mask</code> then check if there exists some sequence of <code>k</code> operations such that <code>mask & answer == 0 </code> where <code>answer</code> is the bitwise-or of the remaining elements of <code>nums</code>. If there is no such sequence of operations, remove the current bit from <code>mask</code>. How can we perform this check?
Let <code>x</code> be the bitwise-and of all elements of <code>nums</code>. If <code>x AND mask != 0</code>, there is no sequence of operations that satisfies the condition in the previous hint. This is because even if we perform this operation <code>n - 1</code> times on the array, we will end up with <code>x</code> as the final element.
Otherwise, there exists at least one such sequence. It is sufficient to check if the number of operations in such a sequence is less than <code>k</code>. Let’s calculate the minimum number of operations in such a sequence.
Iterate over the array from left to right, if <code>nums[i] & mask != 0</code>, apply the operation on index <code>i</code>.
After iterating over all elements, let <code>x</code> be the bitwise-and of all elements of <code>nums</code>. If <code>x == 0</code>, then we have found the minimum number of operations. Otherwise, It can be proven that we need exactly one more operation so that <code>x == 0</code>.
The condition in the second hint is satisfied if and only if the minimum number of operations is less than or equal to <code>k</code>.