Как в python сгенерировать очень большие числа в массив?

Question

Решаю задачу "Valid Perfect Square" на leetcode:

Учитывая положительное целое число num, верните true, если num является точным квадратом, или false в противном случае.

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

Вы не должны использовать какие-либо встроенные библиотечные функции, такие как sqrt.

Вот так я ее решил:

class Solution(object):
def isPerfectSquare(self, num):
    """
    :type num: int
    :rtype: bool
    """
    arr = [i for i in range(1, num + 1)]
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = int((low + high) / 2)
        index = arr[mid]
        if index ** 2 == num:
            return True
        if index ** 2 > num:
            high = mid - 1
        else:
            low = mid + 1
    return False

Однако, когда num - очень большое число, например, 2000105819, то происходит очень долгое вычисление. Как быть?

Answer 1

Думаю бесполезно улучшать текущий алгоритм, лучше используйте метод Ньютона:

def isPerfectSquare(num):
    """
    :type num: int
    :rtype: bool
    """
    if num < 2:
        return True

    x = num // 2
    while x * x > num:
        x = (x + num // x) // 2

    return x * x == num

Answer 2

Минимальные изменения позволяют сэкономить до 20, а то и 40 гигабайт памяти и примерно столько же времени.

Выкидывам к черту список, потому что единственное его предназначение здесь - получить число по индексу, которое равно индекс+1!

def isPerfectSquare(self, num):
    """
    :type num: int
    :rtype: bool
    """
    # arr = [i for i in range(1, num + 1)] <- выкидываем
    low = 0
    high = num - 1 # меняем len(arr) на num, потому что длина списка как раз равна заданному числу
    while low <= high:
        mid = int((low + high) / 2)
        # index = arr[mid] <- выкидываем
        if mid ** 2 == num: # меняем index на mid
            return True
        if mid ** 2 > num:  # меняем index на mid
            high = mid - 1
        else:
            low = mid + 1
    return False

БЛОГ НА HUSL

Как в python сгенерировать очень большие числа в массив?

Ответы (2 шт):