Suppose,
a = 7 → 111
b = 1 ->001
n = 5, n-1 = 4, → 100
We have to change 2 bits in a to b, we can’t choose 110 to XOR as it’s greater than n,
But we can choose 100 and 10, so two operations
5 Likes
My code will not print -1 .
1010 , 1001 both have 4th bit as most significant set bit so i==j is satisfied
and n!=power of 2, therefore the ans is 2.
Let’s say n is 21, if a ^ b is 20 then the output should be 1.
Your code output will be 2.
Suppose a = 7, b = 18, a ^ b = 21 and N = 17.
Since N is lesser than a ^ b you can’t choose x = 21 and get b in one operation.
In first operation, choose x = 16 (nearest power of 2 to (a ^ b), and it should be lesser than N, that’s why we are checking that log step) and xor it with a, a will become 21.
In 2nd operation choose x = 7 and xor it with a, a will become 18.
Dry run this case, you will get the intuition.
1 Like
bhava discord id dena tuzi . I have some doubts regarding my solution
test()
{
ll a,b,n;cin>>a>>b>>n;
ll xr=a^b;
ll rxr=rightSetBit(xr),rn=rightSetBit(n-1);
if(a==b)
cout<<0<<endl;
if(b==0)
cout<<1<<endl;
else if(n-1>=xr)
cout<<1<<endl;
else if(rxr==rn)
cout<<2<<endl;
else
cout<<-1<<endl;
}
Can some one tell me which test case am i missing i was able to get partial marks for this.
can anyone explain me why the minimum operation can’t be greater than 2 . also how are we checking that minimum operation is 2 . ??
1 Like
IMPORTANT OBSERVATION :
Decimal → 2^n > (2^n)-1
Binary → 1+(n zeros) > (n ones)
Example :
Decimal = 8
Binary = 1000
Here, 1000 > 0111
But, 1000 == 1000, and 1000 < 1001, of course in binary,
That says that if most significant bit of (a^b) differ, and is equal to most significant bit in n, then in 1 operation we can change the most significant bit only, and in another operation we can change all bits less than most significant one… so total 2 operations at max
I actually just hard coded,
#include <bits/stdc++.h>
#define int long long int
void solve(){
int a, b, n;
std::cin >> a >> b >> n;
int num = 1, val = 0;
std::vector <int> dp(32);
for(int i=0; i<32; i++){
if((a&1) != (b&1)){
dp[i] = 1;
val = num;
}
a >>= 1;
b >>= 1;
num <<= 1;
}
if(val >= n){
std::cout << "-1\n";
return;
}
int cnt = 0, sum = 0;
for(int i=31; i>=0; i--){
if(dp[i]){
if(sum + (1<<i) >= n){
cnt += 1;
sum = 0;
}
sum += (1<<i);
}
}
std::cout << (sum == 0 ? cnt : cnt+1) << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
int t = 1;
std::cin >> t;
while(t--){
solve();
}
}
1 Like
Discord nahiye bhava, ithech v4 ki
Let a = 7, b = 1, n = 5.
let’s find x such that a ^ x = b
So, by using xor property we get x = a ^ b
Now, let say x > = n . So, we can’t use x directly.
let x = d1 ^ d2
So, if d1 < n && d2 < n then, we can replace x by ( d1 ^ d2 )
a ^ ( d1 ^ d2 ) = b
So, all we have to find is, if there exist a pair ( d1 , d2 ) such that d1 < n && d2 < n
So, to find that we simply have to see if n-1 and x have same base of not ,because
the largest set bit of any of the d1 or d2 is equal to the largest set bit of x if
d1 ^ d2 =x.
Ex : let x =6 —> 110 if we want a (d1, d2) for x then think of it how we can generate it?
we must have the leftmost bits of d1 d2 be 0 and 1 such that 0 ^ 1= 1.
here d1 =4–>100 d2 = 2–>010 .
So, we have to do
- a = a ^ d1
- a ^ d2 So, two operations… ans = 2
If the base of x is greater than n-1 , then we know that one of the d1 or d2 have the largest set bit equal to the largest set bit of x .
means one of d1 or d2 will be greater than n-1. So, we have no solution.
sorry for bad english.
3 Likes
are voice channel madhe sangitle aste tar clear zale aste . but still taku ka ithe code jo 30 points sathi accept zala hota. Mala mazi mistake mahitiye but ti resolve kashi karu te kalat nahiye
1 Like
Your logic is correct. i think the problem is here , rn=rightSetBit(n-1) let say x=1 and n=1. now answer should be -1, as x>n-1. but when you call for rightsetbit (depends on your implementation) it may be returning 0. and the rightmost set bit of x=1 is also zero, return 2 which is wrong.
Even though my code is running , there is a heavy flaw in constraints
In statement it is written 1 ≤ X < N , see the testcase
1
3 2 1
a=3 b=2 n=1
according to equality x=1 is not possible ,
also later in editorial it is written X≤N. Answer is 1.
but judge is taking -1.
This is self contradicting.
I feel like that’s a typo because everything else checks out
Hey, in the editorial I have decreased N by 1 at the start.
2 Likes
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int t;
cin>>t;
while(t–){
int a,b,n;
cin>>a>>b>>n;
a=a^b;
if(a==0)
cout<<0;
else {
n–; //X is till n-1
int m=n;
int z=a;
int i=0,j=0;
while(a){
i++;
a=a>>1;
}
while(n){
j++;
n=n>>1;
}
if(i>j)
cout<<-1;
else if(z<=m)
cout<<1;
else
cout<<2;
}
cout<<"\n";
}
return 0;
}
i==j does not always implies that ans could be 2.Eg-a=101 , n=110 . When a<=n then ans will be 1 otherwise it will be 2 .Eg a=110 ,b=101.
Can Someone explain tester’s solution.
Can anyone tell me any testcase which my code is failing on?
using namespace std;
int valueof(int a[])
{
int total=0;
for(int i=0;i<32;i++)
{
total+=a[i]*(pow(2,i));
}
return total;
}
int powsize(int a[])
{
int i=31;
while(a[i]==0)
{
i--;
}
return i;
}
void binary(int x,int p[])
{
int i=0;
while(x!=0)
{
p[i]=x%2;
x=x/2;
i++;
}
}
int main() {
int t;
cin>>t;
while(t--)
{
int a1[32]{0},b1[32]{0},r1[32]{0},n1[32]{0};
int a,b,n,v,sr,sn;
cin>>a>>b>>n;
n-=1;
binary(a,a1);
binary(b,b1);
binary(n,n1);
for(int i=0;i<32;i++)
{
if(a1[i]==b1[i])r1[i]=0;
else
r1[i]=1;
}
sr=powsize(r1);
sn=powsize(n1);
if(sn>=sr)
{
v=valueof(r1);
if(v==0)cout<<"0"<<endl;
else if(v<=n)cout<<"1"<<endl;
else
cout<<"2"<<endl;
}
else
cout<<"-1"<<endl;
}
return 0;
}
you can say n is 21, if a ^ b is 20 then the output should be 1.
Your code output will be 2. test cases will give error