date:20100503

Re: [algogeeks] value of n

2010-05-03 Thread Sundeep Singh

oops 

On Sat, May 1, 2010 at 5:50 PM, Sundeep Singh singh.sund...@gmail.comwrote:

 Hi Amit,

 here's the answer: (I am assuming in your equation lg implies log to the
 base 10)
 n  8 log(n)
 = n/8  log(n)
 = 10 ^(n/8)  n


The final deduction was incorrect!!
for log base 10, the answer is:
2 = n = 6

--Sudneep.



 = n  8

 --Sundeep.



 On Sat, May 1, 2010 at 10:43 AM, Amit Agarwal lifea...@gmail.com wrote:

 I could not get you properly. This is an equation comes from the problem
 statement where I need to find out cut-off value of n between insertion and
 merge sort. I think equation is part of basic mathematics but I don't
 remember how do I solve it.


 -Regards
 Amit Agarwal
 Contact: 09765348182
 www.amitagrwal.com




 On Sat, May 1, 2010 at 9:13 AM, abhijith reddy 
 abhijith200...@gmail.comwrote:

 binary search on n

 On Fri, Apr 30, 2010 at 10:15 PM, Amit Agarwal lifea...@gmail.comwrote:

 how do I compute n from this equation.
 n  8lg(n)

 --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] Where does OS scheduling run??

2010-05-03 Thread Varun Nagpal

I think its a good question and fairly complicated to explain at
hardware(RTL) level. Anyways, let me give it a try :

You suggested that only 1 instruction is executed by one processor,
which is not true(if you have read computer architecture). Briefly,
lets assume the instruction pipeline(assuming only single hardware
thread) is filled with instructions from the present thread(or
process) of execution. Assume number of pipeline stages to be 20. In
the pipeline, 20 instructions from the current instruction control
flow are executing synchronously on every clock tick. Depending upon
the design of pipeline, data from registers/memory is read in
different pipeline stages. Also there may also be many execution
stages(ALU) before the data is written to register/memory.

The OS kernel keeps a track of all the threads/processes presently
executing, active, waiting, suspended etc. in memory in the form of a
data structure, which is to say that it always knows the next
thread/process it needs to schedule on to the processor. I think it
has a compare register that stores an arbitrary number(as decided by
kernel) of clock ticks for a time slice expiry and keeps another
counter register to keep track of time slice expiration for present
thread. At every clock tick, it increments the counter register and
compares it with compare register. This summing and comparison is done
by inserting an instruction in the current instruction flow.  The
point is that a clock interrupt is generated whenever the values of
the counter and the compare registers match. When this does occur, the
next PC value,registers etc(i.e its context information) is pushed
onto the stack and a jump is made to an area in memory storing an
interrupt vector table. I also assume that when this jump is made, the
OS kernel supplies some information to the jump instruction about the
next thread to be executed. This information maybe stored in another
dedicated register. Now by using this information and interrupt vector
table, it can find out the memory address of next thread(ii.e next
instruction) to be executed. The PC including other registers is then
simply loaded with context information of the new thread.

Important thing here is again that when all of this is happening, the
pipeline may still be executing instructions from the previous thread.
In addition it will contain interrupt instructions! Only when PC is
updated(in some stage of pipeline) that the instruction fetch stage
will start fetching instructions from instruction memory area of new
thread. In a 20 stage pipeline, it is still highly likely that it may
be the case that pipeline contains instructions from old thread,
followed by interrupt instruction , followed by instructions from new
thread.

I hope this explanation should give you better clarity.

On Sun, May 2, 2010 at 7:01 PM, harit agarwal agarwalha...@gmail.com wrote:
 although CPU is busy in exexcution...it check's its registers values for the
 pending interrupts ..
 if any interrupt is pending at the end of the current CPU cycle...it
 shedules the interrupt handler to further execute the interrupt
 subroutine...

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@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?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] 400!

2010-05-03 Thread siddharth srivastava

But is there any way to accomplish this without an array ? Even for 100!.

On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote:

I think challenge here is not the Execution time, but the storage. 300 ! or
400! should generally go beyond the storage capabilities of long long ints
in cpp.
@ Rohit Saraf: Hence, I don't know if even tail recursion will ultimately
be able to store the output.
I think Rajesh Patidar's answer fits the bill well, in terms of storage.

On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:

I agree with abhijith. But given some very large x for which i would have
to find factorial.
I would either
(i) use gmp in cpp or BigInteger or java if its not a lab exercise or an
interview
(ii) use simple brute multiplication algorithm.
The second approach requires
(a) The no. of digits in n! for making storage available
(b) The calculation itself which I would brute force

References:

http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html

http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it
http://delphiforfun.org/programs/big_factorials.htm

On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:

google it... u will gt it

i am on mobile... cannot explain now..

On 5/2/10, divya jain sweetdivya@gmail.com wrote:
wat is tail recursion plz explan in detail

On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:

@divya use tail recursion and rest should be fine..

--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
http://www.cse.iitb.ac.in/%7Erohitfeb14

--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com

.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
There are two kinds of people. Those who care for others and The others

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
Siddharth Srivastava

Human Knowledge is for all

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] Re: a google question

2010-05-03 Thread Varun Nagpal

Guys no one commented on my solution? Any takes on it?


Anyways, below is my solution (in pseudo code)

Pre-condition: A and B are sequences of equal length and sorted in
descending order
Input: Sequences A[1..N] and B[1..N] of equal lengths(N)
Ouput: Sequence C[1..N] containing sorted sum of ordered pairs from
cartesian products of A, B or B,A

Sort(A,B)
{
 k = 1
 N = length(A) = length(B)
 C[1..2*N] = []// Empty array
 cart_prod_order = 0   // 0 - AxB, 1 - BxA. 0 is default

 // Complexity : O(N)
 while(k != N+1)
 {
   if (A[k]  B [k])
   {
cart_prod_order = 1
break
   }
   else
   {
k = k + 1
   }
 }

 // Choose the correct order of Cartesian product sum
 // Complexity: Theta(2N) = O(N)
 if (cart_prod_order == 1)
 {
// take cartesian product of B and A, storing the sum of ordered
pair (b,a) in each element of C
C[1..2N] = B[1..2] x A[1..N]
 }
 else
 {
   // take cartesian product of A and B, storing the sum of ordered
pair (a,b) in each element of C
   C[1..2N] = A[1..2] x B[1..N]
 }

 // Merge
 // C[1..N] and C[N+1..2N] are already sorted in descending order
 // Complexity: Theta(N)
 C[1..2N] = Merge(C[1..N],C[N+1..2N])

 return C[1..N]
}

Merge(C,D)
{
 i=1,j=1,k=1
 E = []
 while(i=length(C) OR j=length(D))
 {
   if(i=length(C) AND (jlength(D) OR C[i]D[j]))
   {
E[k] = C[i]
i = i + 1
   }
   else
   {
E[k] = D[j]
j = j + 1
   }
   k = k + 1
 }

 return E;
}

On Fri, Apr 30, 2010 at 7:50 PM, banu varun.nagp...@gmail.com wrote:
 Nice question:

 1. |A| = |B| i.e I assume their cardinality is equal

 2. A(n) = { a1, a2  a3, ...aN} such that a1=a2=a3...=aN
 3. B(n) = { b1, b2  b3, ...bN} such that b1=b2=b3...=bN

 4. S(n^2) = A x B = {(a1,b1), (a1,b2)(a1,bN),
                              (a2,b1), (a2,b2)(a2,bN),
                               
                              (aN,b1), (aN,b2)(aN,bN)}

  assuming we have added in a way such that we find a pair  ai  bi,
 for some i in 1..N such that a(i-1) = b(i-1)

 A first observation is that in the worst case, the first 2N numbers in
 S will contain the final result of N numbers.
 i.e in  (a1,b1), (a1,b2)(a1,bN), (a2,b1), (a2,b2)(a2,bN)

 In the best case first N numbers in S will contain the final N numbers
 (already sorted in decreasing order)
 i.e in  (a1,b1), (a1,b2)(a1,bN)

 Now, if we consider again the worst case scenario, then we can first
 divide 2N numbers in two groups of size N each and each of this group
 is already sorted in decreasing order.
 i.e  (a1,b1), (a1,b2)(a1,bN) and (a2,b1), (a2,b2)(a2,bN)

 Now we can simply apply Merge Algorithm on these 2 already sorted
 arrays of size N each in O(N) time, which solves the problem

 I can be wrong only if the the results lie outside first 2N
 numbers(which I hope is not the case).


 On Apr 30, 2:05 pm, divya sweetdivya@gmail.com wrote:
 Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's
 say they are decreasingly sorted), we define a set S = {(a,b) | a \in
 A
 and b \in B}. Obviously there are n^2 elements in S. The value of such
 a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
 from S with largest values. The tricky part is that we need an O(n)
 algorithm.

 --
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to 
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group 
 athttp://groups.google.com/group/algogeeks?hl=en.

 --
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To post to this group, send email to algoge...@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?hl=en.



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] 400!

2010-05-03 Thread Rohit Saraf

are forget abt representation. It can be stored as string anyways.
Tail recursion is awesome at times !

--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14

On Mon, May 3, 2010 at 9:46 AM, siddharth srivastava akssps...@gmail.comwrote:

But is there any way to accomplish this without an array ? Even for 100!.

On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote:

I think challenge here is not the Execution time, but the storage. 300 !
or 400! should generally go beyond the storage capabilities of long long
ints in cpp.
@ Rohit Saraf: Hence, I don't know if even tail recursion will ultimately
be able to store the output.
I think Rajesh Patidar's answer fits the bill well, in terms of storage.

On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:

References:

http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html

http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it
http://delphiforfun.org/programs/big_factorials.htm

On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:

google it... u will gt it

i am on mobile... cannot explain now..

On 5/2/10, divya jain sweetdivya@gmail.com wrote:
wat is tail recursion plz explan in detail

On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:

@divya use tail recursion and rest should be fine..

.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14

--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
There are two kinds of people. Those who care for others and The others

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
Siddharth Srivastava

Human Knowledge is for all

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For

Re: [algogeeks] tree from linked list

2010-05-03 Thread Rohit Saraf

1) Make the middle element the root.
 Recursively make the left and right subtrees from the left and right
halves of the link list.

2) Implement balanced insertion in trees (via rotations on every step...).
Now insert each element
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14


On Sun, May 2, 2010 at 6:38 PM, divya sweetdivya@gmail.com wrote:

 u are given a sorted lnked list construct a balanced binary search
 tree from it.

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] 400!

2010-05-03 Thread Jitendra Kushwaha

You can do it easily in python...:)
Here is the python code

n=400
def fact(num):
ans = 1
while(num):
ans = ans*num
num = num-1
return ans
print fact(n) #printing 400!

even 1000! can be calculated

Regards
Jitendra Kushwaha
Undergradute Student
Computer Science  Eng.
MNNIT, Allahabad

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] tree from linked list

2010-05-03 Thread jalaj jaiswal

for simplicity in writin algo i've taken sorted array instead of list
struct node * create( int *sorted,number of elements){
 struct node *temp,*left,*right;
 int tempii[100],tempiii[100];
 if(number of elemnts ==0)
   return NULL;
 temp-data=sorted[mid];
 temp-left=NULL;
 temp-right=NULL;
 if number of elements == 1
return temp;
 int count=0;
 for(int i=0;imid;i++){
 tempii[i]=sorted[i];
 count++;
 }
 left=create(int *tempii,count);
 temp-left=left;
 count=0;
 for(i=mid+1;inumberofelemnts;i++){
   tempiii[i]=sorted[i];
   count++;
 }
 right=create(int *tempiii,count);
 temp-right=right;

 return temp;
}

On Mon, May 3, 2010 at 5:36 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:

 1) Make the middle element the root.
  Recursively make the left and right subtrees from the left and right
 halves of the link list.

 2) Implement balanced insertion in trees (via rotations on every step...).
 Now insert each element
 --
 Rohit Saraf
 Second Year Undergraduate,
 Dept. of Computer Science and Engineering
 IIT Bombay
 http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14



 On Sun, May 2, 2010 at 6:38 PM, divya sweetdivya@gmail.com wrote:

 u are given a sorted lnked list construct a balanced binary search
 tree from it.

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] Re: a google question

2010-05-03 Thread Jitendra Kushwaha

The Question only ask to print first n number and each array array is of
size n
So in the worst case  we will take combination of 1st element of first array
with all the element of second array.

my above code runs in O(n) taking this considerations... any comments or
test case where it fails???


Regards
Jitendra Kushwaha
Undergradute Student
Computer Science  Eng.
MNNIT, Allahabad

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] 400!

2010-05-03 Thread divya jain

nice algo by rajesh.
bt i think using linked list will be better..

On 3 May 2010 09:46, siddharth srivastava akssps...@gmail.com wrote:

But is there any way to accomplish this without an array ? Even for 100!.

On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote:

I think challenge here is not the Execution time, but the storage. 300 !
or 400! should generally go beyond the storage capabilities of long long
ints in cpp.
@ Rohit Saraf: Hence, I don't know if even tail recursion will ultimately
be able to store the output.
I think Rajesh Patidar's answer fits the bill well, in terms of storage.

On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:

References:

http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html

http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it
http://delphiforfun.org/programs/big_factorials.htm

On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:

google it... u will gt it

i am on mobile... cannot explain now..

On 5/2/10, divya jain sweetdivya@gmail.com wrote:
wat is tail recursion plz explan in detail

On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:

@divya use tail recursion and rest should be fine..

.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14

--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
There are two kinds of people. Those who care for others and The others

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
Siddharth Srivastava

Human Knowledge is for all

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to

Re: [algogeeks] 400!

2010-05-03 Thread vignesh radhakrishnan

@siddharth and prasoon either design a very long integer library yourself,
or use gmp library in cpp or BigInteger Class in java.

Regards,
vignesh

On 3 May 2010 09:46, siddharth srivastava akssps...@gmail.com wrote:

But is there any way to accomplish this without an array ? Even for 100!.

On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote:

I think challenge here is not the Execution time, but the storage. 300 !
or 400! should generally go beyond the storage capabilities of long long
ints in cpp.
@ Rohit Saraf: Hence, I don't know if even tail recursion will ultimately
be able to store the output.
I think Rajesh Patidar's answer fits the bill well, in terms of storage.

On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:

References:

http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html

http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it
http://delphiforfun.org/programs/big_factorials.htm

On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:

google it... u will gt it

i am on mobile... cannot explain now..

On 5/2/10, divya jain sweetdivya@gmail.com wrote:
wat is tail recursion plz explan in detail

On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:

@divya use tail recursion and rest should be fine..

.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14

--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
There are two kinds of people. Those who care for others and The others

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
Siddharth Srivastava

Human Knowledge is for all

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
There are two kinds of people. Those who care for others

Re: [algogeeks] Re: a google question

2010-05-03 Thread divya jain

@satish

ur solution is of o(nlogn) complexty

@ jitendra

suppose p11 and p21 r pointing at index 0 and p12 at 4 and p22 at 1. now
suppose at ths point d s greater than b and c. now u increment p11 and p21.
but it can be a case that a[0] + b[2] is next greatest  value bt t wont
work for ur algo.

On 3 May 2010 00:46, Shishir Mittal 1987.shis...@gmail.com wrote:

 @Algoose : No, it is not necessary that first n elements must contain A[0]
 or B[0]. For e.g.
 A = {40,30,15,10}
 B = {40,30,15,10}

 Required 4 largest values = {40+40, 40+30, 40+30, 30+30}.


 @Satish:
 A very nice algorithm provided by you.
 Complexity Analysis for the algorithm provided by you:

 Creation of max-heap of n elements = O(n).
 Time to add a new element to the heap after extracting the maximum - O(log
 n)
 Overall Complexity = O(n log n)

 Regards,
 Shishir


 On Sun, May 2, 2010 at 10:52 PM, Satish satish.mit...@gmail.com wrote:

 This problem can be simplified to a variation of merge part of merge
 sort algorithm.

 - Break the set S having n^2 values into n individual arrays of length
 n, say S1, S2,..Sn, where S1 = [a1+b1, a1+b2,...a1+bn].
 - One can observe that each Si has entries which are themselves sorted
 within Si.
 - Perform merge of S1, S2,..Sn where take the largest values of each
 Si, and create a heap of these individual max values.
 - In each step, return the max value from heap and then add the next
 max value from the Si that had the current max value and add it in the
 max-heap.
 - Repeat this step n times and then exit.

 Time: O(n).

 Satish

 On May 2, 5:41 pm, Algoose Chase harishp...@gmail.com wrote:
  Hi
 
  will this work ?
 
  since we need Set S with n pairs of largest values , any such pair
 within
  the set would (always) contain A[0] or B[0] because they maximize the
 value
  of the pair.
 
  so
 
  // code snippet
  typedef std::vectorint,int Pairs;
 
  Pairs.push(A[0],B[0])
  int i = 1; // index for ListA
  int j = 1; // index for list B
  count = 1;
  while( count = n)
  {
if( A[0] + B[j]  B[0] + A[i] )
{
  Pairs.push(A[0],B[j])
  j++;
}
else
{
   Pairs.Add(A[i],B[0])
   i++;
}
count++;
 
  }
 
  since there are n items in both the lists, j and i wont go beyond n in
 the
  while loop
 
 


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] 400!

2010-05-03 Thread Rajesh Patidar

you have to store the result some where for that you don't have
inbuilt datatype like python those will take care of your overflow

On Mon, May 3, 2010 at 9:46 AM, siddharth srivastava
akssps...@gmail.com wrote:
But is there any way to accomplish this without an array ? Even for 100!.

On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote:

I think challenge here is not the Execution time, but the storage. 300 !
or 400! should generally go beyond the storage capabilities of long long
ints in cpp.
@ Rohit Saraf: Hence, I don't know if even tail recursion will ultimately
be able to store the output.
I think Rajesh Patidar's answer fits the bill well, in terms of storage.

On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:

References:

http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html

http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it
http://delphiforfun.org/programs/big_factorials.htm

On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:

google it... u will gt it

i am on mobile... cannot explain now..

On 5/2/10, divya jain sweetdivya@gmail.com wrote:
wat is tail recursion plz explan in detail

On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:

@divya use tail recursion and rest should be fine..

--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay

http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14

algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14

--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

--
There are two kinds of people. Those who care for others and The others

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

--
Siddharth Srivastava

Human Knowledge is for all

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

--
BL/\CK_D!AMOND

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] value of n

2010-05-03 Thread Amit Agarwal

yeah, you are right. It comes from 2 to 6. But is there any way to solve it
on paper?
-Regards
Amit Agarwal
Contact: 09765348182
www.amitagrwal.com



On Mon, May 3, 2010 at 3:02 PM, Sundeep Singh singh.sund...@gmail.comwrote:

 oops 

 On Sat, May 1, 2010 at 5:50 PM, Sundeep Singh singh.sund...@gmail.comwrote:

 Hi Amit,

 here's the answer: (I am assuming in your equation lg implies log to the
 base 10)
 n  8 log(n)
 = n/8  log(n)
 = 10 ^(n/8)  n


 The final deduction was incorrect!!
 for log base 10, the answer is:
 2 = n = 6

 --Sudneep.



 = n  8

 --Sundeep.



 On Sat, May 1, 2010 at 10:43 AM, Amit Agarwal lifea...@gmail.com wrote:

 I could not get you properly. This is an equation comes from the problem
 statement where I need to find out cut-off value of n between insertion and
 merge sort. I think equation is part of basic mathematics but I don't
 remember how do I solve it.


 -Regards
 Amit Agarwal
 Contact: 09765348182
 www.amitagrwal.com




 On Sat, May 1, 2010 at 9:13 AM, abhijith reddy abhijith200...@gmail.com
  wrote:

 binary search on n

 On Fri, Apr 30, 2010 at 10:15 PM, Amit Agarwal lifea...@gmail.comwrote:

 how do I compute n from this equation.
 n  8lg(n)

 --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] 400!

2010-05-03 Thread Anil C R

@Jitendra
but that's no fun [?]

-
Anil

On Mon, May 3, 2010 at 5:12 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:

@siddharth and prasoon either design a very long integer library yourself,
or use gmp library in cpp or BigInteger Class in java.

Regards,
vignesh

On 3 May 2010 09:46, siddharth srivastava akssps...@gmail.com wrote:

But is there any way to accomplish this without an array ? Even for 100!.

On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote:

I think challenge here is not the Execution time, but the storage. 300 !
or 400! should generally go beyond the storage capabilities of long long
ints in cpp.
@ Rohit Saraf: Hence, I don't know if even tail recursion will ultimately
be able to store the output.
I think Rajesh Patidar's answer fits the bill well, in terms of storage.

On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:

I agree with abhijith. But given some very large x for which i would
have to find factorial.
I would either
(i) use gmp in cpp or BigInteger or java if its not a lab exercise or an
interview
(ii) use simple brute multiplication algorithm.
The second approach requires
(a) The no. of digits in n! for making storage available
(b) The calculation itself which I would brute force

References:

http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html

http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it
http://delphiforfun.org/programs/big_factorials.htm

On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:

google it... u will gt it

i am on mobile... cannot explain now..

On 5/2/10, divya jain sweetdivya@gmail.com wrote:
wat is tail recursion plz explan in detail

On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com
wrote:

@divya use tail recursion and rest should be fine..

.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14

--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
There are two kinds of people. Those who care for others and The others

--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--
Siddharth Srivastava

Human Knowledge is for all

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more

[algogeeks] question

2010-05-03 Thread jalaj jaiswal

given an array(unsorted) may contain negative numbers too
find the index of three numbers whose sum is closest to zero  in  O(N2 log
N) time and O(N) space.

P.S -3 is more close to zero then -6 (number line ...)
-- 
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] Re: a google question

2010-05-03 Thread Jitendra Kushwaha

@divya

I try to simulate what you said for the given array

index : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
array1:8, 7, 4 ,3 , 2, 1, 1, 1, 1, 1
   ^  ^
  p11  p12

*p11 = 8 and  *p12 = 3

index : 0,  1,   2,   3,   4,  5,   6,  7, 8, 9
array2:34, 23, 21, 19, 15, 13, 11, 8, 4, 2
   ^^
  p21 p22

*p21 = 34 and  *p22 = 23

a =  8 + 34 = 41//arr1[0] + arr2[0]
b = 8 +23 = 31//arr1[0] + arr2[1]
c = 34 + 3 = 37   //arr1[4] + arr2[0] greatest !!!
d = 7 +23 = 30 //arr1[1] + arr2[1]

arr1[0] + arr2[2] = 29   which is less than c..

here is my output

  arr1[0] + arr2[0] = 42
  arr1[1] + arr2[0] = 41
  arr1[2] + arr2[0] = 38
  arr1[3] + arr2[0] = 37
  arr1[4] + arr2[0] = 36
  arr1[5] + arr2[0] = 35
  arr1[6] + arr2[0] = 35
  arr1[7] + arr2[0] = 35
  arr1[8] + arr2[0] = 35
  arr1[9] + arr2[0] = 35

i have attached the code try with  replacing arr1 and arr2 with
following.and the case u wanted to point out will be taken throught in
following test case..(arr1[0] + arr2[1] = 9+27 = 36  will be taken before
arr1[6] + arr2[0] = 1+34 = 35 )

int arr1[N] = {9,7,4,3,2,1,1,1,1,1};
int arr2[N] = {34,27,21,19,15,13,11,8,4,2};

Regards
Jitendra Kushwaha

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

#include cstdio
#includeiostream
using namespace std;

#define N 10

int main(void)
{
int arr1[N] = {8,7,4,3,2,1,1,1,1,1};
int arr2[N] = {34,23,21,19,15,13,11,8,4,2};
int *p11,*p12,*p21,*p22;
int w=0,x=0,y=0,z=0;
p11 = p12 = arr1;
p21 = p22 = arr2;
int f1;
f1 = 0;
   
for(int i=0;iN;i++) {
int ans=0;
int a,b,c,d;
a = *p11 + *p21;
b = *p11 + *p22;
c = *p21 + *p12;
d = *(p11+1) + *(p21+1);
   
//printf(a=%d b=%d c=%d d=%d\n,a,b,c,d); //debug
   
if(f1==0)ans = a  ,p12++ , p22++ , f1=1 , printf( arr1[%d] + arr2[%d] = ,w,y),x++,z++; 
   
else if(b = c  b = d )ans = b  , p22++ , printf( arr1[%d] + arr2[%d] = ,w,z),z++; 
   
else if(c = b  c = d )ans = c , p12++ ,  printf( arr1[%d] + arr2[%d] = ,x,y),x++; 
   
elseans = d , p11++ , p21++ ,  printf( arr1[%d] + arr2[%d] = ,w,y),w++,y++; 
   
printf(%d\n,ans);
}
}

Re: [algogeeks] Re: a google question

2010-05-03 Thread Jitendra Kushwaha

slight change in value of c

c = 34 + 2 = 36   //arr1[4] + arr2[0] greatest !!!

my mistake..

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] 400!

2010-05-03 Thread Varun Nagpal

@Rajesh gave a simple elegant solution.

A look at a Linux calculator : you can even calculate 99! =
8.854887824e+5584950 in few seconds. I just looked at the code(its open
source right!), which is not so easy to understand in few minutes.

Here is the some part of code I extracted from source files:

/* Size of the multiple precision values */
#define MP_SIZE 1000

/* Base for numbers */
#define MP_BASE 1

/* Object for a high precision floating point number representation
 *
 * x = sign * (MP_BASE^(exponent-1) + MP_BASE^(exponent-2) + ...)
 */
typedef struct
{
   /* Sign (+1, -1) or 0 for the value zero */
   int sign; //, im_sign;

   /* Exponent (to base MP_BASE) */
   int exponent; //, im_exponent;

   /* Normalized fraction */
   int fraction[MP_SIZE]; //, im_fraction[MP_SIZE];
} MPNumber;


void mp_factorial(const MPNumber *x, MPNumber *z)
{
int i, value;

/* 0! == 1 */
if (mp_is_zero(x)) {
mp_set_from_integer(1, z);
return;
}
if (!mp_is_natural(x)) {
/* Translators: Error displayed when attempted take the factorial of
a fractional number */
mperr(_(Factorial is only defined for natural numbers));
mp_set_from_integer(0, z);
return;
}

/* Convert to integer - if couldn't be converted then the factorial
would be too big anyway */
value = mp_cast_to_int(x);
mp_set_from_mp(x, z);
for (i = 2; i  value; i++)
mp_multiply_integer(z, i, z);
}

mp_multiply_integer(z, i, z) subroutine is too big too put in here, too see
its code visit:  http://live.gnome.org/Gcalctool
http://live.gnome.org/Gcalctool
On Mon, May 3, 2010 at 2:34 PM, Anil C R cr.a...@gmail.com wrote:

 @Jitendra
 but that's no fun [?]

 -
 Anil



 On Mon, May 3, 2010 at 5:12 PM, vignesh radhakrishnan 
 rvignesh1...@gmail.com wrote:

 @siddharth and prasoon either design a very long integer library yourself,
 or use gmp library in cpp or BigInteger Class in java.

 Regards,
 vignesh

 On 3 May 2010 09:46, siddharth srivastava akssps...@gmail.com wrote:

 But is there any way to accomplish this without an array ? Even for 100!.


 On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote:

 I think challenge here is not the Execution time, but the storage. 300 !
 or 400! should generally go beyond the storage capabilities of long long
 ints in cpp.
 @ Rohit Saraf: Hence, I don't know if even tail recursion will
 ultimately be able to store the output.
 I think Rajesh Patidar's answer fits the bill well, in terms of storage.


 On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan 
 rvignesh1...@gmail.com wrote:

 I agree with abhijith. But given some very large x for which i would
 have to find factorial.
 I would either
 (i) use gmp in cpp or BigInteger or java if its not a lab exercise or
 an interview
 (ii) use simple brute multiplication algorithm.
 The second approach requires
  (a) The no. of digits in n! for making storage available
  (b) The calculation itself which I would brute force

 References:

 http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html

 http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it
 http://delphiforfun.org/programs/big_factorials.htm



 On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:

 google it... u will gt it

 i am on mobile... cannot explain now..

 On 5/2/10, divya jain sweetdivya@gmail.com wrote:
  wat is tail recursion plz explan in detail
 
  On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com
 wrote:
 
  @divya use tail recursion and rest should be fine..
 
  --
  --
  Rohit Saraf
  Second Year Undergraduate,
  Dept. of Computer Science and Engineering
  IIT Bombay
  http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
 http://www.cse.iitb.ac.in/%7Erohitfeb14
 
  --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To post to this group, send email to algoge...@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
 
  .
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
 
 
  --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To post to this group, send email to algoge...@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
 


 --
 --
 Rohit Saraf
 Second Year Undergraduate,
 Dept. of Computer Science and Engineering
 IIT

Re: [algogeeks] Re: a google question

2010-05-03 Thread Varun Nagpal

@Jitendra
I dont think so.Try these 2 examples to check:

A[1..n]   :20 10 0
B[1..n]   :18 13 5
Ans   :38 33 28

A[1..n]   :20 10 0
B[1..n]   :18 17 16
Ans   :38 37 36

My conjecture is: In the worst case, instead of combination of 1st
element of first array with all elements of second array, we need to
instead choose 2 elements from first array and than take combination
with all elements of second array. Also before doing this we need to
choose from which array should these 2 elements be extracted. I have
already suggested before how to do this.

On Mon, May 3, 2010 at 1:23 PM, Jitendra Kushwaha
jitendra.th...@gmail.com wrote:
 The Question only ask to print first n number and each array array is of
 size n
 So in the worst case  we will take combination of 1st element of first array
 with all the element of second array.

 my above code runs in O(n) taking this considerations... any comments or
 test case where it fails???


 Regards
 Jitendra Kushwaha
 Undergradute Student
 Computer Science  Eng.
 MNNIT, Allahabad

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@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?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.

Re: [algogeeks] 400!

2010-05-03 Thread Rajesh Patidar

ya string one even will be more suitable way..

On Mon, May 3, 2010 at 5:33 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
are forget abt representation. It can be stored as string anyways.
Tail recursion is awesome at times !
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14

On Mon, May 3, 2010 at 9:46 AM, siddharth srivastava akssps...@gmail.com
wrote: