How to check if an array can become a "zero array"?

Question

Given an array of integers, you can repeatedly choose 2 different random entries (not necessarily adjacent) in the array and then subtract 1 from each. Doing this, some arrays can be transformed into arrays of all zeros, while some can't. How can I check if an array can be transformed into an array of zeros? I don't know where to start.

Example, give an array: [1, 2, 1, 1]

Choose 1, 2 then minus 1 unit -> [0, 1, 1, 1]
Choose 1, 1 then minus 1 unit -> [0, 0, 0, 1]
=> [0, 0, 0, 1] is not a zero array

Another example of an array can become a zero array: [1, 1, 2, 2]

Choose 1, 1 then minus 1 unit -> [0, 0, 2, 2]
Choose 2, 2 then minus 1 unit -> [0, 0, 1, 1]
Choose 1, 1 then minus 1 unit -> [0, 0, 0, 0]
=> [0, 0, 0, 0] is a zero array

If you're allowed to pick any two indexes (question states "random"), why can `[1, 2, 3, 4]` not become a zero array? `[1, 2, 3, 4]` -> `[1, 1, 3, 3]` -> `[1, 1, 2, 2]` -> `[1, 1, 1, 1]` -> `[0, 0, 1, 1]` -> `[0, 0, 0, 0]` — Robby Cornelissen, Oct 01 '21 at 09:11
I think an algorithm might be: pick the largest and second (or joint) largest non-zero elements; subtract one from each; repeat. e.g. `1234 -> 1223 -> 1212 -> 1111 -> 0011 -> 0000`. — Andy Turner, Oct 01 '21 at 09:52
What is `i != j`? And what does "then minus 1 unit and can do many times" mean? — Randomness Slayer, Oct 01 '21 at 09:55
How can one choose 1,1 if `i != j`? Both as indices and as values, neither is unique they equal eachother. — Randomness Slayer, Oct 01 '21 at 09:58
Wouldn't it be a solution to simply add up all of the array elements and see if the sum is even? Or is there something that you are not telling us. — Stephen C, Oct 01 '21 at 10:25
And, no, your example does not explain. (Examples only illustrate ... or prove a particular model is incorrect. They don't / can't prove that a model is correct.) If you are going to explain, you need to *explain*. — Stephen C, Oct 01 '21 at 10:28
@Stephen C Thank you for your feedback, I will try to improve the question — Đức Long, Oct 01 '21 at 10:30
@StephenC you can only subtract from array elements (you can't add to them); since you want to see if you can make all array elements in the array zero, you don't want to touch an element once it's become zero. Since there is no other non-zero element in the array `[0,2]`, other than 2, no pair exists for you to subtract from. As such, no operation can be performed, you're finished, and because the resulting array has at least one non-zero element, it's not a zero array. — Andy Turner, Oct 01 '21 at 10:51
@AndyTurner - Like I said ... I understand why my solution doesn't work — Stephen C, Oct 01 '21 at 10:52
@StephenC but you had previously asked for an explanation of the example. — Andy Turner, Oct 01 '21 at 10:52

score 2 · Answer 1 · edited Oct 01 '21 at 12:53

2

Here's a heuristic implementation:

An array can become a zero array if the sum of its values is an even number, and if the largest value is not larger than the sum of the other values.

Implementation:

import java.util.Arrays;

public class ZeroArrays {
    private static boolean isZeroArray(int[] array) {
        int sum = Arrays.stream(array).sum();
        int max = Arrays.stream(array).max().orElseThrow();

        return sum % 2 == 0 && sum - max >= max;
    }

    // test code
    public static void main(String[] args) {
        int[][] arrays = new int[][] {
                {1, 2, 3, 4},
                {1, 2, 1, 1}
        };

        for (int[] array: arrays) {
            System.out.println(Arrays.toString(array));
            System.out.println(isZeroArray(array) ? "> Zero array"
                                                  : "> Non-zero array");
        }
    }
}

_{(Note: I opted for readability. Performance can be further improved by converting the two stream operations to one simple loop. Also, I assume that all array values are non-negative.)}

edited Oct 01 '21 at 12:53

Andy Turner

137,514
11
162
243

answered Oct 01 '21 at 08:42

Robby Cornelissen

91,784
22
134
156

"An array can become a zero array where the sum of its values is an even number." You mean, like [1,2,3,4]? – Andy Turner Oct 01 '21 at 08:43
What about `[2]`? – khelwood Oct 01 '21 at 08:44
@AndyTurner Sure. `[1, 2, 3, 4]` -> `[1, 1, 3, 3]` -> `[1, 1, 2, 2]` -> ... You get the drift – Robby Cornelissen Oct 01 '21 at 08:45
@khelwood OK, any array with at least two elements. – Robby Cornelissen Oct 01 '21 at 08:45
@RobbyCornelissen OK, then what about `[0,2]`? Or even `[1,3]`? – khelwood Oct 01 '21 at 08:45
So yeah, I had to add an additional condition. I've tested this with randomly generated arrays against [my other answer](https://stackoverflow.com/a/69404117/3558960) and get matching results. Probably worthwhile to test it against @AndyTurner's answer as well. – Robby Cornelissen Oct 01 '21 at 12:14
@khelwood I think I addressed your concerns. Better late than never :) – Robby Cornelissen Oct 01 '21 at 12:30
@RobbyCornelissen I'd consider an empty array to be a zero array: it contains no non-zero elements. So I think using `max = ... .orElse(0);` would work. – Andy Turner Oct 01 '21 at 12:35
@AndyTurner Fair point. I kind of ignored input validation, and started from the premise that arrays would have a length of at least 2, and would have non-negative values, but I'll apply the fix. – Robby Cornelissen Oct 01 '21 at 12:38
@RobbyCornelissen Yep, good adjustment. – khelwood Oct 01 '21 at 13:16

Andy Turner · Accepted Answer · 2021-10-01T10:35:51.807

I think an algorithm could be to pick the pair based on the largest and second- (or joint-) largest element.

// Assuming in.length > 1.
Arrays.sort(in);
while (in[in.length - 1] != 0 && in[in.length - 2] != 0) {
  // Decrement the elements.
  --in[in.length-1];
  --in[in.length-2];

  // Restore the sorted order
  // (could do this by bubbling the changed elements, done with sort for clarity)
  Arrays.sort(in);
}

if (in[in.length - 1] == 0) {
    System.out.println("Is a zero array");
} else {
    System.out.println("Not a zero array");
}

Trying with the inputs in the question Ideone:

[1, 2, 1, 1] is not a zero array
[1, 2, 3, 4] is a zero array
[1, 1, 2, 2] is a zero array

And another:

[1, 1, 2] is a zero array (112 -> 011 -> 000)

Actually, full sorting isn't necessary, since you're only interested in the values in the last 2 positions in the array.

void zero(int[] in) {
  if (in.length > 1) {
    restore(in);

    while (in[in.length - 1] != 0 && in[in.length - 2] != 0) {
      --in[in.length-1];
      --in[in.length-2];

      restore(in);
    }
  }

  if (in.length == 0 || in[in.length - 1] == 0) {
    System.out.println("Is a zero array");
  } else {
    System.out.println("Not a zero array");
  }
}

void restore(int[] in) {
  // Find the largest element in the array, swap with the last element.
  int largest = largestIndex(in, 0, in.length);
  swap(in, largest, in.length-1);

  // Find the largest element in the array, excluding last element, swap with the second-last element.
  int second = largestIndex(in, 0, in.length-1);
  swap(in, second, in.length-2);
}

void swap(int[] in, int i, int j) {
  int tmp = in[i];
  in[i] = in[j];
  in[j] = tmp;
}

int largestIndex(int[] in, int from, int to) {
  int result = from;
  for (int i = from + 1; i < to; ++i) {
    if (in[i] > in[result]) result = i;
  }
  return result;
}

this answer really helpful with me, easy to understand – Đức Long Oct 01 '21 at 10:17 — Đức Long, Oct 01 '21 at 10:17
Aaah should have thought to sort. Very elegant +1 – Robby Cornelissen Oct 01 '21 at 10:27 — Robby Cornelissen, Oct 01 '21 at 10:27

Robby Cornelissen · Answer 3 · 2021-10-01T12:07:39.710

Here's a brute-force approach:

Find the indexes of the two highest values (peaks).
If the values at both indexes are 0, it's a zero array.
If the value at only one index is 0, it's a non-zero array.
Otherwise subtract one from both values and try again.

Implementation:

import java.util.Arrays;

public class ZeroArrays {
    private static boolean isZeroArray(int[] array) {
        while (true) {
            int[] peaks = peaks(array);
            int first = peaks[0];
            int second = peaks[1];

            if (array[first] == 0 && array[second] == 0) {
                return true;
            }

            if (first == second || array[first] == 0 || array[second] == 0) {
                return false;
            }

            array[first]--;
            array[second]--;
        }
    }

    private static int[] peaks(int[] array) {
        int first = -1, second = -1;

        for (int i = 0; i < array.length; i++) {
            if (first == -1 || array[i] > array[first]) {
                second = first;
                first = i;
            } else if (second == -1 || array[i] > array[second]) {
                second = i;
            }
        }

        return new int[]{first, second};
    }

    public static void main(String[] args) {
        int[][] arrays = new int[][] {
                {1, 2, 3, 4},
                {1, 2, 1, 1}
        };

        for (int[] array: arrays) {
            System.out.println(Arrays.toString(array));
            System.out.println(isZeroArray(array) ? "> Zero array"
                                                  : "> Non-zero array");
        }
    }
}

You can check the answer of Andy, this answer is easy to understand for me https://stackoverflow.com/a/69404105/13919785 — Đức Long, Oct 01 '21 at 10:19

How to check if an array can become a "zero array"?

3 Answers3