Find a multiple (Editorial)

Find a multiple#5621

Let $d_{1}, d_{2}, ..., d_{n}$ d_1, d_2, ..., d_n be the input numbers. Consider all their partial sums:

s_{i} = d_{1} + ... + d_{i}

s_i = d_1 + ... + d_i

Since there are exactly $n$ partial sums, among all the values of $s_{i} m o d n$ s_i~mod~n there must be either two that are equal or at least one that is zero.

If for some indices $a - 1 < b$ a - 1 < b it holds that

s_{a - 1} m o d n = s_{b} m o d n,

s_{a-1}~mod~n = s_b~mod~n,

then the sum $d_{a} + ... + d_{b}$ d_a + ... + d_b is divisible by $n$ .

Therefore, the sequence of numbers $d_{a}, d_{a + 1}, ..., d_{b}$ d_a, d_{a + 1}, ..., d_b is a valid solution.

If there exists an $i$ such that $s_{i} m o d n = 0$ s_i~mod~n = 0, then the sequence $d_{1}, d_{2}, ..., d_{i}$ d_1, d_2, ..., d_i forms a valid solution..

Example

Let’s consider the given example. Compute all the partial sums:

There are several valid subsets. For example:

since $s_{1} = s_{3}$ s_1 = s_3, then $d_{2} + d_{3} = 5$ d_2 + d_3 = 5 is divisible by $5$ .
since $s_{1} = s_{5}$ s_1 = s_5, then $d_{2} + d_{3} + d_{4} + d_{5} = 10$ d_2 + d_3 + d_4 + d_5 = 10 is divisible by $5$ .
since $s_{3} = s_{5}$ s_3 = s_5, then $d_{4} + d_{5} = 5$ d_4 + d_5 = 5 is divisible by $5$ .
since $s_{4} = 0$ s_4 = 0, then $d_{1} + d_{2} + d_{3} + d_{4} = 10$ d_1 + d_2 + d_3 + d_4 = 10 is divisible by $5$ .

Algorithm implementation

We'll store the input numbers in an array $d$ . The array $r$ will be used to record partial sums: $s = d_{1} + ... + d_{i}$ s = d_1 + ... + d_i, then assign $r [s] = i$ r[s] = i.

#define MAX 10100
int d[MAX], r[MAX];

The desired set of numbers whose sum is divisible by $n$ , will be $d_{a}, d_{a + 1}, ..., d_{b}$ d_a, d_{a+1}, ..., d_b. Print their count $b - a + 1$ b - a + 1, followed by the numbers themselves — one per line.

void print(int a, int b)
{
  printf("%d\n",b - a + 1);
  for(int i = a; i <= b; i++)
    printf("%d\n",d[i]);
}

The main part of the program. Initialize the array $r$ with the value $- 1$ and set $r [0] = 0$ r[0] = 0 to handle the case when the sum of the first $i$ numbers is divisible by $n$ .

memset(r,-1,sizeof(r)); r[0] = 0;

Read the number of elements $n$ .

scanf("%d",&n);

Compute the partial sums modulo $n$ in the variable $s u m$ .

sum = 0;
for (i = 1; i <= n; i++)
{
  scanf("%d", &d[i]);
  sum = (sum + d[i]) % n;

If a partial sum $s u m$ occurs again, print the desired set of numbers:

d_{r [s u m] + 1}, d_{r [s u m] + 2}, ..., d_{i}

d_{r[sum] + 1}, d_{r[sum] + 2}, ..., d_i

  if (r[sum] != -1)
  {
    print(r[sum] + 1, i);
    break;
  }

$r [s u m]$ stores the first index $i$ where the partial sum $d_{1} + ... + d_{i}$ d_1 + ... + d_i produced the remainder $s u m$ when divided by $n$ .

  else r[sum] = i;
}