# Remove One Element | codechef solution

## 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},\dots ,{�}_{�}$, denoting the array $�$.
• The third line contains $�-1$ space-separated integers ${�}_{1},{�}_{2},\dots ,{�}_{�-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\le �\le 7$
• $2\le �\le 1{0}^{5}$
• $1\le {�}_{�}\le 1{0}^{9}$
• $1\le {�}_{�}\le 2\cdot 1{0}^{9}$
• ${�}_{1},{�}_{2},\dots ,{�}_{�}$ are pairwise distinct.
• ${�}_{1},{�}_{2},\dots ,{�}_{�-1}$ are pairwise distinct.
• Sum of $�$ over all test cases does not exceed $5\cdot 1{0}^{5}$.

### 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 $\left\{1,4,8\right\}$ and adds $7$ to them to obtain a new sequence $\left\{8,11,15\right\}$. 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 $\left\{2\right\}$ and add $1$ to it to get array $�$. If he takes element $\left\{4\right\}$, 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:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-