TopCoder Statistics - Problem Statement

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
1

Returns: 0
2

Returns: -1
3

Returns: 0
4

Returns: -1
5

Returns: 0
6

Returns: -1
7

Returns: 0
8

Returns: -1
9

Returns: 1
10

Returns: -1
11

Returns: 2
12

Returns: -1
13

Returns: 4
14

Returns: -1
15

Returns: 6
16

Returns: -1
17

Returns: 9
18

Returns: -1
19

Returns: 12
20

Returns: -1
123

Returns: 870
1234

Returns: -1
12345

Returns: 9517225
123456

Returns: -1
1234567

Returns: 95258958240
123456789

Returns: 952598594726416
987654321

Returns: 60966315494589241
1000000000

Returns: -1
999999999

Returns: 62499999250000002
999999997

Returns: 62499999000000004
933495633

Returns: 54463380468444649
865435235

Returns: 46811133582822056
810101011

Returns: 41016477495138252
999999

Returns: 62499250002
11111111

Returns: 7716042283952
987654323

Returns: 60966315741502820
999979999

Returns: 62497499275015002
99999999

Returns: 624999925000002
967459543

Returns: 58498622354198340
25

Returns: 25
21

Returns: 16

Statistics

Problem Statement for "GridSpiral"

Problem Statement

Definition

Notes

Constraints

Examples