FastPrepMinimum Values with Even Powers of Two

Minimum Values with Even Powers of Two

Visa logoVisa● MediumFULLTIMENEW GRADOA
Learn

Problem statement

For each value x in the integer array arr, find the minimum positive integer k such that x can be written as a sum of exactly k positive integers under these rules:

  • Exactly k - 1 summands are powers of two with positive even exponents: 4, 16, 64, .... A value may be used more than once.
  • Exactly one summand is less than 4, so it must be 1, 2, or 3.

If no valid representation exists, return -1 for that value. Return the answers in the same order as arr.

Function

getMinimumValues(arr: int[]) → int[]

Examples

Example 1

arr = [5,1,4,6,10]return = [2,1,-1,2,3]

The valid minimum representations include 5 = 1 + 4, 1 = 1, 6 = 2 + 4, and 10 = 2 + 4 + 4. The value 4 cannot include exactly one summand smaller than 4, so its answer is -1.

Example 2

arr = [2,3,7,21,64]return = [1,1,2,3,-1]

The values 2 and 3 each use one small summand. Also, 7 = 3 + 4 and 21 = 1 + 4 + 16. A multiple of 4, such as 64, cannot satisfy the required small summand.

Constraints

  • 1 <= arr.length <= 2 * 10^5.
  • 1 <= arr[i] <= 10^9.

More Visa problems

See Visa hiring insights
public int[] getMinimumValues(int[] arr) {
  // write your code here
}
arr[5,1,4,6,10]
expected[2,1,-1,2,3]
Checking account…