Meta interview question
Given two unsigned integer values, write a function that returns the first divided by the second. You cannot (of course) use div or mod operators - only addition, subtraction and multiplication. Discuss the strengths/weaknesses/algorithmic complexity of your solution. Is there a better way to do it? If so, what, and what is its complexity?
Interview Answers
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
uint x1=54;
uint x2 = 3;
var d = invert(x2);
System.Console.WriteLine((uint) (d*x1));
}
static double invert(uint i)
{
double d = .5;
double x1 = d;
double x2 = 0;
do
{
x2 = x1*(2 - i*x1);
d = x2 - x1;
x1 = x2;
} while (Math.Abs(d)> 1e-4);
return x2;
}
}
}
Started with a brute force approach (very inefficient) then worked to a log(n) complexity solution somewhat reminiscent of a binary search algorithm.
First make a brute forcé like this: ---
public static int divide(int a,int b){
int out=0;
int test = 0;
int i=0;
while(a>=test){
out = i;
i++;
test = b*i;
System.out.print(i+",");
}
System.out.println(".");
return out;
}
--- then use a recursive way to Split the divided element like this: ---
public static int divMain(int a, int b){
StringBuilder sb = new StringBuilder();
if(a>(b*10)){
String bstr = String.valueOf(b);
String astr = String.valueOf(a);
String temp;
int bsize = bstr.length();
int asize = astr.length();
int atemp = Integer.valueOf(astr.substring(0,bsize));
if(atemp<b>(bsize+1)){
bsize++; atemp = Integer.valueOf(astr.substring(0,bsize));
}
int parc = divide(atemp,b);
//System.out.println("D1: "+atemp+"/"+b+"="+parc);
sb.append(parc);
temp = astr.substring(bsize);
if(asize>bsize && !temp.isEmpty()){
int res = atemp-(parc*b);
int anew = Integer.valueOf(res+temp);
//System.out.println("D2: "+((int)anew)+"/"+b+"=?");
sb.append(divMain((int)anew,b));
}
}else{
sb.append(divide(a, b));
}
return Integer.valueOf(sb.toString());
}
--- Now you can show a easy algorithmic complexity ---
public static void main(String[] args) {
int a = 39942;
int b = 202;
System.out.println("R: "+a+"/"+b+"="+(a/b));
//System.out.println("F: "+a+"/"+b+"="+divide(a,b));
System.out.println("T: "+a+"/"+b+"="+divMain(a,b));
}
--- Maybe is not the better but is easy to share.</b>
First make a brute forcé like this:<br>public static int divide(int a,int b){<br>
int out=0;
int test = 0;
int i=0;<br>
while(a>=test){<br>
out = i;
i++;
test = b*i;
System.out.print(i+",");<br>
}<br>
System.out.println(".");
return out;<br>
}<br>
then use a recursive way to Split the divided element like this:<br>
public static int divMain(int a, int b){<br>
StringBuilder sb = new StringBuilder();<br>
if(a>(b*10)){<br>
String bstr = String.valueOf(b);
String astr = String.valueOf(a);
String temp;
int bsize = bstr.length();
int asize = astr.length();
int atemp = Integer.valueOf(astr.substring(0,bsize));<br>
if(atemp <b>(bsize+1)){<br>
bsize++; atemp = Integer.valueOf(astr.substring(0,bsize));<br>
}<br>
int parc = divide(atemp,b);
//System.out.println("D1: "+atemp+"/"+b+"="+parc);
sb.append(parc);
temp = astr.substring(bsize);<br>
if(asize>bsize && !temp.isEmpty()){<br>
int res = atemp-(parc*b);
int anew = Integer.valueOf(res+temp);
//System.out.println("D2: "+((int)anew)+"/"+b+"=?");
sb.append(divMain((int)anew,b));<br>
}<br>
}else{<br>
sb.append(divide(a, b));<br>
}<br>
return Integer.valueOf(sb.toString());<br>
}<br>
Now you can show a easy algorithmic complexity:<br>
public static void main(String[] args) {<br>
int a = 39942;<br>
int b = 202;<br>
System.out.println("R: "+a+"/"+b+"="+(a/b));<br>
//System.out.println("F: "+a+"/"+b+"="+divide(a,b));<br>
System.out.println("T: "+a+"/"+b+"="+divMain(a,b));<br>
}<br>
<b>Maybe is not the better but is easy to share.</b></b>
Sorry. New version without div/mod operation:
private static void Main()
{
int number1 = 1250;
int number2 = 250;
int precision = 3;
int sum = 0;
double count1 = 0;
double count2 = 0;
int diff = 0;
diff = (number1 - sum);
if(number2 == 0)
return;
while ((sum = number2))
{
sum = sum + number2;
diff = (number1 - sum);
count1++;
}
if (diff > 0)
{
for (int i = 0; i = number2))
{
sum = sum + number2;
diff = (mod - sum);
count2++;
}
decimalValue = decimalValue + count2;
count1 = count1 + Convert.ToDouble(decimalValue);
}
}
Console.WriteLine(count1);
Console.ReadKey();
}
What about this?
int number1 = 125;
int number2 = 13;
int sum = 0;
double count = 0;
int diff = 0;
do
{
sum = sum + number2;
diff = (number1 - sum);
count++;
} while ((sum number2));
double mod = diff/(double)number2;
Console.WriteLine(count + mod);