Подсчитайте целые числа, квадрат которых лежит в заданном диапазоне, а цифры являются полными квадратами

Опубликовано: 20 Февраля, 2023

Даны два целых числа L и R . Затем задача состоит в том, чтобы вывести количество целых чисел X , таких что L ≤ X 2 ≤ R и X 2 состоят только из цифр, которые являются полными квадратами.

Примеры:

Input: L = 167, R = 456
Output:  2
Explanation: Two numbers are 20 and 21, Their squares are 400 and 441 respectively. It can be verified that squares of both 20 and 21 are in the range of L and R and contains only digits which are square numbers. ie. 0, 4, 1.

Input: L = 4567, R = 78990
Output: 11

Подход: реализуйте приведенную ниже идею, чтобы решить проблему.

Find the nearest numbers from L and R both using floor(), ceil(), and in-built sqrt() function. Traverse all the integer values between those obtained two numbers and check if a number exists such that they only contain digits 0, 1, 4, 9, or not. Count those numbers in a variable.

Были предприняты шаги для решения проблемы:

  • Инициализируйте переменную ans = 0 , чтобы сохранить количество вхождений идеального квадрата.
  • Возьмем целочисленную переменную X, которая будет идеальным квадратом, ближайшим к R, и может быть получена как X = (Math.floor(Math.sqrt(R))) .
  • Возьмем целочисленную переменную Y, которая будет ближайшим к L совершенным квадратным числом и может быть получена как (Math.floor(Math.sqrt(L))) .
  • Пройдите все целочисленные значения между X и Y, используя Loop, и проверьте:
    • Сколько существует таких чисел, что они содержат только цифры 0, 1, 4 и 9?
    • Если все цифры только 0, 1, 4 или 9, то увеличьте число на 1.
  • Верните ответ.

Ниже приведена реализация описанного выше подхода.

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

Статьи по Теме:

  • Квадратный корень из целого числа