Количество чисел в заданном диапазоне [L, R], которые представляют собой идеальный квадрат, а цифры имеют форму волны

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

Даны два целых числа L и R , задача состоит в том, чтобы подсчитать целые числа в диапазоне [L, R] так, чтобы они удовлетворяли следующим двум свойствам:

  • Число должно быть полным квадратом любого целого числа.
  • In цифры целого числа должны быть в волновой форме, т. е. пусть d1 , d2 , d3 , d4 , d5 будут цифрами текущего целого числа, тогда d1 < d2 > d3 < d4… должно выполняться.

Примеры:

Input: L = 1, R = 64
Output: 7 
Explanation:
The special numbers in the range [1, 64] are 1, 4, 9, 16, 25, 36 and 49.

Input: L = 80, R = 82
Output: 0

Наивный подход: самый простой подход к решению проблемы — пройтись по диапазону [L, R] и для каждого числа в диапазоне проверить два вышеуказанных условия.
Временная сложность: O(N)
Вспомогательное пространство: O(1)

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

  • Инициализируйте переменную, скажем, count = 0 , чтобы подсчитать все специальные числа в диапазоне [L, R] .
  • Перебрать все идеальные квадраты, которые меньше R .
  • Определите функцию, скажем, check(N) , чтобы проверить, удовлетворяет ли число N второму условию, перебирая четные и нечетные цифры.
  • Увеличьте count , если число больше L и проверка функции возвращает true для данного числа.
  • Наконец, верните count .

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


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

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