Максимизируйте 0 в заданном массиве после замены каждого элемента A[i] на (A[i]*D + B[i])

Даны два массива A[] и B[] , состоящие из N целых чисел, задача состоит в том, чтобы найти максимальное количество нулей в массиве A[] , которое можно получить после замены каждого элемента массива A[i] на A[i]* D + B[i] , выбрав любое значение D .

Примеры:

Input: A[] = {1, 2, -1}, B[] = {-6, -12, 6}
Output: 3
Explanation:
Consider the value of D as 6. Now the array A[] modifies to {1*6 – 6, 2*6 – 12, -1*6 + 6} = {0, 0, 0}.
Therefore, the value of D as 6 makes all the array elements A[i] to 0. Hence, print 3.

Input: A[] = {0, 7, 2}, B[] = {0, 5, -4}
Output: 2

Подход: данная проблема может быть решена путем вычисления значения D , необходимого для приведения каждого элемента массива A[i] к 0 , и сохранения значений на карте. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте карту, скажем, M и два целых числа, скажем, cnt и ans как 0 .
• Переберите диапазон [0, N – 1], используя переменную i , и выполните следующие шаги:
  • Инициализируйте два целых числа num как -B[i] и den как A[i] .
  • Если значение den не равно 0 , разделите оба значения num и den на GCDof num и den .
  • Если значение num не больше 0 , то умножьте и num , и den на -1 .
  • Если значения den и num равны 0 , то увеличьте значение cnt на 1 , а если значение den не равно 0 , увеличьте значение mp[{num, den}] на 1 и обновите значение ans как max(ans, mp[{num, den}] .
• После выполнения вышеуказанных шагов выведите значение ans + cnt как возможное значение D , которое максимизирует количество нулей в заданном массиве A[i] после выполнения данных операций.

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

Временная сложность: O (N log N)
Вспомогательное пространство: O(N)