PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given N, construct an array of length N containing non-zero integers with absolute value not exceeding 3, such that the sum of the array is 0.
EXPLANATION:
If N is even, a very simple construction is to just use \frac{N}{2} copies each of +1 and -1, for example to obtain [1, -1, 1, -1, \ldots, 1, -1].
What if N is odd?
The sample cases showcase that there’s no solution when N = 1, and give the array [1, 2, -3] for N = 3.
But now we can simply replicate what we did for even N, i.e. use an equal number of 1's and -1's.
So, for odd N that’s \geq 3, we obtain [1, 2, -3, 1, -1, 1, -1, \ldots, 1, -1] as one construction.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
if n == 1:
print(-1)
continue
ans = []
if n%2 == 1:
ans = [1, 2, -3]
n -= 3
while n > 0:
ans.append(1)
ans.append(-1)
n -= 2
print(*ans)