I think that this code can suffice.
http://www.ideone.com/ESW8Z
#includestdio.h
int solve(int,int);
int main()
{
printf(%d,solve(100,10));
return 0;
}
int solve(int a,int b)
{
int quotient=0,k=0;
if(ab)
return quotient;
while((1k)*b=a)
{
k++;
}
k--;
@Saurabh: According to the statement of the problem using
multiplication is not allowed, but you can replace (1k)*b by bk to
eliminate your multiplications.
Dave
On Aug 27, 2:49 am, saurabh modi saurabhmodi102...@gmail.com wrote:
I think that this code can suffice.
http://www.ideone.com/ESW8Z
haha yeah okay..that can be done :-)
i had forgotten abt *
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
@Dave Yup, but Overall Complexity Will remain O(log(Quotient)) as
y=logn^k=klogn=O(logn) where k is constant
isn't it ? Also case of -Ive Numbers Can be handled easily :)
*Thanks
Shashank Mani
Computer Science
Birla Institute of Technology Mesra*
--
You received this message because you
@Shashank: Regarding the complexity, let's say that you are dividing
15 by 1. The on the original call, you will shift 4 times, on the
first recursive call, 3 times, then 2 times, then 1 time. This is a
total of ten shifts. This is log(quotient) * (log(quotient) - 1) / 2,
which is
@Dave True :)
*Thanks
Shashank Mani
Computer Science
Birla Institute of Technology Mesra*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/mSeEd-_wRcMJ.
@Dave , You are right , i mean to say we reduce the number of instruction or
comparisons executed by the program. ,Never Mind here is recursive code for
doing the same , Algorithm is already explained
#includeiostream
using namespace std;
int dividend,divisor,remainder;
int division(int
//works only for ints
#includestdio.h
int div(int a,int b);
main()
{
int q,w,x;
scanf(%d %d,q,w);
x=div(q,w);
printf(%d,x);
}
int div(int x,int y)
{
int z=x,count=0;
while(z=y)
{
z-=y;
count++;
}
return count;
}
--
You received this message because you are subscribed to the
@Teja: The complexity of your code is O(quotient). Code has been
presented that is O(log(quotient)).
Dave
On Aug 23, 8:47 am, teja bala pawanjalsa.t...@gmail.com wrote:
//works only for ints
#includestdio.h
int div(int a,int b);
main()
{
int q,w,x;
scanf(%d %d,q,w);
x=div(q,w);
@Shashank: Hmmm. In the recursive call, you use the variable divisor,
but I don't see anything assigned to it.
Furthermore, you don't handle negatives, which accounted for almost
half of my code.
In addition, you have to shift the divisor left multiple times in each
recursive call to align it
@Lucky sorry for delay, I am saying compelxity will be number if bits
required to represent quioutent , i think you just try with exmple i have
given
@Dave I didn't See The Whole Code but i think Logic Will Remain The Same.i
Think You forgot to give algorithm :P
also we can reduce the line of
@Shashank: I didn't know that reducing the number of lines of source
code was the goal. Often-times, efficiency demands more code rather
than less. For example, back in the days of the Cray-1 supercomputer,
which had vector registers and could do an operation on up to 64
operand pairs in one
We can use bit logic to reduce the time complexity to O(logn) where n is
Quotient
Algorithm will be as follow as we know
1. Left shifting an unsigned number by 1 multiplies that number by 2.
2. Right shifting an unsigned number by 1 divides that number by 2.
Therefore the procedure for the
@Shashank : Nice solution :)
*Regards
Sanju
Happy to Help :)*
On Fri, Aug 19, 2011 at 2:36 AM, WgpShashank shashank7andr...@gmail.comwrote:
We can use bit logic to reduce the time complexity to O(logn) where n is
Quotient
Algorithm will be as follow as we know
1. Left shifting an
@dave: actually how did u get the approach to this? I mean why did u have to
do the q|=1 in the if(a=b) condition and q=1 always in the loop?
On Fri, Aug 19, 2011 at 1:46 PM, Sanjay Rajpal tosanjayraj...@gmail.comwrote:
@Shashank : Would you throw some light on how you determined the complexity
@Arun: Just think about doing long division with paper and pencil. The
q=1 statement is the same as bringing down a new digit. Doing so
also expands the quotient by one digit. The q|=1 statement is the same
as writing down a nonzero digit in the quotient.
Dave
On Aug 19, 10:31 am, Arun
@Sanjay: Shashank was just reiterating what I said in
http://groups.google.com/group/algogeeks/msg/8590f8a2a8408d93. The
algorithm Shashank described is what I had previously provided code
for in http://groups.google.com/group/algogeeks/msg/735671f6a1e16eec,
with a correction in
@Dave : How did you approach this solution to this problem ?
and how you saw that th complexity is O(log_2(Quotient)) ?
*Regards
Sanju
Happy to Help :)*
On Fri, Aug 19, 2011 at 8:44 AM, Dave dave_and_da...@juno.com wrote:
@Sanjay: Shashank was just reiterating what I said in
exp(ln(a)-ln(b))
On Aug 18, 8:56 am, radha krishnan radhakrishnance...@gmail.com
wrote:
how to do using BIT manipulation ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To
@Don: Try it with a = b = -1.
Dave
On Aug 18, 9:45 am, Don dondod...@gmail.com wrote:
exp(ln(a)-ln(b))
On Aug 18, 8:56 am, radha krishnan radhakrishnance...@gmail.com
wrote:
how to do using BIT manipulation ?
--
You received this message because you are subscribed to the Google Groups
@Radha: You could simulate long division. It would look something like
this:
int divide(int a, int b)
{
int i, k=0, q=0, s=1;
// error checking
if( b == 0 ) return 0 // return 0 for division by zero
// handle signs
if( a 0 )
{
a = -a;
s = -1;
}
if( b 0 )
how abt subtracting . like a=a-b till a becomes zero . no of times
subtraction is done is the answer .
correct me if i am wrong !
On Thu, Aug 18, 2011 at 8:59 PM, Dave dave_and_da...@juno.com wrote:
@Radha: You could simulate long division. It would look something like
this:
int divide(int
wat about shifting 'a' right by floar(log2(b)) and adding 1 to it..
On Aug 18, 8:48 pm, aditya kumar aditya.kumar130...@gmail.com wrote:
how abt subtracting . like a=a-b till a becomes zero . no of times
subtraction is done is the answer .
correct me if i am wrong !
On Thu, Aug 18,
@Aditya: Not wrong, but inefficient and inelegant. Repeated
subtraction has complexity O(quotient), while long division has
complexity O(log quotient).
Dave
On Aug 18, 10:48 am, aditya kumar aditya.kumar130...@gmail.com
wrote:
how abt subtracting . like a=a-b till a becomes zero . no of times
@Dheeraj: What about it? It doesn't give the quotient. What is it
supposed to do?
Dave
On Aug 18, 11:06 am, DheerajSharma dheerajsharma1...@gmail.com
wrote:
wat about shifting 'a' right by floar(log2(b)) and adding 1 to it..
On Aug 18, 8:48 pm, aditya kumar aditya.kumar130...@gmail.com wrote:
@dave: in your algorithm, I have a doubt in the second loop( for loop ).
q=0 initially so the first q1 stays zero and then q|=1 makes q=1 now.
1 then becomes x 2 and then again with the OR 2 becomes 3.
3 becomes 6 and with the OR 6 becomes 7.
for example if i need to do 24/3, according to the
@Arun: Oops. It looks like the while loop condition should be b = a
instead of b a, and the if condition within the for loop should be
a = b instead of a b. I'm glad I equivocated with the phrase
would look something like.
With a = 24 and b = 3, the while loop shifts b left and increments k
27 matches
Mail list logo
