Growing Steps on a Line

Medium

A token sits at point 0 on an infinite number line. Moves are numbered from one: on move i the token shifts by exactly i cells, either left or right, your choice. Return the smallest number of moves after which the token can land exactly on point goal.

Example 1

goal=4 → 3

Two moves reach at most point 3. Three moves cover 1 + 2 + 3 = 6, and making the first move to the left gives −1 + 2 + 3 = 4.

Example 2

goal=-6 → 3

Three moves to the left: −1 − 2 − 3 = −6.

Example 3

goal=2 → 3

Constraints

-10⁹ ≤ goal ≤ 10⁹
goal ≠ 0

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Binary Search

Similar problems

Digit of Endless Counting Medium Two Squares Make It Medium N-th Number Divisible by One of Three Medium Prices That Fade With Each Sale Medium Fencing an Orchard Plot Medium

Input

goal=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 72 tests on the server, hidden ones included.