Подсчитайте делители или кратные числа, присутствующие в массиве для каждого элемента.

Опубликовано: 21 Сентября, 2022

Учитывая массив A[] с N целыми числами, для каждого целого числа A[i] в массиве задача состоит в том, чтобы найти такое количество целых чисел A[j] (j != i) в массиве, что A[i] % A[j] = 0 или A[j] % A[i] = 0 .

Примеры:

Input: A = {2, 3, 4, 5, 6}
Output: 2 1 1 0 2
Explanation: 
For i=0, the valid indices are 2 and 4 as 4%2 = 0 and 6%2 = 0.
For i=1, the only valid index is 4 as 6%3 = 0.
For i=2, the only valid index is 0 as 4%2 = 0.
For i=3, there are no valid indices.
For i=0, the valid indices are 0 and 1 as 6%2 = 0 and 6%3 = 0.

Input: A = {6, 6, 6, 6, 6}
Output: 4 4 4 4 4

Подход: Данную проблему можно решить, используя наблюдение, что количество целых чисел, удовлетворяющих данному условию, можно разделить на два случая. Предположим, что текущее целое число равно P , а Q — целое число, удовлетворяющее заданным условиям.

  • Случай 1 , где Q кратно P . Следовательно, количество целых чисел в данном массиве, которые делятся на P, является требуемым ответом. С этим случаем можно справиться, используя простую модификацию Решета Эратосфена, которая обсуждается здесь.
  • Случай 2 , где P кратно Q . Следовательно, количество целых чисел в заданном массиве, на которые Q делит P, является требуемым ответом. С этим случаем можно справиться так же, используя сито, как и с 1-м случаем.

Итак, требуемый ответ для любого целого числа — это сумма результирующих целых чисел случаев 1 и 2 . В случаях, когда P = Q , и вариант 1 , и вариант 2 представляют одно и то же значение и должны рассматриваться только один раз.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log N)
Вспомогательное пространство: O(MAX), где MAX представляет максимальное целое число в данном массиве.

РЕКОМЕНДУЕМЫЕ СТАТЬИ