O(log ) complexity without shift operation


  • 0
    D

    My solution was inspired in the problem Pow

    1. put in a array list a pair with value=2^k*b and n=2^k
    2. loop array list backward maintaining a variable with result and accumulated. Every time the value accumulated + value in the array list is less than a, I increment accumulated with value in the array list and increment result with n
        public int divide(int a, int b) {
        long c=a;
        long d=b;
        boolean positive=true;
        if(c<0 && d>0){
            positive=false;
            c=-c;
        }
        else if(c>0 && d<0){
            positive=false;
            d=-d;
        }
        else if(c<0 && d<0){
            c=-c;
            d=-d;
        }
        
        ArrayList<Wrapper>al=new ArrayList<>();
        al.add(new Wrapper(d,1));
        while(c>=al.get(al.size()-1).v+al.get(al.size()-1).v){
            Wrapper w=al.get(al.size()-1);
            al.add(new Wrapper(w.v+w.v,w.n+w.n));
            if(w.n==0){
            	System.out.println();
            }
        }
       
        long acc=0;
        long tot=0;
        for(int i=al.size()-1;i>=0;i--){
            Wrapper w=al.get(i);
            if(acc+w.v<=c){
                acc+=w.v;
                tot+=w.n; 
            }
        }
        
        return positive?(int)tot:(int)-tot;
    }
    
    class Wrapper{
        long v;
        long n;
        Wrapper(long _v,long _n){
            v=_v;
            n=_n;
        }
    }

Log in to reply
 

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