9 billion names of God the integer: Difference between revisions

===Solution 1===

===Solution 2===

Clean and straightforward solution

<lang javascript>

function genTriangle(n){ // O(n^3) time and O(n^2) space

var a = new Array(n)

for (let i = 0; i < n; i++){

a[i] = new Array(i+1)

for (let j = 0; j < i; j++){

a[i][j] = 0

let s = i-j-1, k = Math.min(s, j)

while (k >= 0) a[i][j] += a[s][k--]

}

a[i][i] = 1

}

return a.map(x => x.join(" ")).join("\n")

}

function G(n){ // At least O(n^2) time and O(n) space

var a = new Array(n+1)

a[0] = 1n

for (let i = 1; i <= n; i++){

a[i] = 0n

for (let k = 1, s = 1; s <= i;){

a[i] += (k & 1 ? a[i-s]:-a[i-s])

k > 0 ? (s += k, k = -k):(k = -k+1, s = k*(3*k-1)/2)

}

}

return a[n]

}

console.log(genTriangle(25))

console.log("")

for (const x of [23, 123, 1234, 12345]){

console.log("G(" + x + ") = " + G(x))

}

</lang>

{{out}}

<pre>

1

1 1

1 1 1

1 2 1 1

1 2 2 1 1

1 3 3 2 1 1

1 3 4 3 2 1 1

1 4 5 5 3 2 1 1

1 4 7 6 5 3 2 1 1

1 5 8 9 7 5 3 2 1 1

1 5 10 11 10 7 5 3 2 1 1

1 6 12 15 13 11 7 5 3 2 1 1

1 6 14 18 18 14 11 7 5 3 2 1 1

1 7 16 23 23 20 15 11 7 5 3 2 1 1

1 7 19 27 30 26 21 15 11 7 5 3 2 1 1

1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1

1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1

1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1

1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1

1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1

1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1

1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1

1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1

1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1

1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1

G(23) = 1255

G(123) = 2552338241

G(1234) = 156978797223733228787865722354959930

G(12345) = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

</pre>