Yes please some one tell what is the problem in this approach or tell what is the test case 2 for which it is showing WA so i can figure out my mistake.
This is making me crazy, if anyone can help then please.
1 Like
1 2 5 7 13
6 7 10 12
you can try this test case where X must be 5
but the algorithm gives 2.
2 Likes
I get it. yes for this test case my approach is giving the wrong answer but can u explain why? Continuing the discussion from My solution
Please tell me why my code is giving the wrong output.
I have used the algorithm that - if we have taken only n-1 elements from A and left kth element of A (Ak) and added X to each then -
Sum of elements (B) = (Sum of elements (A) - Ak) + X * (n-1)
using namespace std;
int main() {
long long int T,N,temp,sumB=0,sumA=0;
cin>>T;
while(T--){
sumA=0;sumB=0;
cin>>N;
long long int A[N],B[N-1];
for(long long int i=0;i<N;i++){
cin>>A[i];
sumA+=A[i];
}
for(long long int i=0;i<N-1;i++){
cin>>B[i];
sumB+=B[i];
}
long long int X=sumB;
for(long long int i=0;i<N;i++){
temp = sumA-A[i];
temp = sumB-temp;
if(temp%(N-1)==0 and temp/(N-1)>0){
if(X>temp/(N-1))X=temp/(N-1);
// break;
}
}
cout<<X<<endl;
}
return 0;
}
In the problem it was mentioned In case there are multiple possible values of X, print the smallest of them.
Even i did the same approach, but sadly someone posted the same approach as the editorial on youtube and it had more than 1k views during the contest. 
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