Problem
Submission
What am I missing?
if(remaining_elements%2==0){
cout<<(x+remaining_elements)<<"\n";
}else{
if(on_bits<=1){
if(remaining_elements==1){
if(x==1){
cout<<(x+4)<<"\n";
}else{
cout<<(x+n)<<"\n";
}
}else{
cout<<( x+remaining_elements+3)<<"\n";
}
}else{
cout<<(x+remaining_elements+1)<<"\n";
}
}
}
cout<<(x+4)<<"\n" this is pretty much handles a case, if x==1 and there are only one remaining_element i.e n=2
cout<<(x+n)<<"\n", this is when $$$x=2^i$$$ where $$$i \gt 0$$$ and remaining_elements = 1 i.e when n=2
cout<<(x+remaining_elements+3)<<"\n", this handles when we have $$$x=2^i$$$ for $$$i \gt 0$$$ and remaining_elements = {3, 5, ...}
We can generalize this, since remaining_elements will be odd $$$ \gt =3$$$ we can set 0th bit on for all remaining_elements, upto
(remaining_elements-1) then we set 1st bit($$$2^1$$$) for last element and last second so in total : $$$x+(RemainingElements-1)+2+2$$$
so where does this fail?
The erro is in the case where x is a power of two (popcount=1) and you have an odd >=3 “extra” elements: you print x + (rem) + 3 but you can do better by choosing [x+1,1,1,…,1] (n elements) for a sum of x+n and xor x. Replace that to output x + n instead of x + rem + 3
this should pass :
int b = __builtin_popcountll(x); int remaining_elements = n - b; if (remaining_elements < 0) { cout << x << endl; continue; } if (remaining_elements%2 == 0) { cout << (x + remaining_elements) << endl; } else { if (b >= 2) { cout<<(x +remaining_elements+ 1) << endl; } else { if (x==1) { cout << (n + 3) << endl; } else { cout << (x + n) << endl; } } } }It seems to me at least some optimization you can make is for $$$x = 2^i, i \gt = 1$$$ and $$$n\ mod 2 = 0$$$ (even $$$n$$$) case where you would set $$$1st$$$ element to $$$x + 1$$$ and all other $$$n - 1$$$ elements to $$$1$$$.
So for case:
The optimal answer is at most: