How to solve BT engine from "Crack me if you can!" yesterday's contest?

I was unable to solve BT Engine question of yesterday’s contest. Can anyone explain your approach if you got AC. Explanation with your submission url or code url is highly appreciated. Do we need to know any algorithm or simple observation + math is needed? Thank you :slightly_smiling_face:

Hello @ganesh_6

Simple math and observation is enough. First read this to know about cumulative XOR of numbers from 1 to n.

Now, observe that upto n, cumulative XOR for n / 2 numbers (specifically, for all numbers i, such that i % 2 = 0), numbers will be greater than 1. Also, that will be in increasing order (easy to prove using the link I have provided earlier). Another n / 4 numbers (for all numbers i, such that i % 4 = 1) cumulative XOR is 1 and remaining numbers (for all numbers i, such that i % 4 = 3) cumulative XOR is 0.

My correct submission can be seen here.

If you can’t think logically, use brute force to observe these type of things.

2 Likes

Thank you :slight_smile: