Problem Statement
Let the function F(N) be a number of ones in the binary representation of the number N. For example F(279)=5 because 279 = (100010111)2.
The sequence X is constructed using the following rules. The initial element X0 is 0, and each successive elements Xi is A * F(Xi-1) + B.
You will be given integers A, B and K. Your method should return the XK element. See examples for further explanation.
Definition
- Class:
- KthElement
- Method:
- find
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int find(int A, int B, int K)
- (be sure your method is public)
Constraints
- A will be between 0 and 1000000, inclusive.
- B will be between 0 and 1000000, inclusive.
- K will be between 1 and 1000000000, inclusive.
Examples
0
12
5
Returns: 12
The sequence is 0, 12, 12, 12... and so on.
1
7
15
Returns: 9
The sequence is 0, 7, 10, 9, 9, 9... and so on.
15
21
500000001
Returns: 51
The sequence is 0, 21, 66, 51, 81, 66, 51, 81, 66... and so on. The sequence has a period of length 3 starting from X2, so the 500000001th element will be the same as the element with index (500000001 - 2) mod 3 + 2.
79
4
700000000
Returns: 478
The sequence is 0, 4, 83, 320, 162, 241, 399, 478, 557, 399, 478, 557, 399... and so on.
293451
765339
900000000
Returns: 3993300
590
757
350
Returns: 4887
838
864
121
Returns: 8406
455
786
569
Returns: 3061
620
334
381
Returns: 4674
423
900
931
Returns: 4284
664
464
166
Returns: 3120
648
938
39
Returns: 5474
416
600
201
Returns: 2680
966
264
357
Returns: 4128
180
294
143
Returns: 1734
752920
410368
402885
Returns: 3422048
664744
449680
564517
Returns: 7097120
120442
477795
567387
Returns: 2043541
194696
596652
522681
Returns: 3127700
22373
802738
564087
Returns: 1004095
417314
163056
16981
Returns: 3501568
541320
287376
916876
Returns: 7865856
345247
707575
279441
Returns: 4160045
201228
864468
58057
Returns: 2474292
951206
54554
22575
Returns: 12420232
270400
149477
91376641
Returns: 3664677
591328
117779
57287701
Returns: 7805043
734196
377456
530212964
Returns: 10656200
907240
461884
379233541
Returns: 11348764
975264
418288
318889801
Returns: 10170928
776299
137570
48995416
Returns: 7900560
620880
377947
278619309
Returns: 8449387
378490
292702
114565761
Returns: 4077602
978350
137920
191680381
Returns: 9921420
558773
380172
81450739
Returns: 5967902
0
1
3
Returns: 1
5
0
6
Returns: 0
6
8
3
Returns: 26
4
2
10
Returns: 10
8
7
5
Returns: 47
6
8
3
Returns: 26
4
5
3
Returns: 17
0
2
7
Returns: 2
8
0
4
Returns: 0
2
6
7
Returns: 10
60
66
1
Returns: 66
34
86
1
Returns: 86
10
20
10
Returns: 40
16
54
9
Returns: 134
32
0
9
Returns: 0
80
41
5
Returns: 521
28
20
4
Returns: 104
72
50
7
Returns: 266
83
68
5
Returns: 483
42
48
1
Returns: 48
590001
718520
982346342
Returns: 6028529
277297
41473
993946237
Returns: 3369037
724218
589138
923846374
Returns: 6382882
969213
282151
993464664
Returns: 10943494
544831
662659
912236463
Returns: 6110969
792023
6928
963846465
Returns: 5551089
530945
809969
991273634
Returns: 10897924
657211
368091
971234644
Returns: 5625779
229414
589498
942636464
Returns: 1507154
732689
183023
934563456
Returns: 8242602
590001
718520
5
Returns: 9568535
277297
41473
3
Returns: 2814443
724218
589138
9
Returns: 12900844
969213
282151
11
Returns: 7066642
544831
662659
12
Returns: 8835124
792023
6928
10
Returns: 5551089
530945
809969
1
Returns: 809969
657211
368091
3
Returns: 10883467
229414
589498
2
Returns: 3571880
732689
183023
11
Returns: 9707980
0
0
1000000000
Returns: 0
0
0
1
Returns: 0
0
0
2
Returns: 0
0
1
1000000000
Returns: 1
0
1
1
Returns: 1
0
1
2
Returns: 1
1
0
1000000000
Returns: 0
1
0
1
Returns: 0
1
0
2
Returns: 0
1000000
1000000
1000000000
Returns: 8000000
1000000
1000000
999999999
Returns: 8000000
999999
1000000
1000000000
Returns: 16999984
1000000
999999
1000000000
Returns: 16999999
999999
999999
999999999
Returns: 13999986
999999
799993
999999999
Returns: 12799981
219469
524287
934754745
Returns: 3157915
542392
524287
934875475
Returns: 8660167
99999
48585
1000000000
Returns: 1148574
99998
48595
1000000000
Returns: 2048555
99997
48605
1000000000
Returns: 1148572
99996
48615
1000000000
Returns: 1048575
99994
48635
1000000000
Returns: 948581
99968
73343
1000000000
Returns: 1572863
99158
85493
1000000000
Returns: 1572863
699050
699050
1000000000
Returns: 14680050
293451
765339
999999999
Returns: 4286751
1000000
1000000
1000000000
Returns: 8000000
293451
765339
900000000
Returns: 3993300
5
12
500000000
Returns: 32
856785
789485
1000000000
Returns: 11070905
293451
765339
1000000000
Returns: 3993300
351431
751534
9787412
Returns: 6374430
79
4
700000000
Returns: 478
1
7
2
Returns: 10
15
21
1
Returns: 21