Statistics

Problem Statement for "BinaryFlips"

Problem Statement

You are playing a game where you initially have A zeros and B ones. Your goal is to end up with all ones. In each move, you must choose exactly K of the numbers and flip their values (zeros change to ones, and vice-versa). You can choose any K numbers each time, regardless of their current values or whether you have flipped them before. Return the minimal number of moves required to win the game, or -1 if it is impossible.

Definition

Class:
BinaryFlips
Method:
minimalMoves
Parameters:
int, int, int
Returns:
int
Method signature:
int minimalMoves(int A, int B, int K)
(be sure your method is public)

Constraints

  • A will be between 0 and 100,000, inclusive.
  • B will be between 0 and 100,000, inclusive.
  • K will be between 1 and 100,000, inclusive.

Examples

  1. 3

    0

    3

    Returns: 1

    You initially have 3 zeros and 0 ones, and you must flip 3 numbers in each move. Your only possible move is to flip every number. After the first move, you end up with all ones and win the game.

  2. 4

    0

    3

    Returns: 4

    This is similar to the previous example, but this time, you have 4 zeros. Here's one minimal sequence of moves that will lead to a win: 0. 0000 (the initial state) 1. 1110 (first three numbers flipped) 2. 1001 (last three numbers flipped) 3. 0100 (first, second and fourth numbers flipped) 4. 1111 (first, third and fourth numbers flipped)

  3. 4

    1

    3

    Returns: 2

  4. 3

    2

    5

    Returns: -1

  5. 100000

    100000

    578

    Returns: 174

  6. 0

    0

    1

    Returns: 0

  7. 0

    0

    2

    Returns: 0

  8. 0

    0

    99258

    Returns: 0

  9. 0

    3

    4

    Returns: 0

  10. 0

    16

    1

    Returns: 0

  11. 1

    0

    1

    Returns: 1

  12. 1

    1

    1

    Returns: 1

  13. 1

    2

    1

    Returns: 1

  14. 1

    2

    2

    Returns: -1

  15. 1

    3

    3

    Returns: 3

  16. 1

    9128

    5

    Returns: 3

  17. 2

    0

    1

    Returns: 2

  18. 2

    0

    2

    Returns: 1

  19. 2

    0

    3

    Returns: -1

  20. 2

    1

    3

    Returns: -1

  21. 2

    2

    3

    Returns: 2

  22. 2

    5

    3

    Returns: 2

  23. 2

    29292

    2175

    Returns: 2

  24. 3

    0

    2

    Returns: -1

  25. 3

    1

    2

    Returns: -1

  26. 3

    6

    7

    Returns: 3

  27. 3

    2781

    2701

    Returns: 35

  28. 4

    0

    2

    Returns: 2

  29. 4

    2

    3

    Returns: 2

  30. 4

    2

    5

    Returns: 4

  31. 4

    7

    6

    Returns: 2

  32. 4

    7

    7

    Returns: 2

  33. 4

    7

    10

    Returns: 4

  34. 4

    7

    11

    Returns: -1

  35. 4

    44

    50

    Returns: -1

  36. 5

    0

    2

    Returns: -1

  37. 5

    0

    3

    Returns: 3

  38. 5

    1

    2

    Returns: -1

  39. 5

    1

    3

    Returns: 3

  40. 5

    1

    4

    Returns: -1

  41. 5

    2

    1

    Returns: 5

  42. 5

    3

    7

    Returns: 3

  43. 6

    6

    4

    Returns: 2

  44. 6

    7

    4

    Returns: 2

  45. 6

    0

    5

    Returns: 6

  46. 6

    1

    5

    Returns: 4

  47. 6

    2

    5

    Returns: 2

  48. 6

    30000

    5

    Returns: 2

  49. 6

    8291

    8296

    Returns: 6

  50. 7

    1

    1

    Returns: 7

  51. 7

    1

    3

    Returns: 3

  52. 7

    2

    3

    Returns: 3

  53. 7

    5

    5

    Returns: 3

  54. 7

    18

    9

    Returns: 3

  55. 7

    26181

    17921

    Returns: 5

  56. 7

    98520

    56001

    Returns: 3

  57. 7

    99128

    70613

    Returns: 5

  58. 9

    1

    5

    Returns: 3

  59. 9

    82

    15

    Returns: 3

  60. 10

    6

    8

    Returns: 2

  61. 10

    7

    14

    Returns: 3

  62. 10

    7

    15

    Returns: 6

  63. 10

    7

    16

    Returns: 7

  64. 11

    1145

    16

    Returns: -1

  65. 11

    6662

    6671

    Returns: 3331

  66. 11

    99995

    99999

    Returns: 14285

  67. 27

    0

    5

    Returns: 7

  68. 27

    16

    5

    Returns: 7

  69. 40

    40

    43

    Returns: 2

  70. 40

    40

    79

    Returns: 40

  71. 42

    1

    41

    Returns: 22

  72. 42

    2

    41

    Returns: 14

  73. 42

    3

    41

    Returns: 12

  74. 42

    6

    41

    Returns: 6

  75. 42

    10

    41

    Returns: 4

  76. 42

    52891

    41

    Returns: 2

  77. 44

    77

    66

    Returns: 2

  78. 44

    77

    118

    Returns: 16

  79. 85

    5

    5

    Returns: 17

  80. 85

    66

    28

    Returns: -1

  81. 86

    22

    28

    Returns: 4

  82. 86

    0

    73

    Returns: 8

  83. 86

    4

    73

    Returns: 6

  84. 86

    86

    83

    Returns: 2

  85. 89

    7

    95

    Returns: 7

  86. 89

    8

    95

    Returns: 5

  87. 100

    1

    100

    Returns: 1

  88. 100

    1

    99

    Returns: 50

  89. 100

    92

    96

    Returns: 2

  90. 100

    93

    99

    Returns: 2

  91. 615

    9214

    2918

    Returns: -1

  92. 615

    9128

    833

    Returns: 3

  93. 615

    10000

    9999

    Returns: 17

  94. 615

    10000

    10589

    Returns: 385

  95. 680

    311

    36

    Returns: 19

  96. 682

    41

    86

    Returns: 8

  97. 712

    11

    718

    Returns: 3

  98. 1000

    0

    10

    Returns: 100

  99. 1000

    0

    101

    Returns: 10

  100. 1000

    0

    501

    Returns: 4

  101. 1000

    589

    501

    Returns: 2

  102. 1000

    1001

    1999

    Returns: 500

  103. 1000

    88290

    42929

    Returns: 2

  104. 1000

    98383

    99356

    Returns: 38

  105. 1001

    17592

    289

    Returns: 5

  106. 1001

    21789

    22696

    Returns: -1

  107. 1001

    52795

    53769

    Returns: 1957

  108. 2392

    2393

    4756

    Returns: 83

  109. 2393

    2392

    4755

    Returns: 81

  110. 7822

    0

    1

    Returns: 7822

  111. 7895

    89325

    15

    Returns: 527

  112. 8000

    3000

    6

    Returns: 1334

  113. 8000

    3000

    7

    Returns: 1144

  114. 8000

    3000

    100

    Returns: 80

  115. 8000

    3000

    7999

    Returns: 4

  116. 8000

    3000

    10781

    Returns: 38

  117. 8000

    12000

    19999

    Returns: 8000

  118. 8000

    12001

    19929

    Returns: 112

  119. 8001

    5582

    13401

    Returns: 31

  120. 8001

    63969

    65993

    Returns: 11

  121. 14298

    12912

    753

    Returns: 20

  122. 15289

    77124

    13833

    Returns: 3

  123. 16968

    44244

    60036

    Returns: 16

  124. 16968

    44244

    60282

    Returns: 20

  125. 16969

    98268

    61

    Returns: 279

  126. 16969

    98999

    9999

    Returns: 3

  127. 16969

    98999

    17930

    Returns: -1

  128. 16969

    98999

    57930

    Returns: -1

  129. 16969

    98999

    97939

    Returns: 7

  130. 22000

    65954

    794

    Returns: 28

  131. 22000

    68054

    1080

    Returns: 21

  132. 22000

    68054

    1081

    Returns: 22

  133. 22000

    68054

    3081

    Returns: 8

  134. 22000

    68054

    13084

    Returns: 2

  135. 22000

    68054

    33089

    Returns: 2

  136. 22000

    68054

    53089

    Returns: 2

  137. 22000

    68054

    87089

    Returns: 8

  138. 22000

    68054

    89012

    Returns: 22

  139. 23013

    4

    3

    Returns: 7671

  140. 23013

    4

    7

    Returns: 3289

  141. 23013

    5

    23017

    Returns: 5

  142. 23013

    8

    17

    Returns: 1355

  143. 23013

    8

    1573

    Returns: 15

  144. 23013

    50

    313

    Returns: 75

  145. 23013

    51

    77

    Returns: 299

  146. 23013

    8290

    4009

    Returns: 7

  147. 23013

    9923

    20011

    Returns: 3

  148. 23013

    9923

    29661

    Returns: 5

  149. 23013

    14111

    14111

    Returns: 3

  150. 23013

    14111

    37109

    Returns: 941

  151. 23500

    1

    23499

    Returns: 11750

  152. 23500

    2

    3

    Returns: 7834

  153. 23500

    200

    23600

    Returns: 3

  154. 23500

    24000

    47213

    Returns: 82

  155. 25000

    25000

    49692

    Returns: 82

  156. 25001

    25001

    2049

    Returns: 13

  157. 33333

    33333

    33334

    Returns: -1

  158. 33333

    33333

    33335

    Returns: 3

  159. 33333

    33333

    65783

    Returns: 39

  160. 33333

    33333

    66653

    Returns: 2565

  161. 34128

    11

    15

    Returns: 2276

  162. 34585

    1

    33

    Returns: 1049

  163. 35985

    0

    6

    Returns: -1

  164. 35985

    0

    5

    Returns: 7197

  165. 45902

    56

    57

    Returns: 806

  166. 45902

    56

    45901

    Returns: 806

  167. 45902

    56

    45931

    Returns: 1702

  168. 45902

    399

    66

    Returns: 696

  169. 45902

    399

    559

    Returns: 84

  170. 45902

    400

    600

    Returns: 77

  171. 45902

    401

    999

    Returns: 46

  172. 45902

    401

    2999

    Returns: 16

  173. 45902

    401

    7319

    Returns: 8

  174. 45902

    401

    11474

    Returns: 5

  175. 45902

    401

    11475

    Returns: 6

  176. 45902

    401

    11476

    Returns: 4

  177. 45902

    71461

    22476

    Returns: 3

  178. 45903

    100

    101

    Returns: 455

  179. 45903

    10001

    12859

    Returns: 5

  180. 45903

    89257

    15299

    Returns: 5

  181. 45903

    89257

    15300

    Returns: -1

  182. 45903

    89257

    15301

    Returns: 3

  183. 45903

    89257

    63939

    Returns: 3

  184. 45903

    89257

    68938

    Returns: -1

  185. 45903

    89257

    98937

    Returns: 3

  186. 50000

    50000

    1

    Returns: 50000

  187. 50000

    100000

    3

    Returns: 16668

  188. 50000

    33933

    76766

    Returns: 5

  189. 50001

    91285

    73593

    Returns: 3

  190. 51020

    6

    5589

    Returns: 10

  191. 66667

    33393

    9

    Returns: 7409

  192. 66667

    33393

    9588

    Returns: -1

  193. 66667

    33393

    95887

    Returns: 9

  194. 88052

    0

    2

    Returns: 44026

  195. 88052

    0

    71

    Returns: 1242

  196. 88052

    0

    129

    Returns: 684

  197. 88052

    0

    925

    Returns: 96

  198. 88052

    0

    8225

    Returns: 12

  199. 88052

    0

    25225

    Returns: 4

  200. 88052

    0

    25226

    Returns: 4

  201. 88052

    68821

    25225

    Returns: 4

  202. 93851

    0

    3

    Returns: 31285

  203. 93851

    1

    5

    Returns: 18771

  204. 93851

    1

    5001

    Returns: 19

  205. 93851

    72517

    5001

    Returns: 19

  206. 93851

    72517

    16031

    Returns: 7

  207. 100000

    10

    111

    Returns: 902

  208. 100000

    27841

    21979

    Returns: 6

  209. 100000

    68963

    9281

    Returns: 12

  210. 100000

    68963

    9282

    Returns: 11

  211. 100000

    68963

    9283

    Returns: 12

  212. 100000

    99275

    900

    Returns: 112

  213. 100000

    99275

    9100

    Returns: 11

  214. 100000

    99275

    49103

    Returns: 4

  215. 100000

    99275

    49104

    Returns: 3

  216. 100000

    99275

    59100

    Returns: 2

  217. 100000

    99925

    99999

    Returns: 2

  218. 100000

    89285

    100000

    Returns: 1

  219. 100000

    100000

    5781

    Returns: 18

  220. 100000

    100000

    15780

    Returns: 7

  221. 99999

    100000

    15781

    Returns: 7

  222. 100000

    100000

    15781

    Returns: 8

  223. 10

    1

    8

    Returns: 3

  224. 800

    48

    776

    Returns: 3

  225. 762

    118

    630

    Returns: 3

  226. 418

    155

    398

    Returns: 3

  227. 120

    25

    86

    Returns: 3

  228. 450

    82

    448

    Returns: 3

  229. 6

    0

    4

    Returns: 3

  230. 50000

    50000

    99948

    Returns: 962

  231. 100000

    100000

    99999

    Returns: 2

  232. 99999

    99999

    100000

    Returns: -1

  233. 99999

    100000

    99998

    Returns: -1

  234. 100000

    100000

    100000

    Returns: 1

  235. 50000

    50000

    13456

    Returns: 4

  236. 100000

    50001

    79001

    Returns: 2

  237. 100000

    99999

    99997

    Returns: 2

  238. 100000

    100000

    59999

    Returns: 2

  239. 100000

    100000

    91732

    Returns: 2

  240. 100000

    100000

    73536

    Returns: 2

  241. 100000

    0

    99999

    Returns: 100000

  242. 100000

    100000

    99988

    Returns: 2

  243. 100000

    100000

    9999

    Returns: 12

  244. 100000

    100000

    49999

    Returns: 4

  245. 99200

    0

    99101

    Returns: 1004

  246. 3

    5

    2

    Returns: -1

  247. 1

    99999

    99999

    Returns: 99999

  248. 100000

    100000

    49494

    Returns: 3

  249. 100000

    100000

    99998

    Returns: 2

  250. 100000

    100000

    77781

    Returns: 2

  251. 100000

    100000

    12345

    Returns: 10

  252. 100000

    100000

    99997

    Returns: 2

  253. 99998

    9999

    100000

    Returns: 3

  254. 100000

    99999

    98765

    Returns: 2

  255. 100000

    1

    99999

    Returns: 50000

  256. 99993

    99994

    12343

    Returns: 9

  257. 99998

    100000

    100000

    Returns: 2

  258. 99999

    1

    50000

    Returns: -1

  259. 85663

    91743

    87141

    Returns: 3

  260. 100000

    100000

    19999

    Returns: 6

  261. 100000

    100000

    49990

    Returns: 3

  262. 9901

    99923

    99901

    Returns: 11

  263. 0

    1000

    2000

    Returns: 0

  264. 1

    99999

    50000

    Returns: -1

  265. 100000

    100000

    34587

    Returns: 4

  266. 7

    1

    5

    Returns: 3

  267. 3

    3

    5

    Returns: 3

  268. 95274

    18257

    71605

    Returns: 4

  269. 6

    2

    4

    Returns: 2

  270. 500

    1

    499

    Returns: 250

  271. 51662

    63673

    1001

    Returns: 52

  272. 100000

    0

    97865

    Returns: 48

  273. 100000

    10000

    87879

    Returns: 6

  274. 1812

    55328

    68871

    Returns: -1

  275. 99996

    99994

    100000

    Returns: 2

  276. 67989

    83577

    70925

    Returns: 3

  277. 49998

    50002

    99998

    Returns: 25000

  278. 65213

    80521

    9299

    Returns: 9

  279. 100000

    100000

    40578

    Returns: 3

  280. 99999

    100000

    50000

    Returns: -1

  281. 98384

    98382

    98371

    Returns: 2

  282. 100000

    99999

    3

    Returns: 33334

  283. 49998

    50002

    97998

    Returns: 25

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: