Вам дан массив a, состоящий из n положительных целых чисел. Существуют ли три различных индекса i, j, k таких, что сумма a[i]+a[j]+a[k] заканчивается цифрой m?

Условие

Вам дан массив a, состоящий из n положительных целых чисел. Существуют ли три различных индекса i, j, k таких, что сумма a[i]+a[j]+a[k] заканчивается цифрой m?

Например, для m = 3

solve([20, 22, 19, 84]) => true // 20 + 84 + 19 = 123 solve([1,2,3]) => false

Ответ

Достаточно последних цифр: сохраним не более трёх чисел для каждого остатка и переберём тройки различных позиций этого сокращённого массива.

Предполагаются положительные безопасные целые JavaScript и m от 0 до 9; по умолчанию m=3, как в примерах.

function solve(a, m = 3) {
  if (!Number.isInteger(m) || m < 0 || m > 9) throw new RangeError('m');
  const counts = Array(10).fill(0);
  const digits = [];
  for (const x of a) {
    if (!Number.isSafeInteger(x) || x <= 0) throw new TypeError('a');
    const d = x % 10;
    if (counts[d] < 3) { counts[d]++; digits.push(d); }
  }
  for (let i = 0; i < digits.length; i++)
    for (let j = i + 1; j < digits.length; j++)
      for (let k = j + 1; k < digits.length; k++)
        if ((digits[i] + digits[j] + digits[k]) % 10 === m) return true;
  return false;
}

В тройке нельзя использовать больше трёх представителей одного остатка, поэтому остальные не нужны. После O(n) прохода перебирается не более 30 элементов; дополнительная память O(1).