CODEWITHSUNDEEP
javaarrays
tony19
tony19

Reputation: 138256

How does this Java code snippet "work"?

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?

Upvotes: 1

Views: 627

Answers (3)

nhahtdh
nhahtdh

Reputation: 56809

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.

Upvotes: 2

sperumal
sperumal

Reputation: 1519

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.

Upvotes: 1

dlev
dlev

Reputation: 48596

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.

Upvotes: 7

Related Questions