[algogeeks] Re: divide two extremely large numbers
If you can use a library search for GMP or GMPQ and related (depend on the numbers domain ) . Denis On 4 Set, 19:36, ankur aggarwal ankur.mast@gmail.com wrote: Write an algorithm two divide two extremely large numbers, which cannot be stored in an int, long int, float, double etc. Find the remainder and quotient . --~--~-~--~~~---~--~~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: addition without using arithmetic operators
On Tue, Sep 8, 2009 at 2:09 AM, ayush chauhan therajput.ay...@gmail.comwrote:
Cud u plz explain the logic behind this?
On Mon, Sep 7, 2009 at 9:44 PM, Gokul spgo...@gmail.com wrote:
you can try this..
int add(int x, int y)
{
if (!x) return y;
else
return add((x y) 1, x ^ y);
}
Lets consider you want to add 34590 and 987387065 in decimal notation.
9 8 7 6 8 7 0 6 5
+ 3 4 5 5 9 0
---
9 8 7 9 2 2 5 5 5 addition of digits neglecting carry
+ 0 0 0 1 1 0 1 0 0 --- represents carry
--
9 8 7 0 3 2 6 5 5
+ 0 0 1 0 0 0 0 0 0
---
9 8 8 0 3 2 6 5 5
+ 0 0 0 0 0 0 0 0 0
So ans is 988032655.
Similarly, In terms of bit representation, for addition of two numbers 'x'
and 'y', (xy)1 represents the carry number and x^y represents the number
neglecting the carry. So for example let the number is 43 14.
x = 43 = 1 0 1 0 1 1
y = 14 = 0 0 1 1 1 0
1 0 1 0 1 1
+ 0 0 1 1 1 0
--
1 0 0 1 0 1 --- x^y
+ 0 1 0 1 0 0 --- (xy)1
--
1 1 0 0 0 1
+ 0 0 1 0 0 0
--
1 1 1 0 0 1
+ 0 0 0 0 0 0
--
hence 43 + 14 = 111001 = 57
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: N number apples needs to distribute across M num baskets of varying capacity in balanced way
Consider the method used to apportion seats in the United States House of Representatives: http://mathdl.maa.org/mathDL/46/?pa=contentsa=viewDocumentnodeId=3163bodyId=3392. Dave On Sep 9, 1:24 am, Sandeep .A.S. reachtosand...@gmail.com wrote: Hi, Please let me know is there any standard algorithm to solve the below mentioned problem. Problem statement: I am having 10 apples and 4 basket each basket capacity is as mentioned below: Basket1 : capacity can hold maximum of 2 apples Basket2 : capacity can hold maximum of 4 apples Basket3 : capacity can hold maximum of 6 apples Basket4 : capacity can hold maximum of 8 apples I want to distribute the apples based on percentage contribution of each basket to total number of apples can accommodate by all the basket For the above example the 10 apples can be distributed as follows: 1 apple for basket1 (10% = (basket1 capacity/ total of all basket capacity) *100 = (2/20) *100) 2 apple for basket1(20% =(basket2 capacity/ total of all basket capacity) *100 = (4/20) *100) 3 apples for basket 3(30% = (basket3 capacity/ total of all basket capacity) *100 = (6/20) *100) 4 apples for basket 4(40% = (basket4 capacity/ total of all basket capacity) *100 = (8/20) *100) In the above example what if I have 13 apples? What is the best approach to solution which is near to optimal balance? I request you to provide the idea to resolve this problem. Thanks Regards, Sandeep --~--~-~--~~~---~--~~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: nth number of k bits
I think this should be easy to understand.
#includeiostream
using namespace std;
// this function generated next big number of the list having k bit set.
unsigned next_number( unsigned x)
{
unsigned smallest, ripple, one;
smallest = x (-x);
ripple = x + smallest ;
one = ripple^x;
one = (one2)/smallest;
return ripple | one ;
}
// this function first set the initial to the first element of the list and
then call next_number function //(n-1) times to get nth element of the list.
unsigned int nth_number_of_k_setbit(unsigned int k, unsigned n)
{
unsigned initial = 1,i ;
for (i = 0; i (k-1); i += 1)
initial = (initial1) | (1);
for (i = 0; i n-1; i += 1)
initial = next_number( initial);
return initial;
}
int main()
{
coutenter the value of kendl;
unsigned k;
cink;
coutenter the value of nendl;
unsigned n;
cinn;
cout.setf(ios::hex, ios::basefield);
coutnth number of the increasing order of k-bit set list
is:nth_number_of_k_setbit(k,n);
coutendl;
return 0;
}
hope this should help you.
--
Ashish Gupta
Ph. no. +91 9795 531 047
On Thu, Aug 27, 2009 at 10:35 PM, ankur aggarwal
ankur.mast@gmail.comwrote:
@shishir
plz give an example..
its bit tough to understand for me atleast..
On Thu, Aug 27, 2009 at 6:10 PM, Shishir Mittal 1987.shis...@gmail.comwrote:
Its a bit similar to finding the rank of the word COMPUTER in the
dictionary among the words formed from C,O,M,P,U,T,E,R.
Find maximum r such that (k+r)C(r) n.
This represents the total number of numbers formed from 'r' 0 bits and 'k'
1 bits. Since n is greater, it implies it has an extra 1 bit in its
representation.
The problem reduces to finding [n - (m+r)C(r)] smallest number than can be
formed with (k-1) 1 bits.
here is a recursive function to obtain the result.
int rec(int curr, int n, int k){
int r,j,comb,tmp;
if(n==1)
return curr+((1k) - 1); /* 1st number in the sequence with m bits.
*/
for(r =1,comb = 1; ; r++)
{
tmp = (comb*(k+r))/r; /* k+rCr = (k+r-1)C(r-1) x (k+r)/r*/
if(tmp == n)
return curr + (1(k+r)) - (1r); /* All the 'k' left most bits
should be 1 and rest 0 */
else if(tmp n)
return rec(curr+(1(k+r-1)), n-comb,k-1);
comb= tmp;
}
}
Call rec(0,n,k) to get the nth number of the series with 'k' bits set.
On Thu, Aug 27, 2009 at 12:28 PM, ankur aggarwal
ankur.mast@gmail.com wrote:
Nth number with K set bits
We are given with k number of set bits (bit=1). We have to find the Nth
number which has k set bits.
for example
k=3
the numbers with k set bits are as follows:
000111 = 7
001011 = 11
001101 = 13
001110 = 14
010011 = 19
010101 = 21
010110 = 22
011001 = 25
011010 = 26
011100 = 28
and so on
we have to find the Nth number in this series...
suggest some method
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
