Given two arrays of N integers. Consider an array C, where the i-th integer will be d*a[i] + b[i] where d is any arbitrary real number. The task is to print d such that array C has maximum number of zeros and also print the number of zeros.
Examples:
Input: a[] = {1, 2, 3, 4, 5}, b[] = {2, 4, 7, 11, 3}
Output:
Value of d is: -2
The number of zeros in array C is: 2
If we choose d as -2 then we get two zeros in the array C which is the maximum possible.Input: a[] = {13, 37, 39} b[] = {1, 2, 3}
Output:
Value of d is: -0.0769231
The number of zeros in array C is: 2
The following steps can be followed to solve the above problem:
- The equation can be rewritten as d = -b[i]/a[i]
- Use hash-table to count the maximum number of occurrence of any real number to get the value of d.
- Number of zeros will be the maximum count + (number of pairs a[i] and b[i] where both are 0).
Below is the implementation of the above approach:
C++
// C++ program to implement the above// approach#include <bits/stdc++.h>using namespace std;// Function to find the value of d// and find the number of zeros in the arrayvoid findDandZeros(int a[], int b[], int n){ // Hash table unordered_map<long double, int> mpp; int count = 0; // Iterate for i-th element for (int i = 0; i < n; i++) { // If both are not 0 if (b[i] != 0 && a[i] != 0) { long double val = (long double)(-1.0 * b[i]) / (long double)(a[i]); mpp[val] += 1; } // If both are 0 else if (b[i] == 0 && a[i] == 0) count += 1; } // Find max occurring d int maxi = 0; for (auto it : mpp) { maxi = max(it.second, maxi); } // Print the d which occurs max times for (auto it : mpp) { if (it.second == maxi) { cout << "Value of d is: " << it.first << endl; break; } } // Print the number of zeros cout << "The number of zeros in array C is: " << maxi + count;}// Driver codeint main(){ int a[] = { 13, 37, 39 }; int b[] = {1, 2, 3}; int n = sizeof(a) / sizeof(a[0]); findDandZeros(a, b, n); return 0;} |
Java
// Java program to implement the above // approach import java.util.*;class neveropen { // Function to find the value of d // and find the number of zeros in the array public static void findDandZeroes(int[] a, int[] b, int n) { // Hash table HashMap<Double, Integer> mpp = new HashMap<>(); int count = 0; // Iterate for i-th element for (int i = 0; i < n; i++) { // If both are not 0 if (b[i] != 0 && a[i] != 0) { double val = (double) (-1.0 * b[i]) / (double) (a[i]); if (mpp.get(val) != null) { int x = mpp.get(val); mpp.put(val, ++x); } else mpp.put(val, 1); } // If both are 0 else if (b[i] == 0 && a[i] == 0) count += 1; } // Find max occurring d int maxi = 0; for (HashMap.Entry<Double, Integer> entry : mpp.entrySet()) { maxi = Math.max(entry.getValue(), maxi); } // Print the d which occurs max times for (HashMap.Entry<Double, Integer> entry : mpp.entrySet()) { if (entry.getValue() == maxi) { System.out.println("Value of d is: " + entry.getKey()); break; } } // Print the number of zeros System.out.println("The number of zeros in array C is: " + (maxi + count)); } // Driver Code public static void main(String[] args) { int[] a = { 13, 37, 39 }; int[] b = { 1, 2, 3 }; int n = a.length; findDandZeroes(a, b, n); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 program to implement the # above approach # Function to find the value of d and # find the number of zeros in the array def findDandZeros(a, b, n) : # Hash table mpp = {}; count = 0; # Iterate for i-th element for i in range(n) : # If both are not 0 if (b[i] != 0 and a[i] != 0) : val = (-1.0 * b[i]) / a[i]; if val not in mpp : mpp[val] = 0; mpp[val] += 1; # If both are 0 elif (b[i] == 0 and a[i] == 0) : count += 1; # Find max occurring d maxi = 0; for item in mpp : maxi = max(mpp[item], maxi); # Print the d which occurs max times for keys, values in mpp.items() : if (values == maxi) : print("Value of d is:", keys); break; # Print the number of zeros print("The number of zeros in array C is:", maxi + count); # Driver code if __name__ == "__main__" : a = [ 13, 37, 39 ]; b = [ 1, 2, 3 ]; n = len(a); findDandZeros(a, b, n); # This code is contributed by Ryuga |
C#
// C# program to implement the above // approach using System;using System.Collections.Generic; class GFG { // Function to find the value of d // and find the number of zeros in the array public static void findDandZeroes(int[] a, int[] b, int n) { // Hash table Dictionary<double, int> mpp = new Dictionary<double, int>(); int count = 0; // Iterate for i-th element for (int i = 0; i < n; i++) { // If both are not 0 if (b[i] != 0 && a[i] != 0) { double val = (double)(-1.0 * b[i]) / (double)(a[i]); if (mpp.ContainsKey(val)) { mpp[val] = ++mpp[val]; } else mpp.Add(val, 1); } // If both are 0 else if (b[i] == 0 && a[i] == 0) count += 1; } // Find max occurring d int maxi = 0; foreach(KeyValuePair<double, int> entry in mpp) { maxi = Math.Max(entry.Value, maxi); } // Print the d which occurs max times foreach(KeyValuePair<double, int> entry in mpp) { if (entry.Value == maxi) { Console.WriteLine("Value of d is: " + entry.Key); break; } } // Print the number of zeros Console.WriteLine("The number of zeros in array C is: " + (maxi + count)); } // Driver Code public static void Main(String[] args) { int[] a = { 13, 37, 39 }; int[] b = { 1, 2, 3 }; int n = a.Length; findDandZeroes(a, b, n); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to implement the above// approach// Function to find the value of d// and find the number of zeros in the arrayfunction findDandZeros(a, b, n){ // Hash table var mpp = new Map(); var count = 0; // Iterate for i-th element for (var i = 0; i < n; i++) { // If both are not 0 if (b[i] != 0 && a[i] != 0) { var val = (-1.0 * b[i]) / (a[i]); if(mpp.has(val)) mpp.set(val, mpp.get(val)+1) else mpp.set(val, 1) } // If both are 0 else if (b[i] == 0 && a[i] == 0) count += 1; } // Find max occurring d var maxi = 0; mpp.forEach((value, key) => { maxi = Math.max(value, maxi); }); // Print the d which occurs max times mpp.forEach((value, key) => { if (value == maxi) { document.write( "Value of d is: " + key + "<br>"); } }); // Print the number of zeros document.write( "The number of zeros in array C is: " + (maxi + count));}// Driver codevar a = [13, 37, 39];var b = [1, 2, 3];var n = a.length;findDandZeros(a, b, n);// This code is contributed by rutvik_56.</script> |
Output
Value of d is: -0.0769231 The number of zeros in array C is: 2
Time Complexity: O(N), as we are using a loop to traverse N times and map operations will take constant time as we are using a unordered map. Where N is the number of elements in the array.
Auxiliary Space: O(N), as we are using extra space for the map. Where N is the number of elements in the array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
