Найдите пару последовательных идеальных квадратов с разностью K

Для заданного целого числа K задача состоит в том, чтобы найти два последовательных полных квадрата, разность которых равна K . Если таких пар чисел не существует, выведите -1 .

Примеры:

Input: K = 5
Output: 4 9
Explanation:
So, 4 and 9 are the two perfect squares which differ by 5(= 9 – 4 = 5).

Input: K = 4
Output: -1

Наивный подход: простой подход к решению данной проблемы состоит в том, чтобы пройти по всем идеальным квадратам и проверить, существуют ли какие-либо 2 таких числа, разница которых равна K , если окажется, что они верны, а затем вывести эти пары. В противном случае выведите -1 .

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

Эффективный подход. Приведенный выше подход также можно оптимизировать, наблюдая разницу между последовательными идеальными квадратами как:

Perfect Squares:                1     4      9      16     25     …
Consecutive Difference:    3      5      7        9       …

Из приведенного выше наблюдения следует, что разница между последовательными идеальными квадратами находится в порядке последовательных нечетных чисел. Следовательно, когда разница четная, таких пар чисел не существует, поэтому выведите «-1» . В противном случае два числовых числа задаются как (K/2) ² и ((K + 1)/2) ² .

Ниже приведена реализация вышеуказанного подхода:

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