Problem Statement
There is an infinite square grid. Each cell of the grid contains a non-negative integer, and each non-negative integer appears in exactly one cell.
Two cells of the grid are called adjacent if they share a side.
The integers are arranged into a spiral that starts with the number 0. For each n, the cells that contain numbers n and n+1 are adjacent. If you start at 0 and walk along the spiral, your sequence of steps will be as follows: 1 step up, 1 step right, 2 steps down, 2 steps left, 3 steps up, 3 steps right, 4 steps down, and so on.
Beginning of the spiral:
9 10 11 12
8 1 2 13
7 0 3 14
.. 6 5 4 15
.. .. .. .. 16
You are given the int D: a difference we want to find in the grid. Find and return the smallest x such that the cells that contain x and x+D are adjacent. If there is no such x, return -1 instead.
Definition
- Class:
- GridSpiral
- Method:
- findCell
- Parameters:
- int
- Returns:
- long
- Method signature:
- long findCell(int D)
- (be sure your method is public)
Notes
- It is guaranteed that whenever an answer exists, it fits into a long.
Constraints
- D will be between 1 and 10^9, inclusive.
Examples
5
Returns: 0
Cells with values 0 and 5 are adjacent: a step down from cell 0 will take you to cell 5.11
Returns: 2
The cell with value 13 is to the right of the cell with value 2. Cells 0 and 11 are not adjacent and neither are 1 and 12, so 2 is the smallest cell with the desired property.47
Returns: 110
100
Returns: -1