0 like 0 dislike
1,075 views
| 1,075 views

0 like 0 dislike

PhonePe - Online Assessment
Question 1: Given an array numbers[] of N positive integers and a positive integer X, The task is to find the number of ways that X can be obtained by writing pair of integers in the array numbers[] next to each other. In other words, find the number of pairs (i,j) such that i != j and X is the concatenation of numbers[i] and numbers[j]

Example 1:
Input:
N = 4
numbers[] = {1, 212, 12, 12}
X = 1212

Output:
3

Explanation:
We can obtain X=1212 by concatenating:
numbers[0] = 1 with numbers[1] = 212
numbers[2] = 12 with numbers[3] = 12
numbers[3] = 12 with numbers[2] = 12

by Expert (46,090 points)
0 like 0 dislike
//space complexity :- O(n)

//time complexity :- O(max(length of  input int , n))

#include <bits/stdc++.h>
using namespace std;

int f(vector<int>& v , int k)
{
map<int , int> m;
for(int x : v)
m[x]++;
int ans = 0;
int l = 10;
while(k / l > 0)
{
int a = k%l;
int b = k/l;

if(m.find(a) == m.end() || m.find(b) == m.end())
{
l = l*10;
continue ;
}

if(a == b)
ans = ans + m[a]*(m[a] - 1);

else
ans = ans + m[a]*m[b];

l = l*10;
}

return ans;
}

int main()
{

int n;
cin>>n;

int x;
cin>>x;

vector<int> v(n);

for(int i = 0 ; i < n  ; i++)
{
cin>>v[i];
}

cout<<f(v , x);

return 0;
}
by (140 points)
0 like 0 dislike

TimeComplexity = O(n)
SpaceComplexity = O(n)
Used HashMap

public static int find(int n,String arr[],String x)
{
int xlen = x.length();
Map<String, Integer> hm = new HashMap<>();
for(int i=0;i<n;i++) hm.put(arr[i],hm.getOrDefault(arr[i],0)+1);

``````    int cnt = 0;
for(int i=0;i<n;i++){

String s1 = arr[i];
int len1 = s1.length();
if(len1>xlen) continue;

String xpre = x.substring(0,len1);
if(!xpre.equals(s1)) continue;

String xpost = x.substring(len1);
if(hm.containsKey(xpost)) cnt+=hm.get(xpost);
if(xpre.equals(xpost)) cnt-=1;
}
return cnt;
}``````
by Expert (46,090 points)