How should I practice Minimum Power-of-Two Removal Operations?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Visa online assessment problems in FastPrep.

Is Minimum Power-of-Two Removal Operations associated with Visa?

FastPrep tags this as a Visa online assessment coding practice problem when the problem catalog has that company and stage context.

Minimum Power-of-Two Removal Operations

Visa● MediumINTERNOA

Learn

Problem statement

You are given an integer array arr of length n. You may perform the following operation any number of times until the array becomes empty:

Let m be the current size of the array.
Choose an integer k such that 1 <= k <= m, and remove any k elements from the array.
The removal is allowed only when the chosen elements satisfy 2^arr[i1] + 2^arr[i2] + ... + 2^arr[ik] = 2^p for some integer p >= 0.

You may remove elements from any positions; they do not need to be consecutive. The exponent p may differ between operations.

Return the minimum number of operations required to remove every element from the array.

Function

findMinOperations(arr: int[]) → int

Examples

Example 1

arr = [1,1,3,2,3]return = 2

Remove the elements at positions 1, 2, and 4. Their sum is 2^1 + 2^1 + 2^2 = 2^3, leaving [3,3].
Remove the two remaining elements because 2^3 + 2^3 = 2^4.

The array is empty after two operations.

Example 2

arr = [1,1,3,5]return = 3

Remove the two values 1 together because 2^1 + 2^1 = 2^2. The values 3 and 5 must then be removed in separate operations, so the minimum is 3.

Example 3

arr = [0,0,0,0]return = 1

All four elements can be removed together because 2^0 + 2^0 + 2^0 + 2^0 = 2^2.

Constraints

1 <= n <= 10^5.
0 <= arr[i] <= 10^6.