Given two array a[] and b[] of size N, the task is to print the count of operations required to make all the elements of array a[i] equal to its minimum element by performing a[i] – b[i] where its always a[i] >= b[i]. If it is not possible then return -1.
Example:
Input: a[] = {5, 7, 10, 5, 15} b[] = {2, 2, 1, 3, 5}
Output: 8
Explanation:
Input array is a[] = 5, 7, 10, 5, 15 and b[] = 2, 2, 1, 3, 5. The minimum from a[] is 5.
Now for a[0] we don’t have to perform any operation since its already 5.
For i = 1, a[1] – b[1] = 7 – 2 = 5. (1 operation)
For i = 2, a[2] – b[2] = 10 – 1 = 9 – 1 = 8 – 1 = 7 – 1 = 6 – 1 = 5 (5 operation)
For i = 3, a[3] = 5
For i = 4, a[4] – b[4] = 15 – 5= 10 – 5 = 5 (2 operation)
The total number of operations required is 8.
Input: a[] = {1, 3, 2} b[] = {2, 3, 2}
Output:-1
Explanation:
It is not possible to convert the array a[] into equal elements.
Approach: To solve the problem mentioned above follow the steps given below:
- Find minimum from array a[]. Initialize a variable ans = -1 that stores resultant subtractions operation.
- Iterate from minimum element of array a[] to 0 and initialize variable curr to 0 that stores the count subtraction to make the array element equal.
- Traverse in the array and check if a[i] is not equal to x which is the minimum element in the first array, then make it equal to minimum else update curr equal to zero.
- Check if curr is not equal to 0 then update ans as curr finally return the ans.
Below is the implementation of above approach:
C++
// C++ program to count the operations// to make all elements of array a[]// equal to its min element// by performing a[i] – b[i]#include <bits/stdc++.h>using namespace std;// Function to convert all Element of// first array equal using second arrayint findMinSub(int a[], int b[], int n){ // Get the minimum from first array int min = INT_MAX; for (int i = 0; i < n; i++) { if (a[i] < min) min = a[i]; } // Variable that stores count of // resultant required subtraction // to Convert all elements equal int ans = -1; for (int x = min; x >= 0; x--) { // Stores the count subtraction to // make the array element // equal for each iteration int curr = 0; // Traverse the array and check if // a[i] is not equal to x then // Make it equal to minimum else // update current equal to zero for (int i = 0; i < n; i++) { if (a[i] != x) { if (b[i] > 0 && (a[i] - x) % b[i] == 0) { curr += (a[i] - x) / b[i]; } else { curr = 0; break; } } } // Check if curr is not equal to // zero then update the answer if (curr != 0) { ans = curr; break; } } return ans;}// Driver codeint main(){ int a[] = { 5, 7, 10, 5, 15 }; int b[] = { 2, 2, 1, 3, 5 }; int n = sizeof(a) / sizeof(a[0]); cout << findMinSub(a, b, n); return 0;} |
Java
// Java program to count the operations // to make all elements of array a[] // equal to its min element // by performing a[i] – b[i] import java.util.*; class GFG{ // Function to convert all element of // first array equal using second array static int findMinSub(int a[], int b[], int n) { // Get the minimum from first array int min = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if (a[i] < min) min = a[i]; } // Variable that stores count of // resultant required subtraction // to Convert all elements equal int ans = -1; for(int x = min; x >= 0; x--) { // Stores the count subtraction // to make the array element // equal for each iteration int curr = 0; // Traverse the array and check // if a[i] is not equal to x then // Make it equal to minimum else // update current equal to zero for(int i = 0; i < n; i++) { if (a[i] != x) { if (b[i] > 0 && (a[i] - x) % b[i] == 0) { curr += (a[i] - x) / b[i]; } else { curr = 0; break; } } } // Check if curr is not equal to // zero then update the answer if (curr != 0) { ans = curr; break; } } return ans; } // Driver code public static void main(String[] args) { int a[] = { 5, 7, 10, 5, 15 }; int b[] = { 2, 2, 1, 3, 5 }; int n = a.length; System.out.print(findMinSub(a, b, n)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to count the operations# to make all elements of array a[]# equal to its min element# by performing a[i] – b[i]# Function to convert all element of# first array equal using second arraydef findMinSub(a, b, n): # Get the minimum from first array min = a[0] for i in range(0, n): if a[i] < min: min = a[i] # Variable that stores count of # resultant required subtraction # to Convert all elements equal ans = -1 for x in range(min, -1, -1): # Stores the count subtraction # to make the array element # equal for each iteration curr = 0 # Traverse the array and check # if a[i] is not equal to x then # Make it equal to minimum else # update current equal to zero for i in range(0, n): if a[i] != x: if (b[i] > 0 and (a[i] - x) % b[i] == 0): curr += (a[i] - x) // b[i] else: curr = 0 break # Check if curr is not equal to # zero then update the answer if curr != 0: ans = curr break return ans# Driver codea = [ 5, 7, 10, 5, 15 ]b = [ 2, 2, 1, 3, 5 ]n = len(a)print(findMinSub(a, b, n))# This code is contributed by jrishabh99 |
C#
// C# program to count the operations // to make all elements of array a[] // equal to its min element // by performing a[i] – b[i] using System; class GFG{ // Function to convert all element of // first array equal using second array static int findMinSub(int []a, int []b, int n) { // Get the minimum from first array int min = Int32.MaxValue; for(int i = 0; i < n; i++) { if (a[i] < min) min = a[i]; } // Variable that stores count of // resultant required subtraction // to Convert all elements equal int ans = -1; for(int x = min; x >= 0; x--) { // Stores the count subtraction // to make the array element // equal for each iteration int curr = 0; // Traverse the array and check // if a[i] is not equal to x then // Make it equal to minimum else // update current equal to zero for(int i = 0; i < n; i++) { if (a[i] != x) { if (b[i] > 0 && (a[i] - x) % b[i] == 0) { curr += (a[i] - x) / b[i]; } else { curr = 0; break; } } } // Check if curr is not equal to // zero then update the answer if (curr != 0) { ans = curr; break; } } return ans; } // Driver code public static void Main() { int []a = { 5, 7, 10, 5, 15 }; int []b = { 2, 2, 1, 3, 5 }; int n = a.Length; Console.Write(findMinSub(a, b, n)); } } // This code is contributed by Code_Mech |
Javascript
<script>// javascript program to count the operations // to make all elements of array a // equal to its min element // by performing a[i] – b[i] // Function to convert all element of // first array equal using second array function findMinSub(a , b , n) { // Get the minimum from first array var min = Number.MAX_VALUE; for (i = 0; i < n; i++) { if (a[i] < min) min = a[i]; } // Variable that stores count of // resultant required subtraction // to Convert all elements equal var ans = -1; for (x = min; x >= 0; x--) { // Stores the count subtraction // to make the array element // equal for each iteration var curr = 0; // Traverse the array and check // if a[i] is not equal to x then // Make it equal to minimum else // update current equal to zero for (i = 0; i < n; i++) { if (a[i] != x) { if (b[i] > 0 && (a[i] - x) % b[i] == 0) { curr += (a[i] - x) / b[i]; } else { curr = 0; break; } } } // Check if curr is not equal to // zero then update the answer if (curr != 0) { ans = curr; break; } } return ans; } // Driver code var a = [ 5, 7, 10, 5, 15 ]; var b = [ 2, 2, 1, 3, 5 ]; var n = a.length; document.write(findMinSub(a, b, n));// This code is contributed by aashish1995</script> |
Output:
8
Time Complexity: O(min*n) // min is the minimum element in the array
Auxiliary Space: O(1)
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!
