Максимальное количество уникальных квадратов, которые могут быть сформированы с N произвольными точками на координатной плоскости.

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

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

Примечание. Любые два квадрата, которые не перекрываются, считаются уникальными.

Примеры:

Input: N = 9
Output: 5
Explanation:
Consider the below square consisting of N points:

The squares ABEF, BCFE, DEHG, EFIH is one of the possible squares of size 1 which are non-overlapping with each other.
The square ACIG is also one of the possible squares of size 2.

Input: N = 6
Output: 2

Подход: Эта проблема может быть решена на основе следующих наблюдений:

  • Заметьте, что если N — идеальный квадрат, то максимальное количество квадратов будет сформировано, когда точки sqrt(N)*sqrt(N) образуют сетку sqrt(N)*sqrt(N) , и все они равны по площади.
  • Но когда N не является идеальным квадратом , тогда он по-прежнему образует сетку, но с наибольшим числом, которое является идеальным квадратом, имеющим значение меньше, чем N.
  • Остальные координаты можно разместить по краям сетки, что приведет к максимально возможным квадратам.

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

  1. Инициализируйте переменную, скажем, an , которая хранит результирующее количество сформированных квадратов.
  2. Найдите максимально возможный размер сетки как sqrt(N) и количество всех возможных квадратов, сформированных до длины len , в переменную ans , которую можно вычислить с помощью .
  3. Уменьшите значение N на len*len .
  4. Если значение N не меньше len , то все остальные квадраты можно сформировать, поместив их в другой кластер точек. Найдите количество квадратов, рассчитанное на шаге 2 , для значения len .
  5. После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

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

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

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