Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Minimal number of swaps

Original Problem

Goal

Given a list of 1 and 0, you must regroup all the 1 at the begin of the list in a minimum number of steps. A step is the interchange of two elements located at different positions.

The expected result is the minimum number of steps required to obtain a sorted list.
Input
Line 1: an integer N.
Line 2: a list of N numbers that can take the values 0 or 1.
Output
Line 1 : The minimum number of steps to regroup all the 1 at the beginning of the list.
Constraints
1 ≤ N < 500

Solution

A lot of tricks can be found to tackle this problem and most of them have linear complexity, so it's just a matter of elegance on how to solve it. The most intuitive idea is that we keep two pointers, for the left- and rightmost element of the array and either start searching for a one on the right that gets integrated into the first zero-spot on left or vice versa that we search for a zero on the left that is moved to the right.

An alternative idea is that we count the number of ones and check how many zeros are currently in the block where we would expect ones. This reduces the effort of the implementation to the following few lines:

var n =+readline();
var a = readline().split(" ");
var o = 0;
var s = 0;

for (var i = 0; i < n; i++) {
  if (a[i] === "1") o++;
}
for (var i = 0; i < o; i++) {
  if (a[i] === "0") s++;
}
print(s);

« Back to problem overview