How to solve this problem with binary search?


  • 0
    L

    I used hash table with powers of divider as keys, their occurrences as values and add them up.
    EG.75/3=25 map = {9: 2, 3: 2, 1: 1}
    9+9+3+3+1=25
    Please tell me how to solve this problem with binary search, not bit manipulation. Many thanks!

    class Solution:
            # @param {integer} dividend
            # @param {integer} divisor
            # @return {integer}
            def divide(self, dividend, divisor):
                flag = True
                if (dividend>0 and divisor<0) or (dividend<0 and divisor>0):
                    flag = False
                dividend = abs(dividend)
                divisor = abs(divisor)
        
                if divisor == dividend:
                    return 1 if flag else -1
                if divisor > dividend:
                    return 0
                    
                if divisor == 1:
                    if dividend == pow(2,31) and flag:
                        return dividend-1
                    return dividend if flag else -dividend
                #Construct a map with low_pow: cur_num as key value pair 
                #EG.75/3=25 map = {9: 2, 3: 2, 1: 1}
                #9+9+3+3+1=25  
                hash_table = {}
                n = 0
                while pow(divisor,n) < dividend:
                    n += 1
                low_pow = pow(divisor, n-1)
                while dividend >= divisor:
                    cur_num = 0
                    while dividend >= low_pow and n > 0:
                        dividend -= low_pow
                        cur_num += 1
                    n -= 1
                    low_pow = pow(divisor, n-1)
                    if cur_num != 0:
                        hash_table[low_pow] = cur_num
                res = 0
                for key in hash_table.keys():
                    while hash_table[key] != 0:
                        res += key
                        hash_table[key] -= 1
                if flag:
                    return res
                else:
                    return -res

Log in to reply
 

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