Grow an Array by Its Total

Hard

An array of length n starts out filled with ones. In one move you pick any element and overwrite it with the current sum of all elements (the element being replaced included). You may make as many moves as you like. Given an array goal of length n, return True if the array of ones can be turned into exactly goal, and False otherwise.

Example 1

goal=[3, 1, 5] → True

[1, 1, 1] → the sum is 3 → [3, 1, 1] → the sum is 5 → [3, 1, 5].

Example 2

goal=[2, 2] → False

From [1, 1] the first move gives [2, 1] or [1, 2], and every later move writes a value of at least 3. [2, 2] is out of reach.

Example 3

goal=[1, 7] → True

Constraints

1 ≤ n = len(goal) ≤ 5·10⁴
1 ≤ goal[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Heap (Priority Queue)

Similar problems

City Block Outline Hard Moving Window Maximum Hard Rain Pools on a Relief Map Hard Moving Window Median Hard Ball Into the Hole Hard

Input

goal=[3, 1, 5]

Expected

True

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