CareerCup

//implementation for positive ints without error checking
int Devide(unsigned int a, unsigned int b)
{
	unsigned int result = 0;
	unsigned int bFriend = b;

	//initialize denominator
	while ( a > bFriend)
	{
		bFriend = bFriend << 1;
	}

	while (bFriend >= b)
	{
		result = result << 1 ;
		if (a >= bFriend)
		{
			result += 1;
			a = a - bFriend;
		}
		bFriend = bFriend >> 1;
	}
	return result;
}

<pre lang="" line="1" title="CodeMonkey79639" class="run-this">class DivideWithoutDivide
{
public static void main (String args[]) throws InterruptedException
{
if (args.length < 2)
{
System.out.println ("Enter numbers a and b for a/b");
return;
}
int a = Integer.parseInt (args[0]);
int b = Integer.parseInt (args[1]);
System.out.println (findQuotient(a, b));
}

static int findQuotient (int a, int b) throws InterruptedException
{
int upper = a;
int lower = 1;
int n = (upper+lower) >> 1;
while (b*n != a && upper-1 > lower)
{
if (b*n < a)// go to the bigger half on right
{
lower = n;
}
else if (b*n > a) // go to the smaller half on the left
{
upper = n;
}
else break;
n = (upper+lower) >> 1;
}

return n;
}
}
</pre><pre title="CodeMonkey79639" input="yes">
1331 12</pre>

if a/b is n your approach is O(n) you can do O(logn)

a

Time complexity = O(lg n)

Is this OK.
1. find x so that b*x < a <b*(x+1). x is quotient and a-b*x = remainder.

Let us take a = 976 and b = 13.
Find the first k so that 13^k >=9 76. Equality we are done.
Here k = 3. We have 13^3 = 2197.
13^3 = 13(169).
Note: All division by 2 can done by >> 1.
(1 +169)/2 = 85. So have the following sequence.
13*1, 976, 13*85 = 1105
Find (1+85)/2 = 43 ,
So we have 13*43= 559, 976,13*85=1105.
Find (43+85)/2 = 64 , and 13*64 = 832.
So we have 13*64 = 832, 976, 13*85=1105.
Find (64+85)/2 = 74 and 13*74 = 962.
So we have 13*74=962, 976, 13*85=1105.
(74+85)/2 = 80 = 1040,
So we have 13*74=963,976,13*80=1040
(74+80)/2 = 77 , and 13*77 = 1001.
So we have 13*74=963, 976,13*77=1001
(74+77)/2 = 75, and 13*75 = 975,
So we have 13*75=975, 936,13*77=1001
Since 75 +2 == 77 check 13*76 = 988 and stop.
13*75<976<13*76. 75 is quotient

repeated subtraction would never give you the answer , try 10/2 for that matter

int quotient(int number,int div){
int count= 1 ;
while(div*count <= number){
count++;
}
return (count-1) ;
}

but for TopCoder thing to work, the number must be divisible right ? I mean if its 10/2 then it works..
if its 18/4 ? please suggest..

#include<stdio.h>
main()
{
int a=10,b=2;
int j=0;
while(a >= b)
{
a=a-b;
j++;

}
printf("value=%d\n",j);
}

a/b is a number between 1 and a. binary search.

For finding A/B
1. Check B < A
2. If yes, then check 2*B < A
3. If yes, then check 4*B < A
4. Keep on doing till you find 2^(N+1)*B > A > 2^N * B

Then you know the range and you just have to do binary search in between them
1. Find a number K between 2^N and 2*2^N such that K*B < A < (K+1)*B


Ex: 976/13

13 < 976
26 < 976
52 < 976
104 < 976
208 < 976
416 < 976
832 < 976
1664 > 976

So search between 64*13 and 128*13.

Complexity of solution O(Log(Q)) , Q is the quotient

Let us take a = 976 and b = 13.
Find the first k so that 13^k >=9 76. Equality we are done.
Here k = 3. We have 13^3 = 2197.
13^3 = 13(169).
Note: All division by 2 can done by >> 1.
(1 +169)/2 = 85. So have the following sequence.
13*1, 976, 13*85 = 1105
Find (1+85)/2 = 43 ,
So we have 13*43= 559, 976,13*85=1105.
Find (43+85)/2 = 64 , and 13*64 = 832.
So we have 13*64 = 832, 976, 13*85=1105.
Find (64+85)/2 = 74 and 13*74 = 962.
So we have 13*74=962, 976, 13*85=1105.
(74+85)/2 = 80 = 1040,
So we have 13*74=963,976,13*80=1040
(74+80)/2 = 77 , and 13*77 = 1001.
So we have 13*74=963, 976,13*77=1001
(74+77)/2 = 75, and 13*75 = 975,
So we have 13*75=975, 936,13*77=1001
Since 75 +2 == 77 check 13*76 = 988 and stop.
13*75<976<13*76. 75 is quotient