 # A^b = a+b , given a find the smallest b possible

Alice wants to send a secret message to Bob. She encrypts the message with the public key (pub) of Bob and sends the message. Eve tries to perform an attack on the message. She knows that the public key and private key are related to each other with the following boolean relation:

pub ^ prv = pub + prv

Now as Eve knows the public key of Bob, she wants to determine his private key using the above relation.

Note: Bob has n private keys.

Input Format

• The first line contains a single integer q, the number of queries.
• Each of the next q lines contain a integer, the public keys of Bob.

Constraints

• 1 <= q <= 15
• 1 <= pub, prv < 10^18

Output Format

For each query, print smallest private key of Bob on a new line.

Sample Input 0

2 4 19

Sample Output 0

1 4

Explanation 0

for first input, pub = 4:

`4^1 = 5 = 4+1, 4^3 = 7 = 4+3, 4^9 = 13 = 4+9 and so on..`

But out of 1, 3, 9, . . . the smallest one is 1.

The below is my code, which just finds the first occurrence of 0 of the number , but it is not able to pass all the test cases, I know there is some minor mistake, but I am unable to point it out, any help or any other solution will be great. thank you

#include
#include
#include
#include
#include
using namespace std;

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int q;
cin>>q;
while(q–){
long long int pub;
cin>>pub;

``````    for(long long int i=0;i<=64;i++){

if((pub & (long long int)(1<<i)) == 0){

cout<<pow(2,i)<<endl;
break;
}
}
}
return 0;
``````

}

It should be `(1ll<<i)`, you need to cast the 1 to long long.

2 Likes

thank you for the reply, but it’s still not working, 2 test cases are still failing, as it was previously.

Do you have a link to the problem?

tell me if its working or not.

`pow` returns something like `9e+ 42` for huge numbers which gives WA.
Why not use `1LL << i` again?
alternatively, you could use` cout << setprecision(0) << fixed << pow(2, i)`

2 Likes

You cud also first store it in a variable like `ans = pow(2, i);` then output `ans`

1 Like

Yes, the link is working. As said by @singlabharat , you can use `(1LL << i)` again since `pow()` function works with doubles and shows unexpected behaviour.

1 Like

thank you @singlabharat @suman_18733097 . I was actually not aware of that , now its working just fine. Big Thanx!!

Yeah np