Prefix
Prefix in computer science is called the beginning of a line. The string's own prefix is not equal in length to the string itself.
The beginning of this sequence will be called the prefix of the sequence. The own prefix of the sequence will be all its subsequences starting from the first element and not equal in length to the sequence itself.
Task
You are given a sequence of N natural numbers. Find the maximum length of its own prefix for a sequence whose sum of all elements of the prefix has the same remainder when divided by K, which is the sum of all elements of the given sequence.
Since all numbers are natural, when reading the next number, the sum of all the numbers read will always increase. Therefore, the desired maximum prefix is the last prefix that satisfies the condition.
There are two ways to find the required prefix.
1 way. Long
1) Go through the array, find the sum of all elements.
2) Go through the array a second time and find the last prefix that satisfies the condition.
The disadvantage of this method is that it is necessary to go through the array twice.
2 way. Using an array of residuals
An array of residuals for the number K will be called an array containing K elements, i-th ;whose element contains the length (sum of elements, etc.) sequence, the sum of whose elements, gives the remainder of division by K value < code>i (0<= i <= K-1). In other words, i takes on a value equal to all possible remainders that can result from when divided by K.
Algorithm
1) Create an array of K elements, where the number of each element will correspond to a certain remainder after dividing by К sums of elements of the current prefix (array of residuals).
2) Considering the next & nbsp; number, we get a new prefix. Let's determine its sum and write its length into the array element with index [s % K], where s is the sum of prefix elements.
3) By reading the last element of the sequence and adding it to the sum of the last prefix, we will find the sum of all elements of the sequence.
4) The answer will be an element of the remainder array with an index equal to the remainder of dividing the sum of all elements of the sequence by the number K.
Try to implement the second method yourself.