BinaryFlips | Topcoder Archive

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

```
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.
```
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)
```
4
```
```
1
```
```
3
```
```
Returns: 2
```
```
3
```
```
2
```
```
5
```
```
Returns: -1
```
```
100000
```
```
100000
```
```
578
```
```
Returns: 174
```
```
0
```
```
0
```
```
1
```
```
Returns: 0
```
```
4
```
```
44
```
```
50
```
```
Returns: -1
```

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.