 # NOTDIVISIBLE - Editorial

Author: satyam_343
Testers: iceknight1093, yash_daga
Editorialist: iceknight1093

TBD

None

# PROBLEM:

Given N, construct an array A of length N such that:

• -1000 \leq A_i \leq 1000
• For each 1 \leq i \lt j \leq N, the sum A_i + A_{i+1} + \ldots + A_j is not divisible by j-i+1. That is, the subarray sum is not divisible by its length.

# EXPLANATION:

The simplest way to ensure that one number (say x) is not divisible by another number (say y) is to see whether 0 \lt x \lt y. If x is smaller then y, of course y can’t be a factor of x.

Let’s try to use this idea.
Consider the array A = [1, 0, 1, 0, \ldots], with alternating zeros and ones.
Since A contains only ones and zeros, the sum of any subarray cannot exceed its length.

Also, any subarray of length \gt 1 contains at least one zero and at least one 1.
This means any such subarray has a strictly positive sum, while also having a sum that’s strictly less than its length.

This is exactly what we wanted!

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

Setter's code (C++)
#include <iostream>
using namespace std;

int main() {
int t; cin>>t;
while(t--){
int n; cin>>n; n++;
while(--n){
cout<<(n&1)<<" ";
}
cout<<"\n";
}
return 0;
}

Editorialist's code (Python)
a = [0, 1]*300
for _ in range(int(input())):
n = int(input())
print(*a[:n])

1 Like

why 1 0 0 0 0 0 … is Not true, May be I’m wrong so, someone plz help me,
edited : got it, we have to consider subarray also

You have to use alternate 0 and 1 because if you take the length from 2 to 3 or any other(excluding 1) then the sum of subarray is 0(which is not possible).