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 IBM online assessment problems in FastPrep.

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

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

Minimum Power-of-Two Removal Operations

IBM● MediumFULLTIMEOA

Learn

Problem statement

You are given an array arr of nonnegative integer exponents. Each element arr[i] represents the value 2^arr[i].

In one operation, select a nonempty group of remaining elements and remove them. The operation is allowed only if the sum of their represented values is exactly 2^p for some integer p >= 0.

You may select elements from any positions; they do not need to be consecutive.
Each element can be removed only once.
The exponent p may differ between operations and may exceed the largest exponent in the input.

Return the minimum number of operations needed to remove all elements.

Function

findMinOperations(arr: int[]) → int

Examples

Example 1

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

Remove all four elements together: 2^0 + 2^0 + 2^1 + 2^2 = 1 + 1 + 2 + 4 = 8 = 2^3. A nonempty array needs at least one operation, so the minimum is 1.

Example 2

arr = [0,2,2]return = 2

Remove the two elements with exponent 2 together, since 4 + 4 = 8. Then remove the element with exponent 0. One operation is impossible because the total 9 is not a power of two, so the minimum is 2.

Example 3

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

The represented values are 1, 2, and 16. No group containing two or more of them sums to a power of two, so each must be removed separately.

Constraints

For this exercise, assume 1 <= arr.length <= 10^5.
For this exercise, assume 0 <= arr[i] <= 10^6.
Every element is an integer exponent, and the input order imposes no restriction on a removal group.