Minimum number of operations to convert array A to array B by adding an integer into a subarray
Given two arrays A[] and B[] of length N, the task is to find the minimum number of operations in which the array A can be converted into array B where each operation consists of adding an integer K into a subarray from L to R.
Examples:
Input: A[] = {3, 7, 1, 4, 1, 2}, B[] = {3, 7, 3, 6, 3, 2}
Output: 1
Explanation:
In the above given example only one operation is required to convert from A to B: L = 3, R = 5 and K = 2
Array after the following operation:
Index 0: A[0] = 3, B[0] = 3
Index 1: A[1] = 7, B[1] = 7
Index 2: A[2] = 1 + 2 = 3, B[2] = 3
Index 3: A[3] = 4 + 2 = 6, B[3] = 6
Index 4: A[4] = 1 + 2 = 3, B[4] = 3
Index 5: A[5] = 2, B[5] = 2Input: A[] = {1, 1, 1, 1, 1}, B[] = {1, 2, 1, 3, 1}
Output: 2
Explanation:
In the above given example only one operation is required to convert from A to B –
Operation 1: Add 1 to L = 2 to R = 2
Operation 2: Add 2 to L = 4 to R = 4
Approach: The idea is to count the consecutive elements, in array A, having an equal difference with the corresponding element in array B.
- Find the difference of the corresponding element from the array A and B:
Difference = A[i] - B[i]
- If the difference of the corresponding elements is equal to 0, then continue checking for the next index.
- Otherwise, Increase the index until the difference between consecutive elements is not equal to the previous difference of the consecutive elements
- Increment the count by 1, until all the indexes are iterated having the same difference.
- In the end, return the count as the minimum number of operations.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // minimum number of operations in // which the array A can be converted // to another array B #include <bits/stdc++.h> using namespace std; // Function to find the minimum // number of operations in which // array A can be converted to array B void checkArray( int a[], int b[], int n) { int operations = 0; int i = 0; // Loop to iterate over the array while (i < n) { // if both elements are equal // then move to next element if (a[i] - b[i] == 0) { i++; continue ; } // Calculate the difference // between two elements int diff = a[i] - b[i]; i++; // loop while the next pair of // elements have same difference while (i < n && a[i] - b[i] == diff) { i++; } // Increase the number of // operations by 1 operations++; } // Print the number of // operations required cout << operations << "\n" ; } // Driver Code int main() { int a[] = { 3, 7, 1, 4, 1, 2 }; int b[] = { 3, 7, 3, 6, 3, 2 }; int size = sizeof (a) / sizeof (a[0]); checkArray(a, b, size); return 0; } |
Java
// Java implementation to find the // minimum number of operations in // which the array A can be converted // to another array B class GFG { // Function to find the minimum // number of operations in which // array A can be converted to array B static void checkArray( int a[], int b[], int n) { int operations = 0 ; int i = 0 ; // Loop to iterate over the array while (i < n) { // if both elements are equal // then move to next element if (a[i] - b[i] == 0 ) { i++; continue ; } // Calculate the difference // between two elements int diff = a[i] - b[i]; i++; // loop while the next pair of // elements have same difference while (i < n && a[i] - b[i] == diff) { i++; } // Increase the number of // operations by 1 operations++; } // Print the number of // operations required System.out.println(operations); } // Driver Code public static void main (String[] args) { int a[] = { 3 , 7 , 1 , 4 , 1 , 2 }; int b[] = { 3 , 7 , 3 , 6 , 3 , 2 }; int size = a.length; checkArray(a, b, size); } } // This code is contributed by AnkitRai01 |
C#
// C# implementation to find the // minimum number of operations in // which the array A can be converted // to another array B using System; class GFG { // Function to find the minimum // number of operations in which // array A can be converted to array B static void checkArray( int []a, int []b, int n) { int operations = 0; int i = 0; // Loop to iterate over the array while (i < n) { // if both elements are equal // then move to next element if (a[i] - b[i] == 0) { i++; continue ; } // Calculate the difference // between two elements int diff = a[i] - b[i]; i++; // loop while the next pair of // elements have same difference while (i < n && a[i] - b[i] == diff) { i++; } // Increase the number of // operations by 1 operations++; } // Print the number of // operations required Console.WriteLine(operations); } // Driver Code public static void Main ( string [] args) { int []a = { 3, 7, 1, 4, 1, 2 }; int []b = { 3, 7, 3, 6, 3, 2 }; int size = a.Length; checkArray(a, b, size); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation to find the # minimum number of operations in # which the array A can be converted # to another array B # Function to find the minimum # number of operations in which # array A can be converted to array B def checkArray(a, b, n) : operations = 0 ; i = 0 ; # Loop to iterate over the array while (i < n) : # if both elements are equal # then move to next element if (a[i] - b[i] = = 0 ) : i + = 1 ; continue ; # Calculate the difference # between two elements diff = a[i] - b[i]; i + = 1 ; # loop while the next pair of # elements have same difference while (i < n and a[i] - b[i] = = diff) : i + = 1 ; # Increase the number of # operations by 1 operations + = 1 ; # Print the number of # operations required print (operations); # Driver Code if __name__ = = "__main__" : a = [ 3 , 7 , 1 , 4 , 1 , 2 ]; b = [ 3 , 7 , 3 , 6 , 3 , 2 ]; size = len (a); checkArray(a, b, size); # This code is contributed by AnkitRai01 |
Javascript
<script> // javascript implementation to find the // minimum number of operations in // which the array A can be converted // to another array B // Function to find the minimum // number of operations in which // array A can be converted to array B function checkArray(a , b , n) { var operations = 0; var i = 0; // Loop to iterate over the array while (i < n) { // if both elements are equal // then move to next element if (a[i] - b[i] == 0) { i++; continue ; } // Calculate the difference // between two elements var diff = a[i] - b[i]; i++; // loop while the next pair of // elements have same difference while (i < n && a[i] - b[i] == diff) { i++; } // Increase the number of // operations by 1 operations++; } // Print the number of // operations required document.write(operations); } // Driver Code var a = [ 3, 7, 1, 4, 1, 2 ]; var b = [ 3, 7, 3, 6, 3, 2 ]; var size = a.length; checkArray(a, b, size); // This code contributed by Rajput-Ji </script> |
1
Performance Analysis:
- Time Complexity: As in the above approach, there is only one loop that takes O(N) time in the worst case. Hence, the Time Complexity will be O(N).
- Auxiliary Space Complexity: As in the above approach, there is no extra space used. Hence, the auxiliary space complexity will be O(1).