Count of operations to make all elements of array a[] equal to its min element by performing a[i] – b[i]
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 array int 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 code int 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 array def 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 code a = [ 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> |
8
Time Complexity: O(min*n) // min is the minimum element in the array
Auxiliary Space: O(1)
Contact Us