Q1. Divide n1 by n2 without using division. Give time complexity
Q2. Improve previous answer

Question

Q1. Divide n1 by n2 without using division. Give time complexity
Q2. Improve previous answer

Sigiloso · Accepted Answer

If I understood the question correctly (feedback is appreciated)
#Takes into account negative inputs
x = -11 #Assume n1
y = 2   #Assume n2
xneg = False
yneg = False
if x = 0:
    x = x - y
    n = n + 1
if xneg ^ yneg: #Exclusive or. Only one of the numbers can be negative for the result to be negative
    print n*-1
else:
    print n

Sigiloso · Answer

^^the copy paste didnt copy my less than sign or the entire code. sorry

Chenqian Lin · Answer

public static int divideWithoutDivision(int n, int d){
        if(d == 0) throw new Exception();
        if(n ＜ 0){
            if(d ＜ 0) return divideWithoutDivision(-n, -d);
            else return -divideWithoutDivision(-n, d);
        }else if(d ＜ 0) return -divideWithoutDivision(n, -d);
            
        if(n ＜ d) return 0;
        int intermediateResult = 1;
        while(d * intermediateResult * 2 ＜ n) intermediateResult *= 2;
        return intermediateResult + divideWithoutDivision(n - d * intermediateResult, d);
    }

Sigiloso · Answer

Define a counter i = 0 and add one each time, find i such that n2*2^(i-1) < n1 <= n2*2^i . Now using binary search in the range (2^(i-1), 2^i) find n3 such that (n1 - n3*n2) is the minimum positive integer.

Sigiloso · Answer

keep adding n2 to itself (n2+n2+n2+...) until it reaches n1. maintain count of iterations. many edge cases to check! improvement was to keep adding of n2 to itself in a different way (1*n2 + 2*n2 + 3*n2 +...) until it crosses n1. then restart again from 1*n2

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas