Given two arrays A[] and B[] consisting of N integers, the task is to find the maximum number of 0s in the array A[] that can be made after replacing each array element A[i] with A[i]*D + B[i] by choosing any value of D.
Examples:
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
Approach: The given problem can be solved by calculating the value of D required to make each array element A[i] to 0 and store the values in a Map. Follow the steps below to solve the problem:
- Initialize a Map, say M and two integers, say cnt and ans as 0.
- Iterate over the range [0, N – 1] using the variable i and perform the following steps:
- Initialize two integers num as -B[i] and den as A[i].
- If the value of den is not equal to 0 then divide both the values num and den by the GCD of num and den.
- If the value of num is not greater than 0, then multiply both num and den by -1.
- If the values of den and num are both equal to 0, then increment the value of cnt by 1 and if the value of den is not equal to 0 then increment the value of mp[{num, den}] by 1 and update the value of ans as max(ans, mp[{num, den}].
- After completing the above steps, print the value of ans + cnt as the possible value of D that maximize the count of 0s in the given array A[i] after performing the given operations.
Below is the implementation of the above approach:
C++
// 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 Codeint main(){ vector<int> A = { 1, 2, -1 }; vector<int> B = { -6, -12, 6 }; maxZeroes(A, B); return 0;} |
Python3
# Python program for the above approachfrom 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 Codeif __name__ == '__main__': A = [1, 2, -1] B = [-6, -12, 6] maxZeroes(A, B)# This code is contributed by mohit kumar 29. |
Javascript
<script>// JavaScript program for the above approachfunction __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 Codelet A = [1, 2, -1];let B = [-6, -12, 6];maxZeroes(A, B);</script> |
Java
import java.util.*;public class GFG { // Function to find the maximum number // of 0s in the array A[] after changing // the array element to A[i]*D + B[i] public static void maxZeroes(List<Integer> A, List<Integer> B) { // Stores the frequency of fractions // needed to make each element 0 Map<Pair<Integer, Integer>, Integer> mp = new HashMap<>(); 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.get(i); int den = A.get(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 && num == 0) cnt++; if (den != 0) { // Increment the value of // {num, den} in the map Pair<Integer, Integer> currentPair = Pair.of(num, den); if(currentPair != null){ mp.put(currentPair, mp.getOrDefault(currentPair, 0) + 1); } // Update the value of ans if(mp.containsKey(currentPair)){ ans = Math.max(mp.get(currentPair), ans); } } } // Print the value of ans+cnt System.out.println(ans + cnt); } // Find the gcd of two numbers public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Driver code public static void main(String[] args) { List<Integer> A = Arrays.asList(1,2,-1); List<Integer> B = Arrays.asList(-6,-12,6); maxZeroes(A, B); }}// custom Pair classclass Pair<T, U> { T first; U second; public Pair(T first, U second) { this.first = first; this.second = second; } public T getFirst() { return first; } public U getSecond() { return second; } public static <T, U> Pair<T, U> of(T first, U second) { return new Pair<T, U>(first, second); } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Pair<?, ?> pair = (Pair<?, ?>) o; return Objects.equals(first, pair.first) && Objects.equals(second, pair.second); } @Override public int hashCode() { return Objects.hash(first, second); }} |
C#
using System;using System.Collections.Generic;public class Program {// Function to find the maximum number of 0s// in the array A[] after changing the array// element to A[i]*D + B[i] public static void MaxZeroes(int[] A, int[] B) {// Stores the frequency of fractions// needed to make each element 0 Dictionary<(int, int), int> mp = new Dictionary<(int, int), int>(); int N = A.Length;// 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 && num == 0) { cnt++; } if (den != 0) { // Increment the value of {num, den} in the map if (mp.ContainsKey((num, den))) { mp[(num, den)]++; } else { mp.Add((num, den), 1); } // Update the value of ans ans = Math.Max(mp[(num, den)], ans); } } // Print the value of ans+cnt Console.WriteLine(ans + cnt); }// Function to find the gcd of two numbers public static int Gcd(int a, int b) { if (b == 0) { return a; } return Gcd(b, a % b); }// Driver Code public static void Main() { int[] A = new int[] { 1, 2, -1 }; int[] B = new int[] { -6, -12, 6 }; MaxZeroes(A, B); }} |
Output:
3
Time Complexity: O(N log N)
Auxiliary Space: O(N)
