Connection Status:
Competition Arena > BitwiseEquations

BitwiseEquations

SRM 430 · 2008-12-20 · by Janq

SRM 430 · 2008-12-20 · by Janq · Simple Math
Class Name: BitwiseEquations
Return Type: long
Method Name: kthPlusOrSolution
Arg Types: (int, int)
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 | y
where '|' 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.

Statement by TopCoder, Inc. — view the original on the archive.

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

Submitting as anonymous