Yes the aim is to minimize the value of X but the minimized value should also satisfy the conditions given in question.
In the above example if you get X=2 then how will you create the second array using the first array & adding X to it’s elements.
May anyone HELP me with this Logic
int n;
cin >> n;
int arr1[n], arr2[n - 1];
for (int i = 0; i < n; i++) {
cin >> arr1[i];
}
for (int i = 0; i < n - 1; i++) {
cin >> arr2[i];
}
int max1 = *max_element(arr1, arr1 + n);
int max2 = *max_element(arr2, arr2 + (n - 1));
int maxdiff = max2 - max1;
sort (arr1, arr1 + n);
sort (arr2, arr2 + (n - 1));
if (n >= 3) {
if ((arr1[0] + maxdiff) == arr2[0] || (arr1[1] + maxdiff) == arr2[0]) {
cout << maxdiff << "\n";
}
else {
int res = arr2[n - 2] - arr1[n - 1];
cout << res << "\n";
}
}
else if (n < 3) {
if (maxdiff <= 0) {
cout << arr2[0] - arr1[0] << "\n";
}
else {
cout << maxdiff << "\n";
}
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl “\n”
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
ll a[n],b[n-1];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n-1;i++)
{
cin>>b[i];
}
sort(a,a+n);
sort(b,b+n-1);
if(n==2)
{
if(b[0]-a[1]<0)
{
cout<<(b[0]-a[0])<<endl;
}
else if(b[0]-a[0]<0)
{
cout<<(b[0]-a[1])<<endl;
}
else
cout<<min((b[0]-a[0]),(b[0]-a[1]))<<endl;
}
else if(b[0]-a[0]==(b[1]-a[1]))
{
cout<<b[0]-a[0]<<endl;
}
else if(b[n-2]-a[n-1]==(b[n-3]-a[n-2]))
{
cout<<b[n-2]-a[n-1]<<endl;
}
else
{
cout<<(b[0]-a[0])<<endl;
}
}
}
can someone explain which test case is going wrong
same doubt
Consider this test case
1 3 5 7 9
5 7 9 11
Here both 2 and 4 are possible values of x. So the output should be the minimum of these two, i.e., 2 but your program is printing 4.
hey i solved problem using same algorithm but checked if bi = ai+x or not. i got AC. code but yeah this is not optimal obviously 
To anyone wondering on which test case the sum approach fails
1 3 4
3 6
ans from algo : 1
correct ans : 2
1 3 4
3 6
ans from algo: 1
correct ans : 2
What is wrong with this code?
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll *arr1=new ll[n];
ll *arr2=new ll[n-1];
for(int i=0;i<n;i++)
{
cin>>*(arr1+i);
}
for(int i=0;i<n-1;i++)
{
cin>>*(arr2+i);
}
int o=n-1;
ll min1=LLONG_MAX,max1=LLONG_MIN,min2=LLONG_MAX,max2=LLONG_MIN;
for(int i=0;i<n;i++)
{
min1=min(arr1[i],min1);
max1=max(arr1[i],max1);
}
for(int i=0;i<o;i++)
{
min2=min(arr2[i],min2);
max2=max(arr2[i],max2);
}
if(n==2)
{
sort(arr1,arr1+n);
sort(arr2,arr2+o);
if(arr1[1]>=arr2[0])
{
cout<<-(arr1[0]-arr2[0])<<endl;
}
else
{
cout<<-(arr1[1]-arr2[0])<<endl;
}
}
else if((max2-max1)==(min2-min1))
{
cout<<max2-max1<<endl;
}
else if(max2<=max1)
{
cout<<min2-min1<<endl;
}
else
{
ll secondmax=LLONG_MIN;
for(int i=0;i<n;i++)
{
if(arr1[i]==max1)
{
arr1[i]=-arr1[i];
}
}
for(int i=0;i<n;i++)
{
secondmax=max(arr1[i],secondmax);
}
if((max2-secondmax)==(min2-min1))
{
cout<<max2-secondmax<<endl;
}
else
{
cout<<max2-max1<<endl;
}
}
}
}
Same here, Couldn’t figure out why its giving wa on first case.
What is wrong in my approach? The logic goes this way - for every value at index i (0<=i<n-1) in B I stored the differences b[i]-a[i], b[i]-a[i+1] in a map. At last I traversed the map to find the difference with count==n-1 and as the difference is stored in a map so the value with count==n-1 will be lowest possible. Code is given below:
#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define pii pair<int, int>
#define vii vector<pii>
#define make make_pair
#define si unordered_set<int>
#define sll unordered_set<ll>
#define mii unordered_map<int, int>
#define mll unordered_map<ll, ll>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define MOD (int) 1e9+7
#define take(n) int n; cin >> n
void pr(int x) {cout << x;}
void prl(int x) {cout << x << endl;}
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define tc(t) int t; cin >> t; while (t--)
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL),cout.tie(NULL)
#define prec(n) fixed<<setprecision(n)
#define ini(a, i) memset(a, i, sizeof(a))
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
int max(int a, int b) {if (a > b) return a; else return b;}
int min(int a, int b) {if (a < b) return a; else return b;}
const int dx[4] = { -1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const int N = (int)(5 * 1e5 + 10);
vector<vector<int>> divs(N);
void pre(){
int i, j;
for1(i, N-1){
for(int j=i;j<N;j+=i)
divs[j].pb(i);
}
}
ll add(ll x, ll y) {ll res=x+y; return res>=MOD ? res-MOD:res;}
ll mul(ll x, ll y) {ll res=x*y; return res>=MOD? res%MOD:res;}
ll sub(ll x, ll y) {ll res=x-y; return res<0? res+MOD:res;}
ll power(ll x, ll y) {ll res=1; x%=MOD; while(y){ if (y&1) res=mul(res, x); y >>=1; x=mul(x, x);} return res;}
ll mod_ind(ll x) {return power(x, MOD-2);}
int main(){
//#ifndef ONLINE_JUDGE
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
//#endif
fio;
tc(t){
take(n);
int arr[n], brr[n-1];
for (auto &i: arr)
cin >> i;
for (auto &i: brr)
cin >> i;
sort(arr, arr+n);
sort(brr, brr+n-1);
if (n==2){
int ans;
if (brr[0]-arr[1]>0)
ans=brr[0]-arr[1];
else
ans=brr[0]-arr[0];
cout << ans << "\n";
continue;
}
map<int, int> mp;
for (int i=0;i<n-1;i++){
mp[brr[i]-arr[i]]++;
mp[brr[i]-arr[i+1]]++;
}
int ans;
for (auto i:mp){
// if (i.first<0)
// continue;
if (i.second==n-1){
ans=i.first;
break;
}
}
cout << ans << "\n";
}
return 0;
}
please help!!
could someone help me find the error in my code
import java.io.*;
import java.util.*;
class Main
{
public static void main(String args[]) throws IOException
{
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(isr);
String s1=in.readLine();
int t=Integer.parseInt(s1);
for(int i=0;i<t;i++)
{
String s2=in.readLine();
int n=Integer.parseInt(s2);
String[] a=in.readLine().split(" ");
String[] b=in.readLine().split(" ");
int[] a1=new int[n];
int[] b1=new int[n-1];
long suma=0,sumb=0;
for(int j=0;j<n-1;j++)
{
a1[j]=Integer.parseInt(a[j]);
b1[j]=Integer.parseInt(b[j]);
suma+=a1[j];
sumb+=b1[j];
}
a1[n-1]=Integer.parseInt(a[n-1]);
suma+=a1[n-1];
int ans=0;
Arrays.sort(a1);
Arrays.sort(b1);
if(n>2)
{
for(int k=0;k<n-1;k++)
{
double x=(sumb-suma+a1[k])/(n-1);
if(x%1!=0)
{
continue;
}
int diff;
if(k==0)
{
diff=b1[0]-a1[1];
if(diff==x)
{
ans=diff;
break;
}
else
{
continue;
}
}
diff=b1[0]-a1[0];
if(diff==x)
{
ans=diff;
break;
}
}
double y=(sumb-suma+a1[n-1])/(n-1);
int diff10=b1[0]-a1[0];
if(diff10==y)
{
ans=diff10;
}
System.out.println(ans);
}
else
{
int diff1=b1[0]-a1[0];
int diff2=b1[0]-a1[1];
if(diff1<0)
{
ans=diff2;
}
else if(diff2<0)
{
ans=diff1;
}
else
{
ans=Math.min(diff1,diff2);
}
System.out.println(ans);
}
}
}
}
edge case is of minimizing x, when n=2 or Ai’s are in AP multiple values of x are possible and one more case is x is positive this case i did wrong and wasted my 15 mins in contest
if arr is 1 2 3 4 and suppose bob added 1 to each then it will become 2 3 4 5 now consider the case when u are given 2 3 4 now in your map mp[2-1]++;mp[2-2]++; mp[3-2]++;mp[3-3]++;mp[4-3]++;mp[4-4]++
and so on now u iterate from first element of map that is mp[0] which is = 3=n-1;u cosider it as answer and print 0 this cotradicts the fact that x is positive i hope u got the error
1 Like
@infinitepro Instead of using extra space to store elements of A in a map, we can simply use Binary Search as initially we have sorted both the arrays A and B which will optimize the space complexity of the solution.
Here is the link to my solution 
REMONE - By dark_coder007
Yep, but I think not implementing binary search is worth the memory tradeoff.
ohhk I got it. Thanks a lot
1
3
1 3 4
3 6
i think this one is the edge case
here is correct answer is 2 but using above approach the answer we get is 1
Yeah i made the test case from your proof.