Given an integer X represented by a binary string S, in one move you can pick an integer 1 \leq Y \leq |S| and set X \gets X \oplus \left \lfloor \frac{X}{2^Y} \right \rfloor.
What is the maximum value of X that can be achieved after performing this exactly once?
EXPLANATION:
First, note that the given operation essentially translates to the following:
Choose 1 \leq Y \leq |S|
Consider the integer X_2 obtained by right-shifting X by Y
Set X \gets X \oplus X_2
Essentially, X is xor-ed with a right-shifted version of itself.
Now, in order to maximize the result, note that we want as many of the highest possible bits to be turned on as possible.
Proof
This follows from the simple fact that
2^i \gt 1 + 2 + \ldots + 2^{i-1}
for any i \geq 0.
In other words, turning on the i-th bit at any cost is always strictly more profitable than turning on all of the lower bits.
So, we will aim to do the following:
All the highest bits of X that are already on shouldn’t be changed
We should turn on the largest off bit of X
This can be achieved as follows:
Let a_0 denote the (1-indexed) position of the highest off bit of X.
S represents integer X, so its first bit is always on (unless X = 0, in which case any move we make is optimal anyway).
So, a_0 \gt 1, and the only way to flip a_0 without affecting the higher bits is to choose Y = a_0 - 1.
If a_0 doesn’t exist, then every bit of X is on. Choosing Y = |S| in this case ensures X doesn’t change, solving this case.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
ans = n
for i in range(1, n):
if s[i] == '0':
ans = i
break
print(ans)
What is wrong with this code , it gave same answers in all my test cases, but was giving wrong answer( not TLE).
#include<bits/stdc++.h>
using namespace std;
long long int binaryToDecimal(string n)
{
string num = n;
long long int dec_value = 0;
// Initializing base value to 1, i.e 2^0
long long int base = 1;
int len = num.length();
for (int i = len - 1; i >= 0; i--) {
if (num[i] == '1')
dec_value += base;
base = base * 2;
}
return dec_value;
}
int main(){
int t;
cin>>t;
while(t--){
long long int n;
cin>>n;
string s;
cin>>s;
long long int number=binaryToDecimal(s);
int count=1 ;
long long int myans=-1;
long long int maxans=INT_MIN;
long long int temp=number;
while(temp>0){
temp=temp>>1;
long long int z=temp^number;
if((z)>=maxans){
maxans=z;
myans=count;
}
count++;
}
if(number==0){
cout<<1<<endl;
}
else{
cout<<myans<<endl; }
}
can anyone tell me why the following code is failing last 4 test cases
#include
#include<math.h>
using namespace std;
int main()
{
long long int t;
cin>>t;
for (long long int i = 0; i < t; i++)
{
long long int l,dec=0,digit,temp=-1,ans,x;
long long int j=1,w;
string s;
cin>>l>>s;
for (int k = l-1; k>=0; k–)
{
w=((int)s[k])-48;
dec=dec+(wj);
j=j2;
}
x=dec;
for (long long int y = 1; y <=l; y++)
{
dec=(x ^ (x >> y));
if(temp<dec){ans=y;temp=dec;}
}
cout<<ans<<endl;
}
}
All three of you (and possibly many others) have the exact same issue: you try to convert the input string to a binary integer, then apply bruteforce xor operations in an attempt to find the answer.
That is never going to work because the input string represents a number that is way too large to be stored in int or long long or any other data type in C++. Depending on your implementation, you’re going to end up with either TLE or WA.
The trick behind this problem is that you can solve it without computing any of the integers involved, please read the editorial to see how to do that.