Дан массив натуральных чисел. Найти сумму элементов, кратных числу k.

Нужно просто просуммировать те элементы массива, которые делятся на $k$ без остатка.

Опишу пошаговый алгоритм.

1. Дано:

   • массив натуральных чисел $a_1, a_2, \dots, a_n$;

   • натуральное число $k$.

2. Вводим переменную для суммы, например sum, и инициализируем её нулём:

   text
   Копировать код
   sum = 0
   

3. Проходим по всем элементам массива по очереди:

   • для каждого элемента $a_i$ проверяем, делится ли он на $k$ без остатка:

     $$a_i \bmod k = 0$$

   • если делится, прибавляем его к сумме:

     text
     Копировать код
     если a[i] % k == 0:
         sum = sum + a[i]
     

4. После обхода всего массива в переменной sum будет находиться искомая сумма всех элементов, кратных $k$.

5. Если в массиве нет ни одного элемента, кратного $k$, то сумма останется равной 0.

Пример на небольшом массиве:

• Массив: $[3, 5, 6, 8, 9]$

• $k = 3$

Проверяем по очереди:

• 3 % 3 = 0 → прибавляем: sum = 3

• 5 % 3 ≠ 0 → не прибавляем

• 6 % 3 = 0 → sum = 3 + 6 = 9

• 8 % 3 ≠ 0 → пропускаем

• 9 % 3 = 0 → sum = 9 + 9 = 18

Ответ: сумма элементов массива, кратных 3, равна 18.

С точки зрения сложности алгоритма:

• по времени — $O(n)$, так как делаем один проход по массиву;

• по памяти — $O(1)$, т.к. используем только одну дополнительную переменную для суммы.