Algorithm
Bajtek, known for his unusual gifts, recently got an integer array x0,x1,…,xk−1.
Unfortunately, after a huge array-party with his extraordinary friends, he realized that he'd lost it. After hours spent on searching for a new toy, Bajtek found on the arrays producer's website another array a of length n+1. As a formal description of a says, a0=0 and for all other i (1≤i≤n) ai=x(i−1)modk+ai−1, where pmodq denotes the remainder of division p by q.
For example, if the x=[1,2,3] and n=5, then:
- a0=0,
- a1=x0mod3+a0=x0+0=1,
- a2=x1mod3+a1=x1+1=3,
- a3=x2mod3+a2=x2+3=6,
- a4=x3mod3+a3=x0+6=7,
- a5=x4mod3+a4=x1+7=9.
So, if the x=[1,2,3] and n=5, then a=[0,1,3,6,7,9].
Now the boy hopes that he will be able to restore x from a! Knowing that 1≤k≤n, help him and find all possible values of k — possible lengths of the lost array.
The first line contains exactly one integer n (1≤n≤1000) — the length of the array a, excluding the element a0.
The second line contains n integers a1,a2,…,an (1≤ai≤106).
Note that a0 is always 0 and is not given in the input.
The first line of the output should contain one integer l denoting the number of correct lengths of the lost array.
The second line of the output should contain l integers — possible lengths of the lost array in increasing order.
5
1 2 3 4 5
5
1 2 3 4 5
5
1 3 5 6 8
2
3 5
3
1 5 3
1
3
In the first example, any k is suitable, since a is an arithmetic progression.
Possible arrays x:
- [1]
- [1,1]
- [1,1,1]
- [1,1,1,1]
- [1,1,1,1,1]
In the second example, Bajtek's array can have three or five elements.
Possible arrays x:
- [1,2,2]
- [1,2,2,1,2]
For example, k=4 is bad, since it leads to 6+x0=8 and 0+x0=1, which is an obvious contradiction.
In the third example, only k=n is good.
Array [1,4,−2] satisfies the requirements.
Note that xi may be negative.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int const N = 1001;
int n, a[N], x[N];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", a + i);
vector<int> sol;
for(int i = 1; i <= n; ++i) {
x[i - 1] = a[i] - a[i - 1];
bool ok = true;
for(int j = 1, cnt = 0; j <= n; ++j, ++cnt) {
if(x[cnt % i] + a[j - 1] != a[j]) {
ok = false;
break;
}
}
if(ok)
sol.push_back(i);
}
printf("%d\n", int(sol.size()));
for(int i = 0; i < sol.size(); ++i)
printf("%d ", sol[i]);
return 0;
}
Copy The Code &
Try With Live Editor
Input
1 2 3 4 5
Output
1 2 3 4 5
Demonstration
Codeforces Solution-B. Lost Array-Solution in C, C++, Java, Python