TopCoder Statistics - 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.

Definition

Class:: BitwiseEquations
Method:: kthPlusOrSolution
Parameters:: int, int
Returns:: long
Method signature:: long kthPlusOrSolution(int x, int k)
(be sure your method is public)

Constraints

x will be between 1 and 2,000,000,000, inclusive.
k will be between 1 and 2,000,000,000, inclusive.

Examples

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
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
11

2

Returns: 16
10

3

Returns: 5

The third solution is 5. The first two solutions are 1 and 4.
845

15734

Returns: 1006640
1

1000000000

Returns: 2000000000
256

1000000000

Returns: 2000000000
1000000000

165446

Returns: 1077941318
4

500000

Returns: 1000000
4

1000000000

Returns: 2000000000
4

1000000001

Returns: 2000000001
4

999999999

Returns: 1999999995
1024

1000000511

Returns: 1999999999
1024

1000000512

Returns: 2000001024
1073741824

1073741823

Returns: 1073741823
1073741824

1073741824

Returns: 2147483648
2000000000

262144

Returns: 2147483648
2000000000

262143

Returns: 147483647
1073741823

1

Returns: 1073741824
1073741823

2

Returns: 2147483648
1

1000000001

Returns: 2000000002
1

2000000000

Returns: 4000000000
2000000000

2000000000

Returns: 16383165351936
1804289384

9159

Returns: 4241415
1681692778

84084

Returns: 306186000
1957747794

23808

Returns: 38600704
719885387

22765

Returns: 68430500
596516650

31950

Returns: 476102740
1025202363

1964

Returns: 14951168
783368691

7932

Returns: 21806592
44897764

327

Returns: 40971
1365180541

25283

Returns: 201371778
304089173

1124345

Returns: 138737538
35005212

59881

Returns: 29908033
294702568

17294

Returns: 67567638
336465783

9563

Returns: 144793736
278722863

4708

Returns: 151191680
145174068

22432

Returns: 85508352
1101513930

1947

Returns: 1585445
1315634023

1331

Returns: 553975832
1369133070

251832

Returns: 773893568
1059961394

1113

Returns: 4195521
628175012

252251

Returns: 444992083
1804289384

846930887

Returns: 27751935424519
1681692778

714636916

Returns: 11708143961872
1957747794

424238336

Returns: 13900700254208
719885387

649760493

Returns: 10645345348260
596516650

189641422

Returns: 6213946359892
1025202363

350490028

Returns: 91877984707328
783368691

102520060

Returns: 6718419942912
44897764

967513927

Returns: 7925843271691
1365180541

540383427

Returns: 17706581504130
304089173

303455737

Returns: 77469562754
127

1000000000

Returns: 128000000000
2000000000

2000000000

Returns: 16383165351936
1073741823

2000000000

Returns: 2147483648000000000
1073741824

2000000000

Returns: 3073741824
1804289383

1846930886

Returns: 242079664218256
1681692777

1714636915

Returns: 28091539785478
1957747793

1424238335

Returns: 46669131817902
1719885386

1649760492

Returns: 54058746421552
1596516649

1189641421

Returns: 77962797126738
1025202362

1350490027

Returns: 177010674795781
1783368690

1102520059

Returns: 36127129138181
1044897763

1967513926

Returns: 4126175100141592
1365180540

1540383426

Returns: 25237328517122
1304089172

1303455736

Returns: 85422873324960
1979711487

2000000000

Returns: 1073741824000000000
1073741823

1073741823

Returns: 1152921503533105152
1999999999

2000000000

Returns: 8388608000000000
10000000

10000000

Returns: 2554487040
1999999999

1999999999

Returns: 8388606000000000
1073741823

1073741824

Returns: 1152921504606846976
253434343

1000000000

Returns: 131071937085440
156

10737

Returns: 171777
5

2000000000

Returns: 8000000000
200000000

200000000

Returns: 819064734720
42145

103230491

Returns: 6606749782
199999999

199999999

Returns: 209715000000000
13

2000000000

Returns: 16000000000
1999999997

2000000000

Returns: 4194304000000000
12345

1000000000

Returns: 64000000000
2000000000

190000000

Returns: 1554920907648
1923023416

1234984312

Returns: 20233609860544
24333

2000000000

Returns: 1024000000000
1200000

2000000000

Returns: 511999279104
1111111111

1111111111

Returns: 36408647843896
536870911

536870911

Returns: 288230375614840832
1900000001

1900000001

Returns: 124517645043714
1073741824

1000000000

Returns: 1000000000
1237

10001

Returns: 639490
1987654321

1234567890

Returns: 161817187993860
1000000000

1000000000

Returns: 8191582675968
1998789724

1998775234

Returns: 130990203002882
1048575

1048575

Returns: 1099510579200
1073741823

1000000000

Returns: 1073741824000000000
1879048191

2000000000

Returns: 2147483648000000000
1228033170

1999999999

Returns: 8191140737901
1923453245

213421343

Returns: 13986566375106
1000000

2000000000

Returns: 255999381504
200000987

30

Returns: 6688
2000000000

1999999999

Returns: 16383165350911
183631871

183631871

Returns: 1540415606882304
1900000001

2000000000

Returns: 131071702204416
1073741823

111

Returns: 119185342464
12703918

1000000000

Returns: 4095992135680
1023

2000000000

Returns: 2048000000000
4879451

7891542

Returns: 32322388640
1073741535

1073741773

Returns: 288230362193068064
1073741823

1999999999

Returns: 2147483646926258176
2048

5

Returns: 5
1073741824

1999999999

Returns: 3073741823
45345

200300

Returns: 12796568
1073741802

1073741823

Returns: 144115187002114069
1073741824

1

Returns: 1
750139004

575013601

Returns: 75368090419201
1073741823

1971764517

Returns: 2117166028982059008
3

2000000000

Returns: 8000000000
111111111

2000000000

Returns: 524288000000000

Statistics

Problem Statement for "BitwiseEquations"

Problem Statement

Definition

Constraints

Examples