Префикс
Префиксом в информатике принято называть начало строки. Собственный префикc строки не равен по длине самой строке.
Префиксом последовательности будем называть начало этой последовательности. Собственным префиксом последовательности будут являться все ее подпоследовательности, начинающиеся с первого элемента и не равные по длине самой последовательности.
Задача
Дана последовательность из N натуральных чисел. Найдите максимальную длину собственного префикса последовательность, у которого сумма всех элементов префикса имеет тот же остаток при делении на K, что и сумма всех элементов данной последовательности.
Так как все числа натуральные, то при считывании очередного числа, сумма всех прочитанных чисел будет всегда увеличиваться. Следовательно, нужный максимальный префикс - это последний префикс удовлетворяющий условию.
Найти нужный префикс можно двумя способами.
1 способ. Долгий
1) Пройтись по массиву, найти сумму всех элементов.
2) Пройтись по массиву второй раз и найти последний префикс, удовлетворяющий условию.
Минус данного способа заключается в том, что необходимо дважды проходить по массиву.
2 способ. Используем массив остатков
Массивом остатков для числа K будем называть массив, содержащий в себе K элементов, i-ый элемент которого содержит длину (сумму элементов и пр.) последовательности, сумма элементов которой, дает в остатке от деления на K значение i (0<= i <= K-1). Другими словами i принимает значение равное всем возможным остаткам, которые могут получиться при делении на K.
Алгоритм
1) Завести массив из К элементов, где номер каждого элемента будет соответствовать определенному остатку от деления на К суммы элементов текущего префикса (массив остатков).
2) Считав очередное число, получим новый префикс. Определим его сумму и запишем его длину в элемент массива с индексом [s % K], где s - сумма элементов префикса.
3) Считав последний элемент последовательности и добавив его к сумме последнего префикса, мы найдем сумму всех элементов последовательности.
4) Ответом будет являться элемент массива остатков с индексом равным остатку от деления суммы всех элементов последовательности на число K.
Попробуйте реализовать второй способ самостоятельно.