У меня есть вопрос, который я пытался использовать в LeetCode, и мне нужна помощь в устранении ошибки: превышен лимит времени.

Question

Ссылка на конкретный вопрос выглядит следующим образом: https://leetcode.com/problems/nth-magical-number/. Мой код показывает «Превышен лимит времени», и я не могу понять, где на самом деле кроется ошибка в моем коде. Мой код выглядит следующим образом:

class Solution {
public:
    typedef unsigned int ull;
    int gcd(int A,int B)
    {
        if(B==0)
            return A;
        else
            return gcd(B,A%B);
    }
    int nthMagicalNumber(int N, int A, int B) {
        ull m;
        if(A<B)
        {
           int t;
            t=A;
            A=B;
            B=t;
        }
        ull lcm=(A*B)/gcd(A,B);
        ull l=2;
        ull h=1e9;
        ull n;
        while(l<=h)
        {
            m=l+(h-1)/2;
           n=(m/A)+(m/B)-(m/lcm);
            if(n==N)
                break;
            else if(n<N)
                l=m+1;
            else if(n>N)
                h=m-1;
        }
        ull x=(1e9)+7;
        return (int)(m%x);       
    }
};

Может ли кто-нибудь сообщить мне, где я ошибаюсь и как я могу исправить ошибку?

Answer 1

Вы можете попробовать этот подход на C ++ для этого вопроса, мое решение было принято:

class Solution {
public:
    long long gcd(long long a, long long b) {
        if(b == 0)
            return a;
        return gcd(b, a % b);
    }

    int nthMagicalNumber(long long n, long long a, long long b) {
        
        long long end = max(a, b) * (n + 1);
        long long min = 1;
        long long lcm = (a / gcd(a, b)) * b;
        long long curr, mid;
        while(min <= end) {
            mid = (end - min)/2 + min;
            
            curr = (mid / a) + (mid / b) - (mid / lcm);
            if(curr > n) {
                end = mid - 1;
            } else if(curr < n) {
                min = mid + 1;
            } else {
                break;
            }
        }
       
        while((mid % a != 0) && (mid % b != 0)) {
            mid--;
        }
        return mid % (1000000007);
    }
};

Answer 2

Вы можете использовать для этого отладчик. Это решение очень похоже (с использованием двоичного поиска с gcd) и будет проходить через:

// This block might trivially optimize the exec time;
// Can be removed;

const static auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();


#include <cstdint>
#include <vector>


const static struct Solution {
    using SizeType = std::uint_fast64_t;
    static constexpr SizeType kMod = 1e9 + 7;
    const SizeType nthMagicalNumber(
        const SizeType N,
        const SizeType A,
        const SizeType B
    ) {
        const SizeType lowest_common_multiple = A * B / getGreatestCommonDivisor(A, B);
        SizeType lo = 2;
        SizeType hi = 1e14;


        while (lo < hi) {
            SizeType mid = lo + (hi - lo) / 2;

            if (mid / A + mid / B - mid / lowest_common_multiple < N) {
                lo = mid + 1;

            } else {
                hi = mid;
            }
        }

        return lo % kMod;
    }

    // __gcd(a, b)
    static const SizeType getGreatestCommonDivisor(
        const SizeType a,
        const SizeType b
    ) {
        if (not b) {
            return a;
        }

        return getGreatestCommonDivisor(b, a % b);

    }
};

Вместо ull здесь мы используем std::uint_fast64_t.

Ссылки

• Дополнительные сведения см. На Доске обсуждения , на которой вы можете найти множество хорошо объясненных принятых решений на различных языках. включая эффективные алгоритмы и асимптотики c время / пространство анализ сложности ^{1 , 2} .