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?

Question

Anonymous · Accepted Answer

Started with a brute force approach (very inefficient) then worked to a log(n) complexity solution somewhat reminiscent of a binary search algorithm.

use Newton Raphleson · Answer

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

Pedro · Answer

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

Use this that you think · Answer

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(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.

Use this that you think · Answer

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 (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.

Pedro · Answer

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

Meta

Meta Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches