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]

1. Choose 1, 2 then minus 1 unit -> [0, 1, 1, 1]
2. 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]

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

Answer 1

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.)}

Answer 2

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;
}

Answer 3

Here's a brute-force approach:

1. Find the indexes of the two highest values (peaks).
2. If the values at both indexes are 0, it's a zero array.
3. If the value at only one index is 0, it's a non-zero array.
4. 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");
        }
    }
}