Maximice los 0 en el Array dado después de reemplazar cada elemento A[i] con (A[i]*D + B[i])

Dados dos arreglos A[] y B[] que consisten en N enteros, la tarea es encontrar el número máximo de 0 en el arreglo A[] que se puede hacer después de reemplazar cada elemento del arreglo A[i] con A[i]* D + B[i] eligiendo cualquier valor de D .

Ejemplos:

Entrada: A[] = {1, 2, -1}, B[] = {-6, -12, 6}
Salida: 3
Explicación:
Considere el valor de D como 6. Ahora la array A[] se modifica a { 1*6 – 6, 2*6 – 12, -1*6 + 6} = {0, 0, 0}.
Por lo tanto, el valor de D como 6 hace que todos los elementos del arreglo A[i] sean 0. Por lo tanto, imprima 3.

Entrada: A[] = {0, 7, 2}, B[] = {0, 5, -4}
Salida: 2

Enfoque: el problema dado se puede resolver calculando el valor de D requerido para hacer que cada elemento de array A[i] sea 0 y almacenar los valores en un Map . Siga los pasos a continuación para resolver el problema:

• Inicialice un Mapa, digamos M y dos enteros, digamos cnt y ans como 0 .
• Iterar sobre el rango [0, N – 1] usando la variable i y realizar los siguientes pasos:
  • Inicialice dos enteros num como -B[i] y den como A[i] .
  • Si el valor de den no es igual a 0 , divida ambos valores, num y den , por el MCD de num y den .
  • Si el valor de num no es mayor que 0 , multiplique tanto num como den por -1 .
  • Si los valores de den y num son ambos iguales a 0 , entonces incremente el valor de cnt en 1 y si el valor de den no es igual a 0 entonces incremente el valor de mp[{num, den}] en 1 y actualice el valor de ans como max(ans, mp[{num, den}] .
• Después de completar los pasos anteriores, imprima el valor de ans + cnt como el posible valor de D que maximiza el conteo de 0 en la array dada A[i] después de realizar las operaciones dadas.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum number
// of 0s in the array A[] after changing
// the array element to A[i]*D + B[i]
void maxZeroes(vector<int>& A,
               vector<int>& B)
{
    // Stores the frequency of fractions
    // needed to make each element 0
    map<pair<int, int>, int> mp;
    int N = A.size();
 
    // Stores the maximum number of 0
    int ans = 0;
    int cnt = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Find the numerator and
        // the denominator
        int num = -B[i];
        int den = A[i];
 
        int gc = __gcd(num, den);
 
        // Check if den is not equal
        // to 0
        if (den != 0) {
 
            // Divide num and den
            // by their gcd
            num /= gc;
            den /= gc;
        }
 
        // Check if num is not
        // greater than 0
        if (num <= 0) {
            num *= -1;
            den *= -1;
        }
 
        // Check if both num and den
        // are equal to 0
        if (den == 0 and num == 0)
            cnt++;
 
        if (den != 0) {
 
            // Increment the value of
            // {num, den} in the map
            mp[{ num, den }]++;
 
            // Update the value of ans
            ans = max(mp[{ num, den }], ans);
        }
    }
 
    // Print the value of ans+cnt
    cout << ans + cnt << endl;
}
 
// Driver Code
int main()
{
    vector<int> A = { 1, 2, -1 };
    vector<int> B = { -6, -12, 6 };
    maxZeroes(A, B);
 
    return 0;
}

# Python program for the above approach
from math import gcd
 
# Function to find the maximum number
# of 0s in the array A[] after changing
# the array element to A[i]*D + B[i]
def maxZeroes(A,B):
    # Stores the frequency of fractions
    # needed to make each element 0
    mp = {}
    N = len(A)
 
    # Stores the maximum number of 0
    ans = 0
    cnt = 0
 
    # Traverse the array
    for i in range(N):
        # Find the numerator and
        # the denominator
        num = -B[i]
        den = A[i]
 
        gc = gcd(num, den)
 
        # Check if den is not equal
        # to 0
        if (den != 0):
 
            # Divide num and den
            # by their gcd
            num //= gc
            den //= gc
 
        # Check if num is not
        # greater than 0
        if (num <= 0):
            num *= -1
            den *= -1
 
        # Check if both num and den
        # are equal to 0
        if (den == 0 and num == 0):
            cnt+=1
 
        if (den != 0):
 
            # Increment the value of
            # {num, den} in the map
            mp[(num, den)] = mp.get((num, den),0)+1
 
            # Update the value of ans
            ans = max(mp[(num, den )], ans)
 
    # Print the value of ans+cnt
    print (ans + cnt)
 
# Driver Code
if __name__ == '__main__':
    A = [1, 2, -1]
    B = [-6, -12, 6]
    maxZeroes(A, B)
 
# This code is contributed by mohit kumar 29.

<script>
 
// JavaScript program for the above approach
 
 
function __gcd(a, b) {
    if (b == 0)
    return a;
    return __gcd(b, a % b);
 }
  
 
// Function to find the maximum number
// of 0s in the array A[] after changing
// the array element to A[i]*D + B[i]
function maxZeroes(A, B) {
    // Stores the frequency of fractions
    // needed to make each element 0
    let mp = new Map();
    let N = A.length;
 
    // Stores the maximum number of 0
    let ans = 0;
    let cnt = 0;
 
    // Traverse the array
    for (let i = 0; i < N; i++) {
 
        // Find the numerator and
        // the denominator
        let num = -B[i];
        let den = A[i];
 
        let gc = __gcd(num, den);
 
        // Check if den is not equal
        // to 0
        if (den != 0) {
 
            // Divide num and den
            // by their gcd
            num /= gc;
            den /= gc;
        }
 
        // Check if num is not
        // greater than 0
        if (num <= 0) {
            num *= -1;
            den *= -1;
        }
 
        // Check if both num and den
        // are equal to 0
        if (den == 0 && num == 0)
            cnt++;
 
        if (den != 0) {
 
            // Increment the value of
            // {num, den} in the map
            if (mp.has(`${num},${den}`)) {
                mp.set(`${num},${den}`, mp.get(`${num},${den}`) + 1)
            } else {
                mp.set(`${num},${den}`, 1)
            }
 
            // Update the value of ans
            ans = Math.max(mp.get(`${num},${den}`), ans);
        }
    }
 
     // Print the value of ans+cnt
    document.write(ans + cnt + "<br>");
}
 
// Driver Code
 
let A = [1, 2, -1];
let B = [-6, -12, 6];
maxZeroes(A, B);
 
</script>

3

Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)