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.

## Overview

Just like in this weeks other challenge, we will use a command line parameter. We will use `-s SIZE`

to indicate the size of the substrings. The binary strings will be read from standard input.

To calculate the minimum number of flips required, note that flipping a bit on position `i`

of a sub string has no bearing on the flips required in any other position. So we can calculate the minimum number of flips required for each position `i`

independently, and sum the totals.

To calculate the minimum number of flips required for a specific position `i`

, we calculate the number of `0`

s in position `i`

in all the sub strings. Given the number of `0`

s, we can calculate the number of `1`

s as both numbers should add up to the number of sub strings (and that number can be easily calculate by dividing the length of the binary string with the length of the sub strings). Now, the minimum number of flips required is the minimum of the number of `0`

s and the number of `1`

s. Observe that is may be possible we end up flipping to a string which is not one of the sub strings. Consider the binary string `111011011011`

, and sub string length of `4`

. Then we get the following sub strings:

```
1110
1101
1011
```

It requires flipping two bits to change one of the sub string to any of the others, so four flips would be required if the target where any of the sub strings. However, if we just flip the `0`

bits, all sub strings end up being `1111`

, and only three flips are required.

Note that we don’t have to split the binary string into sub strings to calculate the number of flips. We can just leave the binary string as is, and use a simple formula. The bit at position `i`

of sub string `j`

, is at position `j * size + i`

, where `size`

is the given length of the sub strings. For languages which index strings starting from index `1`

, the formula is `j * size + i + 1`

.

# Solutions

We will not be showing any code related to parsing command line options. This is the same as for the other challenge of this week. In each language, we will have a variable `size`

(or `$size`

) which will contain the value passed in.

The implementation in each language is almost identical, except for some syntax variation.

## Perl

while (<>) { chomp; my $sections = length () / $size; my $sum = 0; for my $i (0 .. $size - 1) { my $zeros = 0; for my $j (0 .. $sections - 1) { my $index = $j * $size + $i; $zeros ++ if substr ($_, $index, 1) eq "0"; } my $ones = $sections - $zeros; $sum += min ($zeros, $ones); } say $sum; }

For each position `i`

, we count the number of `0`

on that position. We then calculate the number of `1`

s in that position, and sum the minimum of the two.

Find the complete program on GitHub.

## AWK

{ sum = 0 sections = length ($0) / size for (i = 0; i < size; i ++) { zeros = 0; for (j = 0; j < sections; j ++) { indx = j * size + i + 1 # Can't use 'index' as a variable if (substr ($0, indx, 1) == "0") { zeros ++ } } ones = sections - zeros sum += zeros < ones ? zeros : ones } print sum }

Find the complete program on GitHub.

## Bash

while read line do sections=$((${#line} / $size)) sum=0 for ((i = 0; i < size; i ++)) do zeros=0 for ((j = 0; j < sections; j ++)) do index=$(($j * $size + $i)) if [ "${line:$index:1}" == "0" ] then zeros=$(($zeros + 1)) fi done ones=$(($sections - $zeros)) sum=$(($sum + ($zeros < $ones ? $zeros : $ones) )) done echo $sum done

Find the complete program on GitHub.

## C

while ((strlen = getline (&line, &len, stdin)) != -1) { strlen --; /* We don't care about the newline */ int sections = strlen / size; int sum = 0; for (int i = 0; i < size; i ++) { int zeros = 0; for (int j = 0; j < sections; j ++) { int index = j * size + i; if (line [index] == '0') { zeros ++; } } int ones = sections - zeros; sum += zeros < ones ? zeros : ones; } printf ("%d\n", sum); } free (line);

Find the complete program on GitHub.

## Lua

for line in io . lines () do local sections = #line / size local sum = 0 for i = 0, size - 1 do local zeros = 0 for j = 0, sections - 1 do index = j * size + i + 1 if string . sub (line, index, index) == "0" then zeros = zeros + 1 end end local ones = sections - zeros if zeros < ones then sum = sum + zeros else sum = sum + ones end end io . write (sum, "\n") end

Find the complete program on GitHub.

## Node.js

require ('readline') . createInterface ({input: process . stdin}) . on ('line', _ => { let sum = 0 let sections = _ . length / size for (let i = 0; i < size; i ++) { let zeros = 0 for (let j = 0; j < sections; j ++) { let index = j * size + i; if (_ . substring (index, index + 1) == "0") { zeros ++ } } let ones = sections - zeros sum += zeros < ones ? zeros : ones } console . log (sum) });

Find the complete program on GitHub.

## Python

for line in fileinput . input (): sections = len (line) / size sum = 0 for i in range (size): zeros = 0 for j in range (sections): index = j * size + i if line [index : index + 1] == "0": zeros += 1 ones = sections - zeros sum += min (zeros, ones) print (sum)

Find the complete program on GitHub.

## Ruby

ARGF . each_line do |line| sections = (line . length - 1) / size sum = 0 for i in 0 .. size - 1 do zeros = 0 for j in 0 .. sections - 1 do index = j * size + i if line [index, 1] == "0" then zeros += 1 end end ones = sections - zeros sum += [zeros, ones] . min end puts sum end

Find the complete program on GitHub.