Problem Statement
A two-dimensional array of integers is positive if the sum of all elements in each row and each column is strictly greater than zero.
For example, the following array is positive:
2 1 -1 -1 2 2
, while the next one is not:
1 1 -1 -1 2 2
(the sum of the elements in the first column is 0).
You will be given a String[] data, representing a 2-d array. The j-th character of the i-th element of data represents the j-th number in the i-th row of the array. Digits ('0'-'9') denote numbers between 0 and 9, lowercase letters ('a'-'z') denote numbers between 10 and 35, respectively, and uppercase letters ('A'-'Z') denote negative numbers between -1 and -26, respectively. For example, 'a' represents 10, 'c' represents 12, 'A' represents -1 and 'Z' represents -26.
In one move you are allowed to change the signs of all numbers in some row or column (i.e., multiply all numbers in a row or in a column by -1). Return the minimal number of moves you'll need to get a positive array, or -1 if this is impossible.
Definition
- Class:
- PositiveArray
- Method:
- countMoves
- Parameters:
- String[]
- Returns:
- int
- Method signature:
- int countMoves(String[] data)
- (be sure your method is public)
Constraints
- data will contain between 1 and 18 elements, inclusive.
- Each element of data will contain between 1 and 18 characters, inclusive.
- Each element of data will contain only digits ('0'-'9') or letters ('a'-'z', 'A'-'Z').
- All elements of data will have the same length.
Examples
{"12"}Returns: 0
The input array is already positive.{"aB"}Returns: 1
We change signs in the last column and get a positive array.{"Z2","21"}Returns: 2
We can not succeed with less than 2 moves. One of the possible solutions is to reverse the first row and the last column.{"Z9", "99"}Returns: -1
Back to all problems