Given two arrays a[] and b[] of length N consisting of unique elements, the task is to find a number K (K > 0) such that the first array can be converted into the second array by adding K to a selected range [L, R] in the array. If no such number K exists, print N
Examples:
Input: a[] = {3, 7, 1, 4, 0, 2, 2}, b[] = {3, 7, 3, 6, 2, 2, 2}
Output: 2
Explanation:
Array a[] can be converted into Array b[] by adding K = 2 to range [2, 4]Input: a[] = {3, 7, 1, 4, 0, 1, 2}, b[] = {3, 7, 3, 6, 2, 2}
Output: NA
Approach:
- Create a temporary array c[] which contains the difference between the array elements, i.e.,
ci = bi - ai
- Then create a vector pair for all non-zero elements of the array c[n] with their index. Therefore, the vector pair will be as:
vector<c[i], o> where c[i] is a non zero value in c[] and i is the index of c[i]
- If the index value differs by 1 and the difference value is the same, then K = difference value and [L, R] = the index range.
- Hence, the array a[n] can be converted into b[n] by adding K to [a[L], a[R]].
For Example:
- Given
a[n] = [3, 7, 1, 4, 0, 2, 2] b[n] = [3, 7, 3, 6, 2, 2, 2]
- So, upon creating the temporary array c[] and a vector pair:
c[n] = [0, 0, 2, 2, 2, 0, 0]
vector pair = {{2, 2}, {2, 3}, {2, 4}}
- As all the index values (2, 3, 4) in the vector pair differ by 1, so they are consecutive.
- And the value of the difference is the same (2).
- Hence, we can simply add that different value in the first array a[n] in the given indexes [2, 4] to convert it into a second array b[n].
- Hence, the required K value will be 2
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to Check if it is possible to// convert a given array to another array// by adding elements to first arraybool checkconv(int a[], int b[], int n){ int c[n], flag = 0; // Create a temporary array c[] // which contains the difference // of the array elements for (int i = 0; i < n; i++) { c[i] = b[i] - a[i]; } // Create a vector pair for all non zero // elements of array c[n] with their index vector<pair<int, int> > idxs; for (int i = 0; i < n; i++) { if (c[i] != 0) idxs.push_back(make_pair(i, c[i])); } // Check If the index value differs by 1 // and the difference value is same for (int i = 0; i < idxs.size() - 1; i++) { if (idxs[i + 1].first - idxs[i].first != 1 || idxs[i + 1].second != idxs[i].second) { flag = 1; break; } } return !flag;}// Function to calculate the value of Kint diffofarrays(int a[], int b[], int n){ int c[n], ans = 0; for (int i = 0; i < n; i++) { c[i] = b[i] - a[i]; } for (int i = 0; i < n; i++) { if (c[i] != 0) { ans = c[i]; break; } } return ans;}// Driver codeint main(){ int A[] = { 3, 7, 1, 4, 0, 2, 2 }; int B[] = { 3, 7, 3, 6, 2, 2, 2 }; int arr_size = sizeof(A) / sizeof(A[0]); if (checkconv(A, B, arr_size)) { cout << diffofarrays(A, B, arr_size) << endl; } else cout << "NA" << endl; return 0;} |
Java
// Java implementation of above approachimport java.util.*;public class GFG{ static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to Check if it is possible to// convert a given array to another array// by adding elements to first arraystatic boolean checkconv(int a[], int b[], int n){ int []c = new int[n]; int flag = 0; // Create a temporary array c[] // which contains the difference // of the array elements for (int i = 0; i < n; i++) { c[i] = b[i] - a[i]; } // Create a vector pair for all non zero // elements of array c[n] with their index Vector<pair > idxs = new Vector<pair>(); for (int i = 0; i < n; i++) { if (c[i] != 0) idxs.add(new pair(i, c[i])); } // Check If the index value differs by 1 // and the difference value is same for (int i = 0; i < idxs.size() - 1; i++) { if (idxs.get(i + 1).first - idxs.get(i).first != 1 || idxs.get(i + 1).second != idxs.get(i).second) { flag = 1; break; } } return flag == 1 ? false:true;}// Function to calculate the value of Kstatic int diffofarrays(int a[], int b[], int n){ int []c = new int[n]; int ans = 0; for (int i = 0; i < n; i++) { c[i] = b[i] - a[i]; } for (int i = 0; i < n; i++) { if (c[i] != 0) { ans = c[i]; break; } } return ans;}// Driver codepublic static void main(String[] args){ int A[] = { 3, 7, 1, 4, 0, 2, 2 }; int B[] = { 3, 7, 3, 6, 2, 2, 2 }; int arr_size = A.length; if (checkconv(A, B, arr_size)) { System.out.print(diffofarrays(A, B, arr_size) +"\n"); } else System.out.print("NA" +"\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of above approach # Function to Check if it is possible to # convert a given array to another array # by adding elements to first array def checkconv(a, b, n) : c = [0]*n; flag = 0; # Create a temporary array c[] # which contains the difference # of the array elements for i in range(n) : c[i] = b[i] - a[i]; # Create a vector pair for all non zero # elements of array c[n] with their index idxs = []; for i in range(n) : if (c[i] != 0) : idxs.append((i, c[i])); # Check If the index value differs by 1 # and the difference value is same for i in range(len(idxs) - 1) : if (idxs[i + 1][0] - idxs[i][0] != 1 or idxs[i + 1][1] != idxs[i][1]) : flag = 1; break; return not flag; # Function to calculate the value of K def diffofarrays(a, b, n) : c = [0] * n; ans = 0; for i in range(n) : c[i] = b[i] - a[i]; for i in range(n) : if (c[i] != 0) : ans = c[i]; break; return ans; # Driver code if __name__ == "__main__" : A = [ 3, 7, 1, 4, 0, 2, 2 ]; B = [ 3, 7, 3, 6, 2, 2, 2 ]; arr_size = len(A); if (checkconv(A, B, arr_size)) : print(diffofarrays(A, B, arr_size)); else : print("NA"); # This code is contributed by AnkitRai01 |
C#
// C# implementation of above approachusing System;using System.Collections.Generic;class GFG{ class pair { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to Check if it is possible to// convert a given array to another array// by adding elements to first arraystatic bool checkconv(int []a, int []b, int n){ int []c = new int[n]; int flag = 0; // Create a temporary array c[] // which contains the difference // of the array elements for (int i = 0; i < n; i++) { c[i] = b[i] - a[i]; } // Create a vector pair for all non zero // elements of array c[n] with their index List<pair > idxs = new List<pair>(); for (int i = 0; i < n; i++) { if (c[i] != 0) idxs.Add(new pair(i, c[i])); } // Check If the index value differs by 1 // and the difference value is same for (int i = 0; i < idxs.Count - 1; i++) { if (idxs[i + 1].first - idxs[i].first != 1 || idxs[i + 1].second != idxs[i].second) { flag = 1; break; } } return flag == 1 ? false:true;}// Function to calculate the value of Kstatic int diffofarrays(int []a, int []b, int n){ int []c = new int[n]; int ans = 0; for (int i = 0; i < n; i++) { c[i] = b[i] - a[i]; } for (int i = 0; i < n; i++) { if (c[i] != 0) { ans = c[i]; break; } } return ans;}// Driver codepublic static void Main(String[] args){ int []A = { 3, 7, 1, 4, 0, 2, 2 }; int []B = { 3, 7, 3, 6, 2, 2, 2 }; int arr_size = A.Length; if (checkconv(A, B, arr_size)) { Console.Write(diffofarrays(A, B, arr_size) +"\n"); } else Console.Write("NA" +"\n");}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of above approach// Function to Check if it is possible to// convert a given array to another array// by adding elements to first arrayfunction checkconv(a, b, n) { let c = new Array(n); let flag = 0; // Create a temporary array c[] // which contains the difference // of the array elements for (let i = 0; i < n; i++) { c[i] = b[i] - a[i]; } // Create a vector pair for all non zero // elements of array c[n] with their index let idxs = new Array(); for (let i = 0; i < n; i++) { if (c[i] != 0) idxs.push([i, c[i]]); } // Check If the index value differs by 1 // and the difference value is same for (let i = 0; i < idxs.length - 1; i++) { if (idxs[i + 1][0] - idxs[i][0] != 1 || idxs[i + 1][1] != idxs[i][1]) { flag = 1; break; } } return !flag;}// Function to calculate the value of Kfunction diffofarrays(a, b, n) { let c = new Array(n); let ans = 0; for (let i = 0; i < n; i++) { c[i] = b[i] - a[i]; } for (let i = 0; i < n; i++) { if (c[i] != 0) { ans = c[i]; break; } } return ans;}// Driver codelet A = [3, 7, 1, 4, 0, 2, 2];let B = [3, 7, 3, 6, 2, 2, 2];let arr_size = A.length;if (checkconv(A, B, arr_size)) { document.write(diffofarrays(A, B, arr_size) + "<br>");}else document.write("NA" + "<br>");</script> |
Output:
2
Time Complexity: O(n)
Auxiliary Space: O(n), where n is the size of the given 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!
