BitwiseEquations
SRM 430 · 2008-12-20 · by Janq
SRM 430 · 2008-12-20 · by Janq · Simple Math
Problem Statement
Problem Statement
You are given two positive integers x and k. Return the k-th smallest positive integer y (where k is 1-based) for which the following equation holds:
x + y = x | ywhere '|' denotes the bitwise OR operator.
Constraints
- x will be between 1 and 2,000,000,000, inclusive.
- k will be between 1 and 2,000,000,000, inclusive.
Examples
0)
5 1 Returns: 2
The first positive integer for which the equation holds is 2. You can check that 5+2=7 as well as 5|2=7. Both plus and bitwise OR look like the following: 101 + 10 --- 111
1)
5 5 Returns: 18
The fifth number for which the equation 5 + y = 5 | y holds is 18. The first four solutions are 2,8,10,16. The binary sum for 18 looks like the following: 101 +10010 ----- 10111
2)
11 2 Returns: 16
3)
10 3 Returns: 5
The third solution is 5. The first two solutions are 1 and 4.
4)
845 15734 Returns: 1006640
Submissions are judged against all 119 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BitwiseEquations with a public method long long kthPlusOrSolution(int x, int k) · 119 test cases · 2 s / 256 MB per case