Header Ads Widget

Remove One Element | codechef solution

Rajnish Tripathi 20:11

Problem

Alice has an array � consisting of � distinct integers. Bob takes exactly �−1 elements from this array and adds a positive integer � (i.e. �>0) to each of these numbers and then shuffles them to form a new array � of length �−1.

You are given both arrays � and �. You have to identify the value of � chosen by Bob. If there are multiple possible values of �, print the smallest of them. It is guaranteed that for the given input, there exists at least one possible value of �.

Note: Since the input is large, prefer using fast input methods.

Input Format

  • The first line of input contains a single integer � denoting the number of test cases. The description of � test cases follows.
  • Each test case contains 3 lines of input.
  • The first line contains an integer � - the length of array �.
  • The second line contains � space-separated integers �1,�2,…,��, denoting the array �.
  • The third line contains �−1 space-separated integers �1,�2,…,��−1, denoting the array �.

Output Format

For each test case, output the value of � chosen by Bob. In case there are multiple possible values of �, print the smallest of them.

Constraints

  • 1≤�≤7
  • 2≤�≤105
  • 1≤��≤109
  • 1≤��≤2⋅109
  • �1,�2,…,�� are pairwise distinct.
  • �1,�2,…,��−1 are pairwise distinct.
  • Sum of � over all test cases does not exceed 5⋅105.

Sample 1:

Input
Output
3
4
1 4 3 8
15 8 11
2
4 8
10
2
2 4
3
7
2
1

Explanation:

Test case 1: Bob takes the elements {1,4,8} and adds 7 to them to obtain a new sequence {8,11,15}. There is no other value of � that can be added to the elements of � to get �.

Test case 3: There is only one option with Bob to consider, i.e. to take element {2} and add 1 to it to get array �. If he takes element {4}, he will have to add −1

 which is not allowed. 

Code(c++):-

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

int main() {
    // your code goes here
    int t;
    cin>>t;
    while(t--){
     int n;
     cin>>n;
     vector<int> a(n);
     for(int i=0;i<n;i++)cin>>a[i];
     vector<int> b(n-1);
     for(int i=0;i<n-1;i++)cin>>b[i];
     sort(a.begin(), a.end());
sort(b.begin(), b.end());
     unordered_map<int, int>mp;
for(int i:a){
mp[i]++;
}
vector<int> x;
if(b[0]-a[0]>0) x.push_back(b[0]-a[0]);
if(b[0]-a[1]>0) x.push_back(b[0]-a[1]);
int j=0, ans=INT_MAX;
for(int i=0; i<2; i++){
for(j=0; j<n-1; j++){
if(mp[b[j]-x[i]]==0) break;
}
if(j==n-1) ans=min(ans, x[i]);
}
cout<<ans<<endl;
    }
    return 0;
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        Scanner sc=new Scanner(System.in);
        int disha=sc.nextInt();
        while(disha-->0){
         int cnt=0;
         int nocnt=0;
         int n=sc.nextInt();
         int arr[]=new int[n];
         int brr[]=new int[n-1];
         for(int i=0;i<n;i++){
         arr[i]=sc.nextInt();
         }
         for(int i=0;i<n-1;i++){
         brr[i]=sc.nextInt();
         }
         Arrays.sort(arr);
         Arrays.sort(brr);
         int diff1=brr[0]-arr[0];
         int diff2=brr[0]-arr[1];
         int cnt1=0;
         int cnt2=0;
         for(int i=0;i<brr.length;i++){
         if(brr[i]-arr[i]>0){
         if(brr[i]-arr[i]==diff1)cnt1++;
         if(brr[i]-arr[i]==diff2)cnt2++;
         }
         if(brr[i]-arr[i+1]>0){
         if(brr[i]-arr[i+1]==diff1)cnt1++;
         if(brr[i]-arr[i+1]==diff2)cnt2++;
         }
         }
         if(diff1<=0)
         System.out.println(diff2);
        
         else if(diff2<=0)
         System.out.println(diff1);
        
         else if(cnt1 > cnt2 && diff2 > 0) {
System.out.println(diff1);
}
else {
System.out.println(diff2);
}
        }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-




Tags:

Post a Comment

0 Comments