I didn't expect this problem to hide such a nice arithmetic sum. My approach is fundamentally similar to Kyle's, but takes a different approach to the proof, so I'll write my solution in the reply to this comment. I didn't make a full implementation (might come back to that later), but this should be implementable in just a few lines of code.
Edit: Added implementation to below comment if anybody is interested
The lines in the graphic were actually a bit deceiving to me at first. I spent a few minutes thinking about to solve by tracing along the lines. But, then I realized that if we actually ignore the lines entirely, we can visualize this as a series of larger and larger squares expanding from the origin. Once I saw this, I reduced the problem to mapping n to one of the squares, because I knew that some arithmetic would yield the answer after.
Let's define the kth square as the square with its top-right corner at (k,k). Well, how can we determine how many points came before it? Sum the perimeters of the smaller squares! Since it's an integer spiral, we can see that each square's side length increases by 2 from the previous. This means that the top right point of the kth square is the nth point with
An arithmetic sum! A very clever 5-year old Gauss tells us that the sum of the first k natural numbers is k(k+1)/2, so 8 times that is 4k(k+1).
So, how can we use this information? Now that we know spiral(4k(k+1) = (k,k), then for any given n, we can find k with Math.floor(Math.sqrt(n/4)). If we take n - 4k(k+1), we know how many points along the square to move. Luckily, this can be easily done with some arithmetic instead of a for-loop. So, the time complexity is O(1), because we only need to perform a few arithmetic operations for any case.
The advantage of this approach is that the inverse case is very easy! If the point at (x,y) is on the kth square, then k = max(abs(x), abs(y)). Since the top right corner of the kth square is the 4k(k+1)-th point and is at (k,k), that's all the info we need to get n, after some similar arithmetic to above.
Two notes:
1) Math.sqrt() can be considered constant time assuming that numbers do not contain arbitrarily many bits
2) There are a few ways to handle n=0 with algebra tweaks, but I think the simplest is to just hard-code it
Definitely a great problem! It invokes good use of pattern analysis and mathematical thinking. I will write my solutions for both problems in reply to this comment.
When I solved the first problem, I quickly thought of the pattern being related to triangle numbers, since the top-left corners you represent doubled triangle numbers of odd numbers and the bottom-right corners represent doubled triangle numbers of even numbers.
-- STEPS --
1) Find the formula for double triangle numbers: y = x^2 + x
2) To find where n would be in the spiral, we need to see which double triangle number is just above it. Thus we derive a formula for a positive inverse of the double triangle number formula.
y = x^2 + x ==> (Algebra) ==> x = \sqrt{4y + 1}/2 - 1/2
3) For n, we get its double-triangle-number-inverse and then find the ceiling integer upper bound of it. We will call this number "ubRoot"
4A) If the ubRoot is odd, then we start from the top-left, then go right (or right+down)
4B) If the ubRoot is even, then we start from the bottom-right, then go left (or left+up)
5) The x and y of the top-left or bottom-right corner fulfills (x = -y) and it is equal to if the ubRoot is the mth odd / even positive integer. The length m is the x and y distance from the origin of the top-left or bottom-right corner.
6) The time complexity for this is O(1)
-- Code (You can prettify this and run into on a compiler like JS Programiz Compiler to test) --
// I started this at 1/24/2025 9:46pm
// I finished at 1/24/2025 10:21pm
/*
BRAINSTORM:
-- My thoughts during the process --
0 => (0,0)
Then it goes up 1, left 1,
Then down 2, right 2,
Then up 3, left 3,
Then down 4, right 4
That seems to be the pattern
This reminds me of triangle numbers: T(n) = ((n^2 + n)) / 2
In fact, the top left and bottom right corners indicate double triangle numbers
We can maybe get an inverse of triangle numbers from this
Let's say I picked 101, what is the triangle number just above
it?
I can make Triangle Numbers into a continuous function and
When solving the 2nd problem, I looked at the point, found which edge of the spiral it would be in, and then used the logic from my previous formulas to calculate n.
-- STEPS --
1) Find the edge type of (or what direction is the spiral moving at) the point
2) From there, remember top-left-corners signify a double-triangle-number of an odd number, whilst bottom-right corners signifiy a double-triangle-number of an even number
3A) If the point is at a TOP or RIGHT edge, find the distance it would take to get to the top-left corner
3B) If the point is at a BOTTOM or LEFT edge, find the distance it would take to get to the bottom-right corner
4) Calculate the double-triangle-number based on the corner-type and the length of the x (which is always equal to the length of the y)
5) Subtract the distance traveled to that corner, and you have n
[Time Complexity: This is, of course, O(1) time!]
-- Note --
There was a tiny caveat that influenced me to take a little more time solving this problem. A point on the RIGHT edge of the spiral has 1 less X than the absolute value of the X and the Y of the top-left edge. This -1 made me have to adjust some calculations.
This property was not present in the TOP, BOTTOM, or LEFT edges.
-- Code (You can prettify this and run into on a compiler like JS Programiz Compiler to test) --
// Spiral Function PART 2 -- [x,y] = n
// I started this at 1/24/2025 10:35pm
// Finished at 1/24/2025 11:16pm
/*
BRAINSTORM:
I just wrote my reply to the Part #1 of Spiral Inverse. Now
it is 10:35pm and I'm writing for Part #2.
[x, y] => n
-- Please read my logic from Part #1 to understand this --
The top-left corner [-2,2] would map to 12
The bottom-right [2,-2] would map to 20
-- Approach --
1) Let all points be part of 4 categories of a spiral's edge:
I) A top-edge (including both corners)
II) A right-edge (excluding the corners)
III) A bottom-edge (including both corners)
IV) A left-edge (excluding the corners)
2) We can use logic from the x and y to determine which edge a
point is on
(E.G.) If it is (2,5) the y-value is much higher than +2 so it must be on the top-edge
3A) From here, edges I and II are preceding the spiral point to the top-left, so we determine the top-left upper bound point
3B) Edges III and IV are preceding the spiral point on the
bottom-right, so we determine the bottom-right UB point
4) Once we determine the UB point, we use its length to get
the UB root using the inverse of the formula from Part #1
5) We then calculate the di-triangle number from the UB Root
and the subtract the distance traveled to get to the
UB point from our given point
6) BOOM! O(1) Time!
*/
// MAIN FUNCTION
const spiralFunctionInverse = (point) => {
// Get the coordinates
const x = point[0]
const y = point[1]
// Handle zero case
if (x === 0 && y === 0) {
return 0
}
// Get the absolute value of coordinates
const absX = Math.abs(x)
const absY = Math.abs(y)
/** For the sake of speed (pretending this is an interview
* problem), I will handle the edge cases,
* case-by-case, but in a production setting I will have more
* time to leverage code-reuse **/
// Find the edge type
let edgeType = null
// Handle the top and bottom edges
// Caveat: Right edges have 1 less x than the UB length
I didn't expect this problem to hide such a nice arithmetic sum. My approach is fundamentally similar to Kyle's, but takes a different approach to the proof, so I'll write my solution in the reply to this comment. I didn't make a full implementation (might come back to that later), but this should be implementable in just a few lines of code.
Edit: Added implementation to below comment if anybody is interested
------- Solution Below -------
The lines in the graphic were actually a bit deceiving to me at first. I spent a few minutes thinking about to solve by tracing along the lines. But, then I realized that if we actually ignore the lines entirely, we can visualize this as a series of larger and larger squares expanding from the origin. Once I saw this, I reduced the problem to mapping n to one of the squares, because I knew that some arithmetic would yield the answer after.
Let's define the kth square as the square with its top-right corner at (k,k). Well, how can we determine how many points came before it? Sum the perimeters of the smaller squares! Since it's an integer spiral, we can see that each square's side length increases by 2 from the previous. This means that the top right point of the kth square is the nth point with
n = 4*2 + 4*(2+2) + ... 4*(2k) = 8(1) + 8(2) + ... 8k = 8(1 + 2 + ... + k)
An arithmetic sum! A very clever 5-year old Gauss tells us that the sum of the first k natural numbers is k(k+1)/2, so 8 times that is 4k(k+1).
So, how can we use this information? Now that we know spiral(4k(k+1) = (k,k), then for any given n, we can find k with Math.floor(Math.sqrt(n/4)). If we take n - 4k(k+1), we know how many points along the square to move. Luckily, this can be easily done with some arithmetic instead of a for-loop. So, the time complexity is O(1), because we only need to perform a few arithmetic operations for any case.
The advantage of this approach is that the inverse case is very easy! If the point at (x,y) is on the kth square, then k = max(abs(x), abs(y)). Since the top right corner of the kth square is the 4k(k+1)-th point and is at (k,k), that's all the info we need to get n, after some similar arithmetic to above.
Two notes:
1) Math.sqrt() can be considered constant time assuming that numbers do not contain arbitrarily many bits
2) There are a few ways to handle n=0 with algebra tweaks, but I think the simplest is to just hard-code it
------ Implementation below ------
if n == 0:
return (0,0)
j = floor(sqrt(n/4))
k = j+1 if 4*(j * (j+1)) < n else j
side_length = 2*k
end_of_prev_square = 4*k**2 - 4*k
progress_along_square = n - end_of_prev_square
progress_along_side = progress_along_square % (side_length)
if side_length > progress_along_square: #on top side
return (k - progress_along_side, k)
elif 2*side_length > progress_along_square: #on left side
return (-k, k - progress_along_side)
elif 3*side_length > progress_along_square:#on bottom side
return (-k + progress_along_side, -k)
elif 4*side_length > progress_along_square: #on right side
return (k, -k + progress_along_side)
else:
return (k,k)
Definitely a great problem! It invokes good use of pattern analysis and mathematical thinking. I will write my solutions for both problems in reply to this comment.
--Do not look if you are still solving--
-- SOLUTION for 1st Problem --
When I solved the first problem, I quickly thought of the pattern being related to triangle numbers, since the top-left corners you represent doubled triangle numbers of odd numbers and the bottom-right corners represent doubled triangle numbers of even numbers.
-- STEPS --
1) Find the formula for double triangle numbers: y = x^2 + x
2) To find where n would be in the spiral, we need to see which double triangle number is just above it. Thus we derive a formula for a positive inverse of the double triangle number formula.
y = x^2 + x ==> (Algebra) ==> x = \sqrt{4y + 1}/2 - 1/2
3) For n, we get its double-triangle-number-inverse and then find the ceiling integer upper bound of it. We will call this number "ubRoot"
4A) If the ubRoot is odd, then we start from the top-left, then go right (or right+down)
4B) If the ubRoot is even, then we start from the bottom-right, then go left (or left+up)
5) The x and y of the top-left or bottom-right corner fulfills (x = -y) and it is equal to if the ubRoot is the mth odd / even positive integer. The length m is the x and y distance from the origin of the top-left or bottom-right corner.
6) The time complexity for this is O(1)
-- Code (You can prettify this and run into on a compiler like JS Programiz Compiler to test) --
// I started this at 1/24/2025 9:46pm
// I finished at 1/24/2025 10:21pm
/*
BRAINSTORM:
-- My thoughts during the process --
0 => (0,0)
Then it goes up 1, left 1,
Then down 2, right 2,
Then up 3, left 3,
Then down 4, right 4
That seems to be the pattern
This reminds me of triangle numbers: T(n) = ((n^2 + n)) / 2
In fact, the top left and bottom right corners indicate double triangle numbers
We can maybe get an inverse of triangle numbers from this
Let's say I picked 101, what is the triangle number just above
it?
I can make Triangle Numbers into a continuous function and
try to invert it
y = x^2 / 2 + x / 2
2y = x^2 + x
2y + 1/4 = x^2 + x + 1/4
8y + 1 = 4x^2 + 4x + 1
8y + 1 = (2x + 1)^2
\sqrt{8y + 1} = 2x + 1 [Discard the negative solution]
2x = \sqrt{8y + 1} - 1
x = \sqrt{8y + 1}/2 - 1/2
That is the inverse of the Triangle Numbers!
x = \sqrt{4y + 1}/2 - 1/2
That is the inverse of double the Triangle Numbers!
---
Even di triangle numbers are bottom right
Odd di triangle numbers are top left
*/
// MAIN FUNCTION
const spiralFunction = (n) => {
// Handle zero case
if (n === 0) {
return [0, 0]
}
// Get the Triangle Number Data
const nRoot = Math.pow(4*n+1,0.5)/2 - 1/2
const ubRoot = Math.ceil(nRoot)
const upperBound = (ubRoot*ubRoot + ubRoot)
// console.log(`${n}`)
// console.log(` ${nRoot}, ${ubRoot}, ${upperBound}`)
// Check if it is odd (UB top-left) or even (UB bottom-right)
const isOdd = ubRoot % 2 === 1
/** For speed I'm gonna just do the separate cases for odd and even. In production, I can leverage code reuse. **/
// If the upper bound root is odd then the
// upper bound Point will be on the top-left
// and it will be half of the UB root + 1
if (isOdd) {
const length = (ubRoot + 1) / 2
// This is the upper bound point
// const ubPoint = [-length, length]
const remainingDistance = upperBound - n
// If the remaining distance is low, just go right
if (remainingDistance <= ubRoot) {
const distanceX = remainingDistance
return [-length + distanceX, length]
}
// If the remaining distance is high, just go right and down
if (remainingDistance > ubRoot) {
const distanceX = ubRoot
const distanceY = remainingDistance - ubRoot
return [-length + distanceX, length - distanceY]
}
}
// If the upper bound root is even then the
// upper bound Point will be on the bottom-right
// and it will be half of the UB root
if (!isOdd) {
const length = ubRoot / 2
// This is the upper bound point
// const ubPoint = [length, -length]
const remainingDistance = upperBound - n
// If the remaining distance is low, just go left
if (remainingDistance <= ubRoot) {
const distanceX = remainingDistance
return [length - distanceX, -length]
}
// If the remaining distance is high, just go left and up
if (remainingDistance > ubRoot) {
const distanceX = ubRoot
const distanceY = remainingDistance - ubRoot
return [length - distanceX, -length + distanceY]
}
}
// All cases are covered, so it is impossible to reach this point
return null
}
// Prints all spirals up to 100
for (let i = 0; i < 100; i++) {
console.log(`${i}: ${JSON.stringify(spiralFunction(i))}`)
}
-- SOLUTION for the 2nd Problem --
When solving the 2nd problem, I looked at the point, found which edge of the spiral it would be in, and then used the logic from my previous formulas to calculate n.
-- STEPS --
1) Find the edge type of (or what direction is the spiral moving at) the point
2) From there, remember top-left-corners signify a double-triangle-number of an odd number, whilst bottom-right corners signifiy a double-triangle-number of an even number
3A) If the point is at a TOP or RIGHT edge, find the distance it would take to get to the top-left corner
3B) If the point is at a BOTTOM or LEFT edge, find the distance it would take to get to the bottom-right corner
4) Calculate the double-triangle-number based on the corner-type and the length of the x (which is always equal to the length of the y)
5) Subtract the distance traveled to that corner, and you have n
[Time Complexity: This is, of course, O(1) time!]
-- Note --
There was a tiny caveat that influenced me to take a little more time solving this problem. A point on the RIGHT edge of the spiral has 1 less X than the absolute value of the X and the Y of the top-left edge. This -1 made me have to adjust some calculations.
This property was not present in the TOP, BOTTOM, or LEFT edges.
-- Code (You can prettify this and run into on a compiler like JS Programiz Compiler to test) --
// Spiral Function PART 2 -- [x,y] = n
// I started this at 1/24/2025 10:35pm
// Finished at 1/24/2025 11:16pm
/*
BRAINSTORM:
I just wrote my reply to the Part #1 of Spiral Inverse. Now
it is 10:35pm and I'm writing for Part #2.
[x, y] => n
-- Please read my logic from Part #1 to understand this --
The top-left corner [-2,2] would map to 12
The bottom-right [2,-2] would map to 20
-- Approach --
1) Let all points be part of 4 categories of a spiral's edge:
I) A top-edge (including both corners)
II) A right-edge (excluding the corners)
III) A bottom-edge (including both corners)
IV) A left-edge (excluding the corners)
2) We can use logic from the x and y to determine which edge a
point is on
(E.G.) If it is (2,5) the y-value is much higher than +2 so it must be on the top-edge
3A) From here, edges I and II are preceding the spiral point to the top-left, so we determine the top-left upper bound point
3B) Edges III and IV are preceding the spiral point on the
bottom-right, so we determine the bottom-right UB point
4) Once we determine the UB point, we use its length to get
the UB root using the inverse of the formula from Part #1
5) We then calculate the di-triangle number from the UB Root
and the subtract the distance traveled to get to the
UB point from our given point
6) BOOM! O(1) Time!
*/
// MAIN FUNCTION
const spiralFunctionInverse = (point) => {
// Get the coordinates
const x = point[0]
const y = point[1]
// Handle zero case
if (x === 0 && y === 0) {
return 0
}
// Get the absolute value of coordinates
const absX = Math.abs(x)
const absY = Math.abs(y)
/** For the sake of speed (pretending this is an interview
* problem), I will handle the edge cases,
* case-by-case, but in a production setting I will have more
* time to leverage code-reuse **/
// Find the edge type
let edgeType = null
// Handle the top and bottom edges
// Caveat: Right edges have 1 less x than the UB length
const isHorizontalEdge = absY >= absX && !(x > 0 && y === x)
if (isHorizontalEdge) {
const isTopEdge = y > 0
if (isTopEdge) {
edgeType = "TOP"
}
if (!isTopEdge) {
edgeType = "BOTTOM"
}
}
// Handle the left and right edges
if (!isHorizontalEdge) {
const isRightEdge = x > 0
if (isRightEdge) {
edgeType = "RIGHT"
}
if (!isRightEdge) {
edgeType = "LEFT"
}
}
// Handle UB Point and distance
let upperBoundPoint = null
let remainingDistance = 0
if (edgeType === "TOP") {
upperBoundPoint = [-absY, absY]
const goLeftDistance = absY + x
remainingDistance = goLeftDistance
}
// Right edges have 1 less x then UB length
if (edgeType === "RIGHT") {
const length = absX + 1
upperBoundPoint = [-length, length]
const topRightPoint = [absX,length] // For reference
const goUpDistance = length - y
const goLeftDistance = length + absX
remainingDistance = goUpDistance + goLeftDistance
}
if (edgeType === "BOTTOM") {
upperBoundPoint = [absY, -absY]
const goRightDistance = absY - x
remainingDistance = goRightDistance
}
// Left edges have the same length then UB length
if (edgeType === "LEFT") {
const length = absX
upperBoundPoint = [length, -length]
const bottomLeft = [-absX,-length] // For reference
const goDownDistance = absX + y
const goRightDistance = length + absX
remainingDistance = goDownDistance + goRightDistance
}
// Find the UB number
let ubRoot = -1
const ubLength = Math.abs(upperBoundPoint[0])
const isOdd = edgeType === "TOP" || edgeType === "RIGHT"
if (isOdd) {
ubRoot = 2 * ubLength - 1
}
if (!isOdd) {
ubRoot = 2 * ubLength
}
const upperBoundNumber = ubRoot * ubRoot + ubRoot
// Find n
const n = upperBoundNumber - remainingDistance
// console.log(`${edgeType} ${JSON.stringify(upperBoundPoint)}, ${ubRoot}, ${n}`)
// Return n
return n
}
console.log(spiralFunctionInverse([5,7]))