Problem Statement
It's winter time! Time for snowmen to play some games.
Two snowmen are playing a game. In this game, the first snowman must choose a subset of the set {1, 2, ..., N}, and the second one must choose a subset of the set {1, 2, ..., M}. The following two conditions must be fulfilled:
- The two sets have an empty intersection.
- The XOR of all elements in the first set is less than the XOR of all elements in the second set.
You are given two
Definition
- Class:
- WinterAndSnowmen
- Method:
- getNumber
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int getNumber(int N, int M)
- (be sure your method is public)
Notes
- XOR (exclusive or) is a binary operation, performed on two numbers in binary notation. First, the shorter number is prepended with leading zeroes until both numbers have the same number of digits (in binary). Then, the result is calculated as follows: for each bit where the numbers differ the result has 1 in its binary representation. It has 0 in all other positions.
- For example 42 XOR 7 is performed as follows. First, the numbers are converted to binary: 42 is 101010 and 7 is 111. Then the shorter number is prepended with leading zeros until both numbers have the same number of digits. This means 7 becomes 000111. Then 101010 XOR 000111 = 101101 (the result has ones only in the positions where the two numbers differ). Then the result can be converted back to decimal notation. In this case 101101 = 45, so 42 XOR 7 = 45.
- The XOR of an empty set is 0.
Constraints
- N will be between 1 and 2000, inclusive.
- M will be between 1 and 2000, inclusive.
Examples
2
2
Returns: 4
The following 4 pairs of subsets are possible in this case: {} and {1} {} and {2} {} and {1, 2} {1} and {2}
1
1
Returns: 1
The only pair possible in this case is {} and {1}.
3
5
Returns: 74
7
4
Returns: 216
47
74
Returns: 962557390
100
47
Returns: 397941607
100
100
Returns: 777185814
1
1000
Returns: 543008985
2
1000
Returns: 447294105
7
999
Returns: 235898767
1000
1
Returns: 622406461
1000
2
Returns: 300829057
1000
7
Returns: 146762692
999
998
Returns: 960925358
1000
999
Returns: 746030702
999
1000
Returns: 743806415
458
45
Returns: 88500589
620
757
Returns: 853561107
128
256
Returns: 641524997
1000
127
Returns: 706127473
976
345
Returns: 755452670
167
578
Returns: 49051517
875
799
Returns: 928862745
777
778
Returns: 725336219
670
408
Returns: 54825960
569
471
Returns: 554116469
968
75
Returns: 657935194
7
99
Returns: 105156839
78
9
Returns: 154665468
69
96
Returns: 103232048
78
2
Returns: 715073135
1000
1000
Returns: 348131152
875
814
Returns: 333051734
769
701
Returns: 997567630
672
683
Returns: 770447126
537
593
Returns: 181662551
458
485
Returns: 572873874
311
327
Returns: 617632320
987
965
Returns: 251137297
9
875
Returns: 80054132
904
17
Returns: 813149597
875
99
Returns: 779219934
2000
2000
Returns: 11685307
1
2000
Returns: 509814861
2000
1
Returns: 403503230
497
2000
Returns: 127759632
1999
174
Returns: 562152623
2000
1754
Returns: 594691138
1793
1557
Returns: 835306647
1997
1995
Returns: 195768184
1572
1678
Returns: 648752666
1900
1775
Returns: 889778332
2000
47
Returns: 138603651
47
2000
Returns: 317958927
1485
256
Returns: 365011755
790
1171
Returns: 722039649
1999
1999
Returns: 565828266
1793
1501
Returns: 470877615
1988
1977
Returns: 864941527
1970
1978
Returns: 603919484
2000
1999
Returns: 765405632
1999
1995
Returns: 508719938
1987
1789
Returns: 553925400
1999
582
Returns: 249833431
1899
1999
Returns: 564171057