Given two arrays arr[] and brr[] consisting of N and M positive integers respectively, the task is to find all the elements from the array brr[] which are equal to the concatenation of any two elements from the array arr[]. If no such element exists, then print “-1”.
Examples:
Input: arr[] = {2, 34, 4, 5}, brr[] = {26, 24, 345, 4, 22}
Output: 24 345 22
Explanation:
The elements from the array brr[] which are concatenation of any two elements from the array arr[] are:
- 24 is concatenation of 2 and 4.
- 345 is concatenation of 34 and 5.
- 22 is concatenation of 2 and 2.
Input: arr[] = {1, 2, 3}, brr[] = {1, 23}
Output: 23
Naive Approach: The simplest approach to solve the problem is to generate all possible pairs from the given array and check if the concatenation of pairs of elements from the array arr[] is present in the array brr[] or not. If found to be true, then print the concatenated number formed.
Time Complexity: O(M * N2)
Auxiliary Space: O(N2)
Efficient Approach: The above approach can be optimized by checking for each element in the array brr[], whether brr[i] can be divided into 2 parts left and right such that both the parts exists in the array arr[].
Consider a number, b[i] = 2365
All possible combinations of left and right are:
Left Right
2 365
23 65
236 5
Follow the steps below to solve the problem:
- Initialize a HashMap M and store all elements present in the array arr[].
- Traverse the array brr[] and perform the following steps:
- Generate all possible combinations of left and right parts, such that their concatenation results to brr[i].
- If both the left and the right parts are present in Map M in one of the above combinations, then print the value of brr[i]. Otherwise, continue to the next iteration.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find elements present in// the array b[] which are concatenation// of any pair of elements in the array a[]void findConcatenatedNumbers(vector<int> a, vector<int> b){ // Stores if there doesn't any such // element in the array brr[] bool ans = true; // Stored the size of both the arrays int n1 = a.size(); int n2 = b.size(); // Store the presence of an element // of array a[] unordered_map<int, int> cnt; // Traverse the array a[] for (int i = 0; i < n1; i++) { cnt[a[i]] = 1; } // Traverse the array b[] for (int i = 0; i < n2; i++) { int left = b[i]; int right = 0; int mul = 1; // Traverse over all possible // concatenations of b[i] while (left > 9) { // Update right and left parts right += (left % 10) * mul; left /= 10; mul *= 10; // Check if both left and right // parts are present in a[] if (cnt[left] == 1 && cnt[right] == 1) { ans = false; cout << b[i] << " "; } } } if (ans) cout << "-1";}// Driver Codeint main(){ vector<int> a = { 2, 34, 4, 5 }; vector<int> b = { 26, 24, 345, 4, 22 }; findConcatenatedNumbers(a, b); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{ // Function to find elements present in // the array b[] which are concatenation // of any pair of elements in the array a[] static void findConcatenatedNumbers(int[] a, int[] b) { // Stores if there doesn't any such // element in the array brr[] boolean ans = true; // Stored the size of both the arrays int n1 = a.length; int n2 = b.length; // Store the presence of an element // of array a[] int cnt[] = new int[100000]; // Traverse the array for (int i = 0; i < n1; i++) { cnt[a[i]] = 1; } // Traverse the array b[] for (int i = 0; i < n2; i++) { int left = b[i]; int right = 0; int mul = 1; // Traverse over all possible // concatenations of b[i] while (left > 9) { // Update right and left parts right += (left % 10) * mul; left /= 10; mul *= 10; // Check if both left and right // parts are present in a[] if (cnt[left] == 1 && cnt[right] == 1) { ans = false; System.out.print(b[i] + " "); } } } if (ans) System.out.print("-1"); } // Driver code public static void main(String[] args) { int[] a = { 2, 34, 4, 5 }; int[] b = { 26, 24, 345, 4, 22 }; findConcatenatedNumbers(a, b); }}// This code is contributed by sanjoy_62. |
Python3
# Python3 program for the above approachfrom collections import defaultdict# Function to find elements present in# the array b[] which are concatenation# of any pair of elements in the array a[]def findConcatenatedNumbers(a, b): # Stores if there doesn't any such # element in the array brr[] ans = True # Stored the size of both the arrays n1 = len(a) n2 = len(b) # Store the presence of an element # of array a[] cnt = defaultdict(int) # Traverse the array a[] for i in range(n1): cnt[a[i]] = 1 # Traverse the array b[] for i in range(n2): left = b[i] right = 0 mul = 1 # Traverse over all possible # concatenations of b[i] while (left > 9): # Update right and left parts right += (left % 10) * mul left //= 10 mul *= 10 # Check if both left and right # parts are present in a[] if (cnt[left] == 1 and cnt[right] == 1): ans = False print(b[i], end = " ") if (ans): print("-1")# Driver Codeif __name__ == "__main__": a = [ 2, 34, 4, 5 ] b = [ 26, 24, 345, 4, 22 ] findConcatenatedNumbers(a, b)# This code is contributed by chitranayal |
C#
// C# program for the above approachusing System;class GFG{ // Function to find elements present in // the array b[] which are concatenation // of any pair of elements in the array a[] static void findConcatenatedNumbers(int[] a, int[] b) { // Stores if there doesn't any such // element in the array brr[] bool ans = true; // Stored the size of both the arrays int n1 = a.Length; int n2 = b.Length; // Store the presence of an element // of array a[] int []cnt = new int[100000]; // Traverse the array for (int i = 0; i < n1; i++) { cnt[a[i]] = 1; } // Traverse the array b[] for (int i = 0; i < n2; i++) { int left = b[i]; int right = 0; int mul = 1; // Traverse over all possible // concatenations of b[i] while (left > 9) { // Update right and left parts right += (left % 10) * mul; left /= 10; mul *= 10; // Check if both left and right // parts are present in a[] if (cnt[left] == 1 && cnt[right] == 1) { ans = false; Console.Write(b[i] + " "); } } } if (ans) Console.Write("-1"); } // Driver code public static void Main(String[] args) { int[] a = { 2, 34, 4, 5 }; int[] b = { 26, 24, 345, 4, 22 }; findConcatenatedNumbers(a, b); }}// This code is contributed by shivani |
Javascript
<script>// JavaScript program for the above approach// Function to find elements present in// the array b[] which are concatenation// of any pair of elements in the array a[]function findConcatenatedNumbers(a, b){ // Stores if there doesn't any such // element in the array brr[] var ans = true; // Stored the size of both the arrays var n1 = a.length; var n2 = b.length; // Store the presence of an element // of array a[] var cnt = new Map(); // Traverse the array a[] for (var i = 0; i < n1; i++) { cnt.set(a[i], 1); } // Traverse the array b[] for (var i = 0; i < n2; i++) { var left = b[i]; var right = 0; var mul = 1; // Traverse over all possible // concatenations of b[i] while (left > 9) { // Update right and left parts right += (left % 10) * mul; left = parseInt(left/10); mul *= 10; // Check if both left and right // parts are present in a[] if (cnt.has(left) && cnt.has(right)) { ans = false; document.write( b[i] + " "); } } } if (ans) document.write( "-1");}// Driver Codevar a = [2, 34, 4, 5 ];var b = [26, 24, 345, 4, 22 ];findConcatenatedNumbers(a, b);</script> |
Output:
24 345 22
Time Complexity: O(M*log(X)), where X is the largest element in the array brr[].
Auxiliary Space: O(N)
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!