Найдите диапазон [L, R] такой, что сумма чисел в этом диапазоне равна N

Для заданного целого числа N (N ≠ 0) задача состоит в том, чтобы найти диапазон [L, R] (−10⁻¹⁸ < L < R < 10¹⁸), такой, что сумма всех целых чисел в этом диапазоне равна N .

L + (L+1) + … + (R−1) + R = N

Примеры:

Input : N = 3
Output: -2 3
Explanation: For L = -2 and R = -3 the sum becomes -2 + (-1) + 0 + 1 + 2 + 3 = 3

Input : N = -6
Output: -6 5
Explanation: The sum for this range [-6, 5] is -6 + (-5) + (-4) + (-3) + (-2) + (-1) + 0 + 1+ 2 + 3 + 4 + 5 = -6

Наивный подход: для каждого значения L попытайтесь найти значение R, которое удовлетворяет условию L + (L + 1) + . . . + (R-1) + R = N, используя вложенный цикл.
Временная сложность: O(N ² )
Вспомогательное пространство: O(1)

Эффективный подход: поскольку L и R являются целыми числами и могут быть также отрицательными числами, вышеуказанная проблема может быть эффективно решена за O (1). Рассмотрим следующее наблюдение:

• Для N, являющегося положительным целым числом , мы можем рассмотреть:

[−(N – 1)] + [−(N – 2)] + . . . -1 + 0 + 1 + . . . + (N − 1) + N = 
-(N – 1) + (N – 1) – (N – 2) + (N – 2) + . . . + 1 – 1 + 0 + N = N
So, L = -(N – 1) and R = N

• Точно так же , если N является отрицательным , мы можем рассмотреть:

N + (N + 1) + . . . -1 + 0 + 1 + . . . + [-(N + 2)] + [-(N + 1)] = 
(N + 1) – (N + 1) + (N + 2) – (N + 2) + . . . -1 + 1 + 0 + N = N
So L = N and R = -(N + 1)

Следовательно, решение этой задачи в единице времени сложности:

L = -(N – 1) and R = N, when N is a positive integer.

L = N and R = -(N + 1), when N is a negative integer.

Примечание. Это самый длинный возможный диапазон (т. е. R – L имеет наибольшее значение), который удовлетворяет условию задачи.

Ниже приведена реализация подхода:

Временная сложность: O(1)
Вспомогательное пространство: O(1)