Найдите ближайший идеальный квадрат для каждого элемента массива

Дан массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы напечатать ближайший полный квадрат для каждого элемента массива.

Примеры:

Input: arr[] = {5, 2, 7, 13}
Output: 4 1 9 16
Explanation:
The nearest perfect square of arr[0] (= 5) is 4.
The nearest perfect square of arr[1] (= 2) is 1.
The nearest perfect square of arr[2] (= 7) is 9.
The nearest perfect square of arr[3] (= 13) is 16.

Input: arr[] = {31, 18, 64}
Output: 36 16 64

Подход: выполните следующие шаги, чтобы решить проблему:

• Обход массива слева направо.
• Для каждого элемента массива найдите ближайший идеальный квадрат
  • Если N полный квадрат , то выведите N
  • В противном случае найдите первое число совершенных квадратов > N и обратите внимание на его разницу с N .
  • Затем найдите первое число совершенных квадратов < N и обратите внимание на его разницу с N .
  • И выведите идеальный квадрат, в результате которого получается минимум этих двух разностей.

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

Временная сложность: O(N * sqrt(arr[i]))

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