anyone pls help me.
thanks bro.
2 Likes
Go through the question carefully. Its given that choose some i, and reduce the value of ai by i. You can perform this operation any number of time on any element of the array.
i think the question is not totally clear
4 Likes
We can reduce it to [ -1, -1, 1, 1]. We can reduce 17-4-4-4-4= 16, 1-2=-1 and 1-1-1=-1
[-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" ;
1 Like
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
1 Like
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
1 Like
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.