Количество целых точек, находящихся на расстоянии D от начала координат

Опубликовано: 21 Сентября, 2022

Для данного положительного целого числа D задача состоит в том, чтобы найти количество целочисленных координат (x, y), которые лежат на расстоянии D от начала координат.

Пример:

Input: D = 1
Output: 4
Explanation: Total valid points are {1, 0}, {0, 1}, {-1, 0}, {0, -1}

Input: D = 5
Output: 12
Explanation: Total valid points are {0, 5}, {0, -5}, {5, 0}, {-5, 0}, {3, 4}, {3, -4}, {-3, 4}, {-3, -4}, {4, 3}, {4, -3}, {-4, 3}, {-4, -3}

Подход: этот вопрос может быть упрощен для подсчета целых координат, лежащих на окружности с центром в начале координат, имеющей радиус D , и может быть решен с помощью теоремы Пифагора. Так как точки должны находиться на расстоянии D от начала координат, то все они должны удовлетворять уравнению x * x + y * y = D 2 , где (x, y) - координаты точки.
Теперь, чтобы решить вышеуказанную проблему, выполните следующие действия:

  • Инициализируйте переменную, скажем, count , в которой хранится общее количество возможных пар координат .
  • Перебрать все возможные координаты x и вычислить соответствующее значение y как sqrt(D 2 – y*y) .
  • Поскольку каждая координата, у которой x и y являются положительными целыми числами, может образовывать в общей сложности 4 возможных допустимых пары как {x, y}, {-x, y}, {-x, -y}, {x, -y} и увеличивать количество каждой возможной пары (x, y) на 4 в переменной count .
  • Кроме того, на окружности окружности всегда присутствует целочисленная координата, где она пересекает ось x и ось y, потому что радиус окружности является целым числом. Так что добавьте 4 в count , чтобы компенсировать эти очки.
  • После выполнения вышеуказанных шагов выведите значение count как результирующее количество пар.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ