I have no idea to do this, so I need help from guys
For example, I have an array: [1, 2, 1, 1]
Choose random 2 number in array, then minus 1 unit
Can be repeated many times
Example of array not is zero 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] => not an zero array
An example of an array can become a zero array: [1, 1, 2, 2] -> [0, 0, 1, 1] -> [0, 0, 0, 0]
CodePudding user response:
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;
}
CodePudding user response:
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.)
CodePudding user response:
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");
}
}
}