Implement integer division without using / or %. Questions about running time. Can you do it faster?

Question

coding_fakir · Accepted Answer

Here's an implementation that works -- any ideas on how to make it go faster?

public static void divide_without_slash_or_mod(int num, int divisor)
{
     int factor = 0;
     int remainder = num;
		
     System.out.println("Number = " + num + " divisor = " + divisor);
		
     while(remainder >= divisor) {
	remainder -= divisor;
	factor++;
     }
		
    System.out.println(" remainder = " + remainder + " factor = " + factor );
}

Jigsaw · Answer

D(Divisor), N(Divident)

low = 0, high = INT_MAX/D
while(low  N) high = mid - 1;
   else low = mid + 1;
}
return -1; //No divisor

DevSathish · Answer

Here is the Java implementation of implementing division with O(log n) time complexity (actually, this solution is using divide operator).

public static void divide(int dividend, int divisor) {
        int mid,
            low = 0,
            high = Integer.MAX_VALUE / divisor;
        while(low  dividend) { high = mid-1; }
            else { low = mid +1; }
        }
    }

Anoniem · Answer

Optimal running time: O(log n)

Gabriel · Answer

Binary search

X

Sollicitatievraag bij X

Antwoorden op sollicitatievragen

Gevolgde bedrijven

Vacatures