Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
895 views
in Online Assessments by Expert (46,090 points) | 895 views

3 Answers

0 like 0 dislike
Best answer

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)