Codeforces Solution-B. Lost Array-Solution in C, C++, Java, Python

Algorithm

Bajtek, known for his unusual gifts, recently got an integer array $x_{0}, x_{1}, \dots, x_{k - 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, $a_{0} = 0$ and for all other $i$ ( $1 \leq i \leq n$ ) $a_{i} = x_{(i - 1) mod k} + a_{i - 1}$ , where $p mod q$ denotes the remainder of division $p$ by $q$ .

For example, if the $x = [1, 2, 3]$ and $n = 5$ , then:

$a_{0} = 0$ ,
$a_{1} = x_{0 mod 3} + a_{0} = x_{0} + 0 = 1$ ,
$a_{2} = x_{1 mod 3} + a_{1} = x_{1} + 1 = 3$ ,
$a_{3} = x_{2 mod 3} + a_{2} = x_{2} + 3 = 6$ ,
$a_{4} = x_{3 mod 3} + a_{3} = x_{0} + 6 = 7$ ,
$a_{5} = x_{4 mod 3} + a_{4} = x_{1} + 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 \leq k \leq n$ , help him and find all possible values of $k$ — possible lengths of the lost array.

Input

The first line contains exactly one integer $n$ ( $1 \leq n \leq 1000$ ) — the length of the array $a$ , excluding the element $a_{0}$ .

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{6}$ ).

Note that $a_{0}$ is always $0$ and is not given in the input.

Output

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.

Examples
input
Copy
5
1 2 3 4 5
output
Copy
5
1 2 3 4 5 
input
Copy
5
1 3 5 6 8
output
Copy
2
3 5 
input
Copy
3
1 5 3
output
Copy
1
3 

Note

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 + x_{0} = 8$ and $0 + x_{0} = 1$ , which is an obvious contradiction.

In the third example, only $k = n$ is good.

Array $[1, 4, - 2]$ satisfies the requirements.

Note that $x_{i}$ 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

–

cmd

5
1 2 3 4 5

Output

–

cmd

5
1 2 3 4 5

Demonstration

Codeforces Solution-B. Lost Array-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 1 year ago 352 0