Anyone can help me ?[ time limit exceed] Thanks very much!!!


  • 0
    J

    my idea is use left shift to operate on divisor, then get the max n satisifies : divsor*2^n<dividend
    then let rel = divisor<<n; let provider = 1<<n;
    next, from i=n-1 to 0,
    if rel+divisor<<i < dividend, let rel=rel+divisor<<i; let provider=provider+1<<i;
    when i <0, provider is the result.

    I don't know why its time limit exceed, I think the time complexity is O(lgn)
    since every time , i use << , make the number increases 2 times, i don't know why time limit exceed,

    Can anyone help me ?? thanks a lot!!!

    class Solution {
    public:
    /*can use add and bit operation(like shift, |, & ,^) */
    int divide(int dividend, int divisor) {
    int n=0;
    while((divisor<<n)<dividend){n++;}
    n--;
    int rel = divisor<<n;
    int provider = 1<<n;
    if(rel == dividend) return provider;
    n--;
    while(n>=0){
    int m = divisor<<n;
    if((rel+m) <= dividend){
    rel = rel+m;
    provider = provider+1<<n;
    }
    n--;
    }
    return provider;
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.