Участник:Alexryabov/TaskNthMagicalNumber

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/nth-magical-number/

Запускать в Python 2 на leetcode!

"обычная" версия с бинарным поиском

from fractions import gcd 
 
class Solution(object):
    def nthMagicalNumber(self, N, A, B):
        L = A * B / gcd(A,B) # Нам понадобится наименьшее общее кратное. Находим его по формуле
 
        def magics_below_num(x):
            #Сколько магических чисел, меньших числа x?
            #Мы можем их посчитать
            # Суммируем x / A и x / B и вычитаем x / L, чтобы убрать дубликаты
            return x / A + x / B - x / L
 
 
        low = 0
        high = 10**15
 
        while low < high:
            middle = (low + high) / 2
            if magics_below_num(middle) < N:
                low = middle + 1
            else:
                high = middle
 
 
        return low % (10**9 + 7)
 

"гибридная" версия (вроде быстрее, проверял по кол-ву операций сравнения)

from fractions import gcd 
 
class Solution(object):
    def nthMagicalNumber(self, N, A, B):
        L = A * B / gcd(A,B) # Нам понадобится наименьшее общее кратное. Находим его по формуле
 
        def magics_below_num(x):
            #Сколько магических чисел, меньших числа x?
            #Мы можем их посчитать
            # Суммируем x / A и x / B и вычитаем x / L, чтобы убрать дубликаты
            return x / A + x / B - x / L
 
        def nearest_mid(lower_bound_index, upper_bound_index, search_value):
            return lower_bound_index + \
                (upper_bound_index - lower_bound_index) * \
                (search_value - magics_below_num(lower_bound_index)) // \
                (magics_below_num(upper_bound_index) - magics_below_num(lower_bound_index))
 
        def interpolation_search(low, high, term):
 
            size_of_list = high - low
 
            index_of_first_element = 0
            index_of_last_element = size_of_list
 
            while index_of_first_element <= index_of_last_element:
                mid_point = nearest_mid(index_of_first_element, index_of_last_element, term)
 
                if magics_below_num(mid_point) == term:
                    return mid_point
 
                if term > magics_below_num(mid_point):
                    index_of_first_element = mid_point + 1
                else:
                    index_of_last_element = mid_point - 1
 
        low = 0
        high = 10**15
 
        result = interpolation_search(low, high, N) # находим приближение (interpolation search может в некоторых случаях быть быстрее binary search, мы используем его, чтобы найти верхнюю границу для ответа)
 
        low = 0
        high = result
        while low < high:
            middle = (low + high) / 2
            if magics_below_num(middle) < N:
                low = middle + 1
            else:
                high = middle
 
 
        return low % (10**9 + 7)
 

Только интерполяционный поиск:

from fractions import gcd 
 
class Solution(object):
    def nthMagicalNumber(self, N, A, B):
        L = A * B / gcd(A,B) # Нам понадобится наименьшее общее кратное. Находим его по формуле
 
        def magics_below_num(x):
            #Сколько магических чисел, меньших числа x?
            #Мы можем их посчитать
            # Суммируем x / A и x / B и вычитаем x / L, чтобы убрать дубликаты
            return x / A + x / B - x / L
 
        def nearest_mid(lower_bound_index, upper_bound_index, search_value):
            return lower_bound_index + \
                (upper_bound_index - lower_bound_index) * \
                (search_value - magics_below_num(lower_bound_index)) // \
                (magics_below_num(upper_bound_index) - magics_below_num(lower_bound_index))
 
        def interpolation_search(low, high, term):
 
            size_of_list = high - low
 
            index_of_first_element = 0
            index_of_last_element = size_of_list
 
            while index_of_first_element <= index_of_last_element:
                mid_point = nearest_mid(index_of_first_element, index_of_last_element, term)
 
                if magics_below_num(mid_point) == term:
                    return mid_point
 
                if term > magics_below_num(mid_point):
                    index_of_first_element = mid_point + 1
                else:
                    index_of_last_element = mid_point - 1
        def closestNumber(n, m) : 
            q = int(n / m) 
            n = m * q 
            return n
 
        low = 0
        high = 10**15
 
        approx = interpolation_search(low, high, N) # находим приближение
        # быстро за O(1) находим ближайшее снизу максимальное число, которое делится на каждое из чисел
        result1 = closestNumber(approx, A)
        result2 = closestNumber(approx, B)
        result = max(result1, result2)
 
        return result % (10**9 + 7)

Можно сравнить запросто, сколько требуется обоим алгоритмам. Завести какую-нибудь переменную self.operations в цикле while бинарного и интерполяционного. Разница значительная.