Meta Interview Question

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

Interview Answers

Anonymous

Feb 29, 2016

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.

Anonymous

Aug 11, 2016

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

Anonymous

Aug 11, 2016

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

Anonymous

Oct 2, 2016

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); }

Anonymous

Jan 16, 2016

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