How does this Java code snippet "work"?

Question

The Java interview question is:

Without using a temporary buffer, separate the 0's and 1's from an array, placing all 0's to the left and 1's to the right. Print the result as a string. For example, given {0,1,1,0,0,1}, the output is "000111".

And an answer is:

public class ZeroOneSeparator {

    public static void zeroOneSeparator(int[] inputArr){

        // for each index, store number of 1's up to the index
        for (int i = 1; i < inputArr.length; i++) {
            inputArr[i] = inputArr[i-1] + inputArr[i];  
        }

        // This is the "magical math" block I don't understand.
        // Why does this "work"?
        for (int i = inputArr.length - 1; i > 0; i--) {
            if (inputArr[i] > 0) {
                inputArr[i-1] = inputArr[i] - 1;
                inputArr[i] = 1;
            } else {
                inputArr[i-1] = 0;
            }
        }

        for (int i = 0; i < inputArr.length; i++) {
            System.out.print(inputArr[i]);
        }
    }

    public static void main(String[] args) {
        int[] inputArr1 = {1,0,1,0,1,1};
        ZeroOneSeparator.zeroOneSeparator(inputArr1);
        System.out.println();
        int[] inputArr2 = {1,1,1,0,0,0,0,0,0,1};
        ZeroOneSeparator.zeroOneSeparator(inputArr2);
        int[] inputArr3 = {}; // intentionally empty
        System.out.println();
        ZeroOneSeparator.zeroOneSeparator(inputArr3);
        int[] inputArr4 = {0,0,0,0,0,0};
        System.out.println();
        ZeroOneSeparator.zeroOneSeparator(inputArr4);
        int[] inputArr5 = {0,1,0,1,0,1,0,1};
        System.out.println();
        ZeroOneSeparator.zeroOneSeparator(inputArr5);
        int[] inputArr6 = {1,1,1,1,1,1,0,0,0,0,0};
        System.out.println();
        ZeroOneSeparator.zeroOneSeparator(inputArr6);
    }
}

I stepped through this code with a debugger, but I still don't understand why it works. Can someone please walk me through it?

@ColeJohnson: Really? What kind of sort is that? And note that the "magical block" is O(n) which would be a great sort algorithm. — Thilo
– Thilo, Commented Jul 2, 2012 at 3:43
@Thilo This particular sort only works when there are only two distinct objects in the collection. The similar "counting sort" is also O(n), though: en.wikipedia.org/wiki/Counting_sort — dlev
– dlev, Commented Jul 2, 2012 at 3:50
@dlev: If you take the whole method, you get "sorting". But the "magic block" alone (without the previous accumulator loop) cannot be called "just sorting the array". — Thilo
– Thilo, Commented Jul 2, 2012 at 3:53

dlev · Accepted Answer · 2012-07-02 03:50:01Z

Let's try an example to see what's going on. Suppose we had the following array:

0 1 1 0 1 1 0 0

The first loop (as the comment specifies) counts up the total number of 1's seen so far, where each 1 increases the count, and each 0 leaves it the same. So for our array, we end up with this:

0 1 2 2 3 4 4 4

Note that the final element of the array is now 4, which is the total number of 1s. We use that fact in the next loop.

We start at the last element, and check if it's greater than 0. If it is, then we replace that element with a 1, and then decrement that count by 1 and assign it to the previous element. We keep doing that, filling in 1s as we go, until the count reaches 0. At that point, we set each element we encounter to 0.

What's really happening here is that once we know how many 1s there are, we can "count down" from the end of the array, filling in that number of 1s. At that point, we know the rest of the elements must be 0, so we can set the rest of the elements to 0 at that point.

Visually, it looks like this (with the "current element" surrounded by []'s)

0 1 2 2 3 4 4 [4] ->
0 1 2 2 3 4 [3] 1 ->
0 1 2 2 3 [2] 1 1 ->
0 1 2 2 [1] 1 1 1 ->
0 1 2 [0] 1 1 1 1 ->
0 1 [0] 0 1 1 1 1 ->
0 [0] 0 0 1 1 1 1 ->
0 0 0 0 1 1 1 1

Note that the "countdown" seems very obvious when viewed this way.

nhahtdh · Accepted Answer · 2012-07-02 03:56:05Z

2

Since you have the count of 1's in the array at the last index, you will just loop from the back and replace it with 1's. The trick that is done in the code is that, it reduces the count of 1's and store it in the previous array element in every step, so that in the next step, it knows whether the current element is 0 or 1. It works nicely even in the case of all 1's or almost all 1's (only one 0 in the array), since the count of 1's left when it modifies the element at index 0 is just the right number.

Personally, I would record the count of 1's, derive the count of 0's and use 2 loops to print out/set the numbers in the array.

edited Jul 2, 2012 at 3:56

answered Jul 2, 2012 at 3:46

nhahtdh

56.9k15 gold badges131 silver badges164 bronze badges

Comments

sperumal · Accepted Answer · 2012-07-02 03:50:38Z

1

First for loop counts how many 1s are there to the left of each item. If the input is {0,1,1,0,0,1}, as result of counting, the input array becomes {0,1,2,2,2,3}.

The last index 3 says that there are three 1s in the list. Second for loop walks the list in reverse and marks 1 for the last three items.

answered Jul 2, 2012 at 3:50

sperumal

1,51910 silver badges14 bronze badges

Collectives™ on Stack Overflow

How does this Java code snippet "work"?

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related