|
|
back to boardanyone in O(1) extra space? Is there a O(1) extra space solution? I tried looking up for patterns but it didn't help. Can we have a function f such that matrix[i][j] = f(i, j, n) for all valid i and j? Re: anyone in O(1) extra space? Posted by Paul 24 Feb 2023 23:41 Still takes more space than some O(N^2) solution i've found for some reasons. I am not really familiar with cpp compiler optimizations, so that might be linked ! #include <iostream> int main(int argc, char* argv[]) { int size; if (argc != 2) { scanf("%d",&size); } else { size = std::atoi(argv[1]); } int halfSquare = (size * size) / 2; int half = size / 2; int previousY0 = halfSquare - (half) - size; int previous; for (int y = 0; y < size; y++) { previous = previousY0 + (size + 1 - y); printf("\n%d ", previous); for (int x = 1; x < size; x++) { previous = previous - (size - 1 - std::max(std::abs(x - y), 1) + (x >= y)); printf("%d ", previous); } previousY0 = previousY0 + (size + 1 - y); } return 0; } |
|
|