Make One From Multiples

Hard

You are given an array of positive integers values. You may pick any of its elements, multiply each picked element by any integer (negative ones included) and add the results up. Return True if the sum can be exactly 1, and False otherwise.

Example 1

values=[6, 10, 15] → True

6·1 + 10·1 + 15·(−1) = 1.

Example 2

values=[4, 8, 14] → False

All the numbers are even, so every such sum is even as well and can never be 1.

Example 3

values=[1000000000, 999999999] → True

1000000000·1 + 999999999·(−1) = 1.

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Number Theory

Similar problems

Biggest Shared-Factor Group Hard Towns Joined by Big Divisors Hard Nearest Coprime Ancestor Hard Distinct GCDs of Selections Hard Sorting With Shared-Divisor Swaps Hard

Input

values=[6, 10, 15]

Expected

True

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