[Solved] Remove One Element codechef solution

Remove One Element codechef solution

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

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

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

Input Format

  • The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • Each test case contains 33 lines of input.
  • The first line contains an integer NN – the length of array AA.
  • The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN, denoting the array AA.
  • The third line contains N1N−1 space-separated integers B1,B2,,BN1B1,B2,…,BN−1, denoting the array BB.

Output Format

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

Constraints

  • 1T71≤T≤7
  • 2N1052≤N≤105
  • 1Ai1091≤Ai≤109
  • 1Bi21091≤Bi≤2⋅109
  • A1,A2,,ANA1,A2,…,AN are pairwise distinct.
  • B1,B2,,BN1B1,B2,…,BN−1 are pairwise distinct.
  • Sum of NN over all test cases does not exceed 51055⋅105.

Sample Input 1  

3
4
1 4 3 8
15 8 11
2
4 8
10
2
2 4
3

Sample Output 1  

7
2
1

Explanation

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

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


Solution 


Python

from collections import *
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort()
x = float(“inf”)
d = defaultdict(int)
for i in range(n – 1):
d1 = b[i] – a[i]
d2 = b[i] – a[i+1]
if d1 != d2:
if d1>0:
d[d1]+=1
if d2>0:
d[d2]+=1
else:
if d1>0:
d[d1]+=1
for i in d.keys():
if d[i] == n-1:
x = min(x, i)
print(x)


JAVA

 

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

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Reader rd=new Reader();
int t=rd.nextInt();
for(int z=0;z<t;z++){
int n=rd.nextInt();
int A[]=new int[n];
int B[]=new int[n-1];
for(int i=0;i<n;i++){
A[i]=rd.nextInt();
}
for(int i=0;i<n-1;i++){
B[i]=rd.nextInt();
}

Arrays.sort(A);
Arrays.sort(B);

// int a=B[0]-A[0];
// int b=B[0]-A[1];
// int c=B[1]-A[1];
// int d=B[1]-A[2];

// if(a==b)
// System.out.println(Math.abs(a));
// else if(b==c)
// System.out.println(Math.abs(b));
// else if(c==d)
// System.out.println(Math.abs(d));
// else if(a==d)
// System.out.println(Math.abs(a));
// int start=B[0]-A[0];

HashMap<Long,Integer> set=new HashMap<Long,Integer>();

for(int i = 0; i < n-1; i++) {
long x1 = B[i] – A[i];
long x2 = B[i] – A[i+1];
if(x1 != x2) {
if(x2 > 0) {
set.put(x2, set.getOrDefault(x2, 0) + 1);
}
}
if(x1 > 0) {
set.put(x1, set.getOrDefault(x1, 0) + 1);
}
}
long ans = (long) Integer.MAX_VALUE;
for(long k : set.keySet()) {
if(set.get(k) == n-1) ans = (long) Math.min(ans, k);
}
System.out.println(ans);

}
}
}
class Reader{
BufferedReader br;
StringTokenizer token;
public Reader(){
br=new BufferedReader(new InputStreamReader(System.in));
}

String next(){
while(token==null||!token.hasMoreTokens()){
try
{
token = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}

return token.nextToken();
}

int nextInt(){
return Integer.parseInt(next());
}
float nextFloat(){
return Float.parseFloat(next());
}

long nextLong()
{
return Long.parseLong(next());
}

double nextDouble()
{
return Double.parseDouble(next());
}

String nextLine()
{
String str = “”;
try
{
str = br.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}

}


C++

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
ll test;
cin>>test;
while(test–)
{
ll n,i;
cin>>n;
ll a[n];
ll b[n-1];
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n-1;i++)
cin>>b[i];
sort(a,a+n);
sort(b,b+n-1);
map<ll,ll>m;

for(i=0;i<n-1;i++)
{
ll p=b[i]-a[i];
ll q=b[i]-a[i + 1];
if (p!=q)
{
if(p>0)
m[p]++;
if(q>0)
m[q]++;
}
else
{
if(p>0)
m[p]++;
}
}
for(auto pr:m)
{
if(pr.second==n-1)
{
cout<<pr.first<<endl;
break;
}
}
}
}


 Remove One Element codechef solution


Also read :  Polycarp and String Transformation solution codeforces

No Comments, Be The First!

Your email address will not be published.