Statistics

Problem Statement for "DoubleXor"

Problem Statement

Let us introduce a new operation called double xor, and use the operator ^^ to denote it. For two integers A and B, A ^^ B is calculated as follows. Take the decimal representations of A and B. If they have different lengths, prepend the shorter one with leading zeros until they both have the same length. Then, label the digits of A as a1, a2, …, an (from left to right) and the digits of B as b1, b2, ... , bn (from left to right). C = A ^^ B will consist of the digits c1, c2, ... , cn (from left to right), where ci = (ai ^ bi) % 10, where ^ is the usual bitwise XOR operator (see notes for exact definition) and x % y is the remainder of x divided by y. If C happens to have any extra leading zeroes, they are ignored.
For example, 8765 ^^ 2309 = 462 (c1 = (8 ^ 2) % 10 = 10 % 10 = 0, c2 = (7 ^ 3) % 10 = 4 % 10 = 4, c3 = (6 ^ 0) % 10 = 6 % 10 = 6, c4 = (5 ^ 9) % 10 = 12 % 10 = 2), and 5 ^^ 123 = 126 ("5" is prepended with two leading zeros to become "005").
When multiple ^^ operations occur in an expression, they must be evaluated from left to right. For example, A ^^ B ^^ C means (A ^^ B) ^^ C.
You are given an int N. Return the value of N ^^ (N - 1) ^^ (N - 2) ^^ … ^^ 1.

Definition

Class:
DoubleXor
Method:
calculate
Parameters:
int
Returns:
int
Method signature:
int calculate(int N)
(be sure your method is public)

Notes

  • If a and b are single bits then a ^ b is defined as (a + b) % 2. For two integers, A and B, in order to calculate A ^ B, they need to be represented in binary: A = (an...a1)2, B = (bn...b1)2 (if the lengths of their representations are different, the shorter one is prepended with the necessary number of leading zeroes). Then A ^ B = C = (cn...c1)2, where ci = ai ^ bi. For example, 10 ^ 3 = (1010)2 ^ (0011)2 = (1001)2 = 9.

Constraints

  • N will be between 1 and 1,000,000, inclusive.

Examples

  1. 1

    Returns: 1

    This is simply 1.

  2. 2

    Returns: 3

    2^^1=3

  3. 7

    Returns: 0

    7^^6^^5^^4^^3^^2^^1=0

  4. 10

    Returns: 11

  5. 100

    Returns: 100

  6. 1000

    Returns: 1000

  7. 10000

    Returns: 10000

  8. 100000

    Returns: 100000

  9. 1000000

    Returns: 1000000

  10. 9

    Returns: 1

  11. 99

    Returns: 0

  12. 999

    Returns: 0

  13. 9999

    Returns: 0

  14. 99999

    Returns: 0

  15. 999999

    Returns: 0

  16. 1

    Returns: 1

  17. 11

    Returns: 0

  18. 111

    Returns: 0

  19. 1111

    Returns: 0

  20. 11111

    Returns: 0

  21. 111111

    Returns: 0

  22. 22

    Returns: 23

  23. 222

    Returns: 223

  24. 2222

    Returns: 2223

  25. 22222

    Returns: 22223

  26. 222222

    Returns: 222223

  27. 77

    Returns: 1

  28. 777

    Returns: 1

  29. 7777

    Returns: 1

  30. 77777

    Returns: 1

  31. 777777

    Returns: 1

  32. 123456

    Returns: 123012

  33. 654321

    Returns: 1

  34. 78

    Returns: 73

  35. 87

    Returns: 0

  36. 31

    Returns: 0

  37. 93

    Returns: 1

  38. 98

    Returns: 33

  39. 111

    Returns: 0

  40. 121

    Returns: 1

  41. 42

    Returns: 43

  42. 18468

    Returns: 12022

  43. 6335

    Returns: 0

  44. 26501

    Returns: 1

  45. 19170

    Returns: 13131

  46. 15725

    Returns: 1

  47. 11479

    Returns: 0

  48. 29359

    Returns: 0

  49. 26963

    Returns: 0

  50. 24465

    Returns: 1

  51. 5706

    Returns: 5303

  52. 28146

    Returns: 22103

  53. 23282

    Returns: 23223

  54. 16828

    Returns: 12222

  55. 9962

    Returns: 3323

  56. 492

    Returns: 432

  57. 2996

    Returns: 2332

  58. 11943

    Returns: 0

  59. 4828

    Returns: 4222

  60. 5437

    Returns: 1

  61. 32392

    Returns: 32332

  62. 14605

    Returns: 1

  63. 3903

    Returns: 0

  64. 154

    Returns: 111

  65. 293

    Returns: 1

  66. 12383

    Returns: 0

  67. 17422

    Returns: 13023

  68. 18717

    Returns: 1

  69. 19719

    Returns: 0

  70. 19896

    Returns: 13232

  71. 5448

    Returns: 5002

  72. 21727

    Returns: 0

  73. 14772

    Returns: 10332

  74. 11539

    Returns: 0

  75. 1870

    Returns: 1231

  76. 19913

    Returns: 1

  77. 25668

    Returns: 21222

  78. 26300

    Returns: 22300

  79. 17036

    Returns: 13032

  80. 9895

    Returns: 0

  81. 28704

    Returns: 22300

  82. 23812

    Returns: 23212

  83. 31323

    Returns: 0

  84. 30334

    Returns: 30331

  85. 17674

    Returns: 13231

  86. 4665

    Returns: 1

  87. 15142

    Returns: 11103

  88. 7712

    Returns: 7312

  89. 28254

    Returns: 22211

  90. 6869

    Returns: 1

  91. 19656

    Returns: 13212

  92. 167835

    Returns: 0

  93. 123250

    Returns: 123211

  94. 171961

    Returns: 1

  95. 447795

    Returns: 0

  96. 103076

    Returns: 103032

  97. 233496

    Returns: 233032

  98. 473304

    Returns: 433300

  99. 939228

    Returns: 333222

  100. 361836

    Returns: 321232

  101. 237160

    Returns: 233120

  102. 139062

    Returns: 133023

  103. 112219

    Returns: 0

  104. 302574

    Returns: 302131

  105. 644224

    Returns: 600220

  106. 325696

    Returns: 321232

  107. 416108

    Returns: 412102

  108. 794310

    Returns: 730311

  109. 200400

    Returns: 200000

  110. 32220

    Returns: 32220

  111. 571648

    Returns: 531202

  112. 107882

    Returns: 103223

  113. 448210

    Returns: 402211

  114. 101104

    Returns: 101100

  115. 220726

    Returns: 220323

  116. 353460

    Returns: 313020

  117. 502554

    Returns: 502111

  118. 32680

    Returns: 32220

  119. 537208

    Returns: 533202

  120. 412870

    Returns: 412231

  121. 11412

    Returns: 11012

  122. 161013

    Returns: 1

  123. 30923

    Returns: 0

  124. 38663

    Returns: 0

  125. 171985

    Returns: 1

  126. 360282

    Returns: 320223

  127. 650430

    Returns: 610031

  128. 130221

    Returns: 1

  129. 714

    Returns: 711

  130. 216306

    Returns: 212303

  131. 393120

    Returns: 333120

  132. 81175

    Returns: 0

  133. 636637

    Returns: 1

  134. 364559

    Returns: 0

  135. 287988

    Returns: 223322

  136. 415800

    Returns: 411200

  137. 203148

    Returns: 203102

  138. 289982

    Returns: 223323

  139. 9877

    Returns: 1

  140. 504060

    Returns: 500020

  141. 102

    Returns: 103

  142. 8

    Returns: 2

  143. 11736

    Returns: 11332

  144. 666

    Returns: 623

  145. 999998

    Returns: 333333

  146. 298

    Returns: 233

  147. 4

    Returns: 4

  148. 100006

    Returns: 100003

  149. 1024

    Returns: 1020

  150. 12

    Returns: 12

  151. 12346

    Returns: 12303

  152. 140

    Returns: 100

  153. 666999

    Returns: 0

  154. 927928

    Returns: 323322

  155. 14

    Returns: 11

  156. 987654

    Returns: 323211

  157. 123142

    Returns: 123103

  158. 100004

    Returns: 100000

  159. 123458

    Returns: 123013

  160. 4848

    Returns: 4202

  161. 123124

    Returns: 123120

  162. 46238

    Returns: 42233

  163. 4736

    Returns: 4332

  164. 123707

    Returns: 0

  165. 300004

    Returns: 300000

  166. 999973

    Returns: 1

  167. 156

    Returns: 112

  168. 289384

    Returns: 223320

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: