[-1,-2,10] sum=7
we can also do like that
[-1, -2, 7 ]–> [-1,-4,7]–> [-1,-6,7] sum=0
no operation =3 (if we have find to min operation)
[-1,-2,10] sum=7
we can also do like that
[-1, -2, 7 ]–> [-1,-4,7]–> [-1,-6,7] sum=0
no operation =3 (if we have find to min operation)
i already got that bro
can anyone tell. if we can subtract one element only once. then how this problem will be solved ??
@anon22113685 Well in that case you can subtract atmost : n * ( n + 1 ) / 2
from your sum so we will simply check
if( sum >= 0 && sum <= n*(n+1)/2 )
cout << "YES\n" ;
else
cout << "NO\n" ;
logic ???
@akshy_8 With numbers 1 , 2 , 3 , 4 , 5 , . . . . . , n , we can make every possible sum between [ 1 , n*(n+1)/2 ] , Here n*(n+1)/2 is sum of first n natural numbers.
You can prove it this way using induction
Thankyou
why the problem name was watermelon??
its super easy index sum the element @2,3,4,5 their total be 28. take 1st index to -28 ,by decreasing it by 1 each time you get 0 as totalsum now
I was thinking the question in this way…so I got wa
Thanks for the effort man
Yes!! I’m totally agree with you.
I think question is not clearly mention what’s it saying,
According to Question:-
choose some i, and reduce the value of a[i] by i. Find out if it’s possible to make the sum of all the integers equal to 0.
A/c to me solution is like this
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n];
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int sum=0;
for(int i=1;i<=n;i++)
{
sum += a[i];
sum -= i;
}
if(sum) cout<<"NO\n";
else cout<<"YES\n";
}
So please can anyone help me out of it.
My solution got accepted
What I found is that if the summation of all the elements is positive then there might be or I think must be a way to make the sum zero but if the sum is negative then there’s absolutely no way.
Every position has a weight of its own like in
[2,3,5] element 2 has weight 1 ie. we can only subtract 1 from the first element, element 3 has weight 2 and 5 has weight 3
That means every element has a predefined weight which is its position.
Here is what I did. I didnt use an array I simply summed up the elements and passed the total sum to function “check”
Check function tries to make a newsum using the weights equal to the sum passed to it.
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
bool check(int num, int size)
{
int Sum = 0, temp = num;
num = abs(num);
for (int i = size; i >= 1; i–)
{
Sum += i * (num / i);
num %= i;
}
return (Sum == temp);
}
int main()
{
int T; cin>>T;
while(T–)
{
int N; cin >> N;
int sum = 0;
int size = N;
while (N–)
{
int a; cin >> a;
sum += a;
}
if (check(sum, size))
cout << “YES” << endl;
else
cout << “NO”<<endl;
}
return 0;
}
Lets take the input [2,3,5]
Sum is 10
I call check(num, size) // size is 3 and num is 10
check function will try to make a newsum equal to 10 by using the weights of the elements
First iteration:
Newsum += 3*(10/3) = 9 # just remember 10/3 = 3
new num = 10%3 = 1
Newsum += 2*(1/2) #j ust remember 1/2 =0
new num = 1%2 = 1
Newsum += 1*(1/1) # just remember 1/1 = 1
new num += 1%1 = 0
So now what does that 3 0 1 mean
[2,3,5]
From 5 subtract its weight (3) 3 times ie 5 becomes 5-9 = -4
From 3 subtract its weight (2) 0 times ie 3 becomes 3-0 = 3
From 2 subtract its weight (1) 1 time ie 2 becomes
2-1 = 1
Sum the numbers = -4 + 3 + 1 =0
Therefore ans is “YES”
.
.I hope this helps out
If somethings wrong with my idea or code please do tell me.