Найдите положение данного элемента N в бесконечной спиральной матрице, начиная с верхнего левого угла.

Имея число N и бесконечную двумерную матрицу, которую необходимо заполнить по приведенному ниже алгоритму, задача состоит в том, чтобы найти координаты данного элемента, присутствующего в матрице. Алгоритм следующий:

• Крайняя левая и самая верхняя ячейка матрицы заполняется 1. Затем все ячейки заполняются последовательными числами, начиная с 2
• Крайняя левая незаполненная ячейка в первой строке заполняется. Затем, пока заполняется левый сосед последней заполненной ячейки, далее заполняются ячейки под ним, пока у последней заполненной ячейки не появится незаполненный левый сосед
• Далее ячейки заполняются справа налево до первого столбца. Затем снова заполняется крайняя левая незаполненная ячейка в первой строке.
• Вышеуказанные два шага повторяются бесконечно

Примеры:

Input: N = 12
Output: 3 4
Explanation: 12 lies in the cell with row as 3 and column as 4

Input: N = 10549857
Output: 353 3249
Explanation: 10549857 lies in the cell with row as 353 and column as 3249

Подход: можно сделать следующие замечания:

• На приведенном выше изображении выделенная красным часть или «перевернутая буква L», образованная 3-й строкой и 3-м столбцом, состоит из всех чисел больше 4 и меньше 10. Точно так же «перевернутая буква L», образованная 4-й строкой и 4-й колонкой, состоит чисел больше 9 и меньше 17
• Другими словами, присутствующие числа исключают текущий идеальный квадрат до включения следующего идеального квадрата.
• Чтобы найти «перевернутую букву L», в которой находится число, найдите ячейку квадратного корня из числа.
• Вычисляется разница между квадратом «перевернутого L» и заданным числом, скажем, d
• Если l - это «перевернутое L», в котором находится число, а n обозначает данное число, то:

d = l^2 – N 

• Если эта разница d меньше n , то строка r и столбец c числа n задаются следующим образом:

r = l
c = d + l

• Если эта разница d больше или равна n , то строка r и столбец c числа n задаются следующим образом:

r = 2l – d – 1
c = l 

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

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