You are given an integer N. Consider the sequence containing the integers 1, 2, \ldots, N in increasing order (each exactly once). Find the maximum length of its contiguous subsequence with an even sum.
EXPLANATION:
\sum_{k=1}^{k=n} k = n*(n+1)/2
Take whole sequence if above sum is even else leave out 1 to make sum even
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
SOLUTIONS:
[details = âEditorialâs Solutionâ]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,e) for(ll i = 0; i < e; i++)
void solve()
{
ll n;
cin>>n;
ll sum = (n*(n+1))/2;
if(sum%2)
{
cout<<n-1<<endl;
}
else
{
cout<<n<<endl;
}
}
int main()
{
ll t=1;
cin >> t;
forn(i,t) {
solve();
}
return 0;
}
You should check the sum of entire series. In that way if sum is odd just one can be removed to make it largest even sum subsequence
What youâre doing fails for numbers like 10. (Ans should be 9 but your code gives 8)!
Hope this helps even a little bit!
Brother I could see that you didnât intialize the sum variable to 0 before using it. So when you write sum+=i you are adding it to the garbage value. Sum has garbage value(unpredictible value) in it.
Replace int sum with int sum=0;
Also you are adding extra couts i mean remove all those else statements and replace them with just single cout<<count<<endl; as this will do the job.
Also this logic is not what the question asked. I did the same logic untill i saw the editorial loll.
Happy to hear back from you brother love from India
from sys import stdin
for _ in range(int(stdin.readline())):
n = int(stdin.readline())
print (n if (n+1)//2%2==0 else n-1)
To save a multiply operation only (n+1)//2 needs to be checked for parity. Yes, I know its miniscule, but in systems running 100 billion operations every second it really helps.
i feel like this problem is not right becoz when n=6 it will return 5 but for the statement âmaximum length of subsequences whose sum is evenâ 5 is not right answer 1+2+3+4+5=15 which is odd
To falsify the given solution: For 22 as input it gives 21 as output and for 21 as input it gives 20 as output. This clearly means for 22 it should give 20 only and not 21. Sum of first 22 & 21 integers 1+âŚ+ 22 & 1+âŚ+21 both are odd.
What does contiguous subsequence mean? Does it mean just next subsequence (regardless of it being even)? I was under the impression that the statement asks for highest even-summed subsequence? What does CONTIGUOUS mean ? @grimshinigami1 is that what you meant ?