Can any one help what is wrong in my code. I am getting Wrong Answer.
#include #include <bits/stdc++.h>
int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
long int a[n],b[n-1];
long double sa=0,sb=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
sa=sa+a[i];
}
for(int i=0;i<n-1;i++)
{
cin>>b[i];
sb=sb+b[i];
}
unsigned long long int min=ULLONG_MAX;
unsigned long long int y;
for(int i=0;i<n;i++)
{
long double g = (sb-(sa-a[i]))/(n-1);
// cout<<"g="<<g<<" ";
y=g;
if(g-y==0)
{
if(y<min && y>0)
{
// cout<<"y="<<y<<" ";
min=y;
}
}
}
// cout<<"\n";
cout<<min<<"\n";
}
return 0;
}
I used the same approach as well. Wrong answer in part 1, but correct in part 2.
@ankur_10 Isn’t it guaranteed that an X would always exist?
Another approach that is used:1 , A2 , … An 1 , B2 ,… Bn-1 .
We calculate the frequency of difference between A1 , A2 , … An-1 and B1 , B2 ,… Bn-1 ; and between A2 , A3 , … An and B1 , B2 ,… Bn-1 .
The frequency of X must be >= (n-1) as we have added X to n-1 elements. Out of all such values, we take the minimum such X.
One implementation can be:
map<int, int> diff;
for(int i=0; i<n-1; i++){
diff[b[i]-a[i]]++;
}
for(int i=0; i<n-1; i++){
diff[b[i]-a[i+1]]++;
}
int m = 0;
int me = 1e9;
for(auto &i: diff){
if(i.second >= (n-1) && i.first>0){
me = min(me, i.first);
}
}
cout << me << "\n";
My solution
Can someone please tell me where i am making the mistake?
My concept is to find sum of array A(sumA) and array B(sumB) then
sum=sumA-A[i];
x=(sumB-sum)/(N-1);
then I take the minimum of all the “possible” values of x
abhihi
August 29, 2021, 3:09pm
43
Same here. I think @ankur_10 was just trying to make point with example. There will be cases where even after changing values in B it will hold valid status.
thyl
August 29, 2021, 3:10pm
44
X can do =<0 in your solution, but the problem say it cannot
The problem can be solved without extra space as well. My Solution
Thanks for the reply but
3
4
1 4 3 8
15 8 11
2
4 8
10
2
2 4
3
the last one output will be -1 because it is minimum according to you
Please correct me if I am wrong
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.
1 Like
1 2 5 7 13
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.
#include
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.
@ishan301 X=2 , i.e, by algo doesn’t give a correct solution
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;
}
}
}
