Алгоритм для поиска двух чисел разность которых по модулю будет кратна числу m
Есть N натуральных чисел, нужно найти такие два числа, у которых разница по модулю будет кратна числу m.
Подскажите, пожалуйста алгоритм для решения этой задачи. Мне ничего лучше полного перебора в голову не приходит. Хотя возможно стоит отталкиваться от остатков.
Ответы (1 шт):
Автор решения: Qwertiy
→ Ссылка
Вот. А если надо только количество способов, то вместо индексов можно хранить количество.
var a = [2,3,5,6,7,5]
var m = 10
var i = Array(m).fill().map(() => [])
for (var q=0; q<a.length; ++q) {
i[a[q] % m].push(q)
}
for (var q=0; q+q<=m; ++q) {
if (i[q].length && i[m-q].length) {
if (m-q !== q) {
console.log(`${q}+${m-q}: One of [${i[q]}] and one of [${i[m-q]}]`)
} else if (i[q].length >= 2) {
console.log(`${q}+${q}: Any two of [${i[q]}]`)
}
}
}