BLNDOR - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: kingmessi
Tester: watoac2001
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given N integers, each of which is either one or two.
Can their product be written as k^8, where k is some integer?

EXPLANATION:

First, notice that N can be quite large, so it’s not really feasible to directly compute the product of the array and then check if it’s of the required form — the product of the array can be as large as 2^{200000} which is way too large.

Since each A_i is either 1 or 2, the product of the array will always be some power of 2.
Specifically, if there are m twos in the array, the product of the array is 2^m.

We want 2^m to be an eighth power, which is only possible if m is a multiple of 8.

So, the answer is Yes if m is a multiple of 8, and No otherwise.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    twos = list(map(int, input().split())).count(2)
    print('Yes' if twos%8 == 0 else 'No')