Skip to content

Instantly share code, notes, and snippets.

@quadrupleslap
Created March 20, 2018 06:55
Show Gist options
  • Save quadrupleslap/01079058183c78c70d6cc382c2302175 to your computer and use it in GitHub Desktop.
Save quadrupleslap/01079058183c78c70d6cc382c2302175 to your computer and use it in GitHub Desktop.
This (probably) sucks.
#include <stdio.h>
// Should run in O(1) space (ignoring output) and O(n^3) time, assuming TCO.
int solve(int n, int x, int y) {
int k = (n - 1) * (n + 3) / 2;
if (y == 0) {
// First Row
return k - x;
} else if (y == 1) {
// Second Row
if (x == n - 1) {
return k - x - 1;
} else {
return -1;
}
} else if (y == n - 2) {
// Second-Last Row
if (x == 0) {
return k - 3*(n - 1) - 1;
} else if (x == n - 1) {
return k - 2*(n - 1) + 1;
} else {
return -1;
}
} else if (y == n - 1) {
// Last Row
return k - 3*(n - 1) + x;
} else {
// Middle
if (x == 0) {
return k - 4*(n - 1) + y;
} else if (x == 1) {
if (y == 2) {
return k - 4*(n - 1) + y - 1;
} else {
return -1;
}
} else if (x == n - 1) {
return k - (n - 1) - y;
} else if (x == n - 2) {
return -1;
} else {
return solve(n - 4, x - 2, y - 2);
}
}
return -1;
}
void main(void) {
int n, k;
printf("Enter size: ");
scanf("%d", &n);
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
k = solve(n, x, y);
if (k == -1) printf("-");
else printf("%d", k % 10);
}
printf("\n");
}
}
@williom0228
Copy link

may i ask how did u get k = (n-1)(n+3)/2 ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment