diff options
| author | Abigail <abigail@abigail.be> | 2021-01-27 17:14:54 +0100 |
|---|---|---|
| committer | Abigail <abigail@abigail.be> | 2021-01-27 17:14:54 +0100 |
| commit | 1cf50661eec1020927b95eeacd21c9f5ee650fc6 (patch) | |
| tree | 0ec9f620ab3a2be463b2070472f7b001c1756f15 | |
| parent | 87492b8eeeb02a6325f056662b07cf9e773930a2 (diff) | |
| download | perlweeklychallenge-club-1cf50661eec1020927b95eeacd21c9f5ee650fc6.tar.gz perlweeklychallenge-club-1cf50661eec1020927b95eeacd21c9f5ee650fc6.tar.bz2 perlweeklychallenge-club-1cf50661eec1020927b95eeacd21c9f5ee650fc6.zip | |
Add algorithm notes to README
| -rw-r--r-- | challenge-097/abigail/README.md | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/challenge-097/abigail/README.md b/challenge-097/abigail/README.md index 50e3627151..30c09a9877 100644 --- a/challenge-097/abigail/README.md +++ b/challenge-097/abigail/README.md @@ -43,6 +43,26 @@ You are given a binary string `$B` and an integer `$S`. Write a script to split the binary string `$B` of size `$S` and then find the minimum number of flips required to make it all the same. +### Notes +We will be reading the strings from STDIN. The number of sections +will be passed in as an option: -s SECTIONS. + +To calculate the mininim number of flips required, note that we +can calculate the number of flips for each position independently; +that is, flipping a bit at position $i doesn't influence how the +number of flips required for position $j, if $i != $j. + +For each position $i, we either need to flip all the 0s to 1s, +or all the 1s to 0s. To minimize the number of flips, we count +the number of 0s in each position, and compare that with the +number of 1s in that position. Then we take the minimum of 0s +and 1s, and sum this for all positions. + +There is no need to split the input string into chunks, +we can leave it as is. The $i-th character of the $j-th section +is as position $j * $s_len + $i, where $s_len is the length +of a section. + ### Examples #### Example 1 ~~~~ |
