I need to fill a int[2000][2000]
matrix with some logic.
My code for filling array:
// n: (1 to 2000)
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
uniMatrix[i][j] = (((calc(i * j * i * j)) & 1) == 0) ? 0 : 1;
}
}
Here: i * j * i * j
is my take on getting square of i*j
.
The calc()
is a method used to get a value. Then, I check if value returned by calc()
is even or odd. If it is even, I store 0
in matrix on (i, j)
, otherwise I store 1
in it.
My calc()
function is as below:
private static int calc(int n){
// value of n=calc(1 | 2 | 3) is known
if(n < 4) return n;
// if value is present in HashMap, return it (don't calculate again)
if(map.containsKey(n)) {
return map.get(n);
}
// calculate the answer
int answer = 1 * calc(n-1) + 2 * calc(n-2) + 3 * calc(n-3);
// store it in HashMap so that we don't have to recalculate it
map.put(n, answer);
return answer;
}
Now, If n
is 13, it creates a [13x13] matrix. But, for n=14
, it throws a StackOverflowError
at map.containsKey(n)
. I need to be able to make [2000x2000] matrices.
I know that the problem might be recursion. But, is there a way around this? Can I do something with BitSets(I don't have a clue on how to do it)?
I can use other datatype matrices: String[][]
or boolean[][]
too. I can't use a library outside Java SDK/JDK.
Edit: It is not a duplicate of "What is StackOverflowError?", I know what it is, I know why they occur. I need help in finding an alternative to my approach to prevent this error.
You cannot calculate calc
for the range of values that you need. At i = j = 216
you get an integer overflow (the result of i * j * i * j
becomes negative), and so the result of calc
would likely be incorrect. Worse, your memoization map
would explode in size as well.
The good news is that you don't actually need to calculate it. Look at this expression:
uniMatrix[i][j] = (((calc(i * j * i * j)) & 1) == 0) ? 0 : 1;
You don't need the calculated value, all you need to know is if the value is even or odd. And you can know that, using simple math. The heart of the calc
implementation is this:
int answer = calc(n - 1) + 2 * calc(n - 2) + 3 * calc(n - 3);
And we know that the first 3 values are 1, 2, 3. In fact it's enough to know that they are odd, even, odd. The values that will follow after can be calculated based on simple math:
Now, let's see the first couple of values calculated by calc
, and verify the logic of deciding if the value will be odd or even:
If you notice, a repeating pattern has emerged:
even odd even even odd odd odd
Only 0 breaks the pattern, in which case the value is given as 0. As such, your implementation can be rewritten as this, with no risk of stack overflow:
int[] pattern = {0, 1, 0, 0, 1, 1, 1};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
long x = (long) i * j * i * j;
if (x < 2) {
uniMatrix[i][j] = (int) x;
} else {
uniMatrix[i][j] = pattern[(int)((x - 2) % pattern.length)];
}
}
}
For 0, since it doesn't follow the pattern, an exceptional treatment is necessary. For 1, x - 2 would be negative. Since the correct value for 0 and 1 is itself, the if (x < 2) branch is an easy way to treat these cases.