Перевірка, чи є число квадратом цілого числа

Враховуючи ціле число, визначте, чи воно є квадратним числом: У математиці квадратне число або ідеальний квадрат — це ціле число, яке є квадратом цілого числа; інакше кажучи, це твір деякого цілого числа самого себе. Приклади: -1: False, 0: True, 25 True | CodeWars Перший варіант рішення проходить усі тести, але не проходить за часом:

if n ==0: return True else: for i in range(0,n): if i*i==n: return True else: return False

if n == 0: return True elif n  

Чому другий варіант не проходить ці тести? Потрібен варіант, який займає мало часу (не потрапить під помилку Execution Timed Out (12000 ms)), а також не використовуються бібліотеки.

@Akina У пітоні приводити до інту треба викликаючи його як функцію, це не C # ) Але так то питання абсолютно точне

5 відповідей 5

Найпростіше швидке рішення для будь-якого цілого числа - двійковий пошук для отримання цілої частини квадратного кореня і пряма перевірка, що його квадрат дорівнює вихідному числу:

def isqrt(n): low = 0 high = n + 1 # + 1 to process 0, 1 property while low < high - 1: mid = (low + high) // 2 if n < mid ** 2: high = mid else: low = mid return low def is_square(n): return n >= 0 and isqrt(n) ** 2 == n

Немає сенсу робити цикл до n. Це приблизно 100 500 зайвих операцій у середньому. Якщо n дорівнює 10001, то вийде 9900 зайвих ітерацій, адже квадрат будь-якого числа більше 100 вже більше 10000, то навіщо їх перевіряти. Потрібно робити цикл до квадратного кореня з n

if n == 0: return True else: for i in range(n + 1): i2 = i * i # квадрат чергового числа if i2 == n: return True elif i2 > n: # якщо квадрат більший за n, то немає сенсу перевіряти далі break return False # тут я прибрав else і переніс рядок на рівень вище. Різниці ніякої немає, а читальність покращала.

Додаток 1 дозволяє прибрати першу перевірку на 0. Отже, ми цю перевірку краще замінимо на перевірку негативних чисел:

if n < 0: return False else: for i in range(n + 1): i2 = i * i if i2 == n: return True elif i2 >n: break return False

Дописав, а також спробував брати 2 - n, час скоротився на 0.04ms в тесті, але цього недостатньо.

Наведу як відповідь, тому що часто сам стикаюся з таким у завданнях, а в коментарях саме цього способу не бачу. Хоча, якщо у вас випадок саме для простого зведення в ступінь, то варіант нижче не допоможе. А от у ряді подібних випадків буде просто необхідним. Дякуємо @CrazyElf за дуже цінний коментар до першого варіанта відповіді.

Використання оператора зведення в ступінь ** і поділу по модулю % (а вони часто використовуються разом, при хешуванні, наприклад) зазвичай витратно за великими числами. У цьому випадку краще використовувати вбудовану функцію pow.

Наприклад, у разі зведення тризначного числа в тризначний ступінь ** ще працює швидше, ніж pow , а для чотиризначних - вже навпаки. Див. приклад нижче зроблений на моєму (далеко не найновішому) ноуті.

import timeit import math print(timeit.timeit ('pow(5362, 2445)')) # 142 секунд print(timeit.timeit ('5362**2445')) # 147 секунд print(timeit.timeit ('(526 * * 252) % 10145')) # 2.87 секунди print(timeit.timeit ('pow(526, 252, 10145)')) # 0.90 секунд

Особливо важливо це при різних множинних застосуваннях зведення в ступінь у програмі, включаючи рекурсивні і т.д., тобто. за великої кількості таких операцій.

Є ще pow в бібліотеці math, але з ним взагалі щось дивне. Наприклад, pow(53, 244) вважається без помилок, а math.pow(53, 244) видає OverflowError: math range error . Тож його тут не розглядаю.