Re: [algogeeks] Re: how to solve this?

2013-04-04 Thread Shashwat Anand
@Dave solution is perfect. I prefer it over mind. However, here is an alternate solution. We know that this is an equation in 'x' with a degree of 1. It means it is a straight line and root is guaranteed unless of course the equation is of the form y = c. That is not the case here as it would m

[algogeeks] Re: how to solve this?

2013-04-04 Thread Don
I like that solution better than the one I suggested. Don On Apr 4, 4:45 pm, Dave wrote: > @Kumar0746: Technically, you can't solve an _expression_; you can solve an > _equation_, which is a statement of the form expression = expression, which > is what you have. > > Don's suggestion is a good on

[algogeeks] Re: how to solve this?

2013-04-04 Thread Dave
@Kumar0746: Technically, you can't solve an _expression_; you can solve an _equation_, which is a statement of the form expression = expression, which is what you have. Don's suggestion is a good one. Another way is to call the expression on the left side of the equation f(x) and the expressi

[algogeeks] Re: how to solve this?

2013-04-04 Thread Don
Simplify the expression by evaluating expressions inside parenthesis first. Follow the order of evaluation, doing multiplications first and then addition and subtraction. It should be possible to reduce any expression to the form ax+b=0. Then x=-b/a. Don On Apr 4, 11:18 am, arun kumar wrote: > Gi

[algogeeks] Re: How to solve this

2011-12-24 Thread Dave
@Ankur: Since the list is of infinite length, equal probability of selecting any given node is impossible. The probability distribution must be such that inf sum p(i) = 1. i = 0 I.e., the individual probabilities must form a convergent series, and thus p(i) --> 0. But a uniform distribution has

Re: [algogeeks] Re: How to solve this

2011-12-24 Thread Ankur Garg
The thing is ..will it ascertain that the probability is equal I am not sure how ur method guarantees that... May be if you and Dave can explain the algo a bit better that wud be great . regards Ankur On Sat, Dec 24, 2011 at 5:48 AM, Piyush Kansal wrote: > Hey Ankur, > > What is the order of ti

Re: [algogeeks] Re: How to solve this

2011-12-24 Thread atul anand
@piyush : O(n/2) is O(n) . your approach is good , it will efficient than linear search. On Sat, Dec 24, 2011 at 5:48 AM, Piyush Kansal wrote: > Hey Ankur, > > What is the order of time complexity we are looking for in this case. The > option which Dave suggested can give us random node by

[algogeeks] Re: How to solve this

2011-12-23 Thread Piyush Kansal
Hey Ankur, What is the order of time complexity we are looking for in this case. The option which Dave suggested can give us random node by traversing that many number of nodes from the head. That will be O(n). This can be further reduced to n/2 if we use two pointers, both of which will trave

[algogeeks] Re: How to solve this

2011-12-23 Thread Dave
@Ankur: The linked list is isomorphic to the non-negative integers, so selecting a random integer is equivalent to selecting a random node. There is no uniform distribution on the integers, so we can't find a uniform distribution on the nodes. One way to find a non-uniform distribution is by taking

Re: [algogeeks] Re: How to Solve This

2011-10-24 Thread Prabhat Kiran
Correct me if I am wrong, If the given number is lets say 'p'. We have to find N such that N=(10^m-1)/9 for least m,that is divisible by 'p'. (10^m-1)/9 = 0 (mod p) (10^m-1) = 0 (mod p) 10^m = 1 (mod p) Since the given number 'p' always ends with a 3 in its units place, 10^m and p are always c

[algogeeks] Re: How to Solve This

2011-10-13 Thread Gene
I should have noted that this can handle inputs up to about 2^32 / (10 * x). Run time is proportional to the number of 1's. You can also add a bit of code to discover the digits of the multiplicand. I was able to verify with lisp bignums that: 25,514 1's is equal to 76543 * ( a 25,509 digit numb

[algogeeks] Re: How to Solve This

2011-10-12 Thread Gene
First note: 0 * 3 = 0 7 * 3 = 21 4 * 3 = 12 1 * 3 = 3 8 * 3 = 24 5 * 3 = 15 2 * 3 = 6 9 * 3 = 27 6 * 3 = 18 3 * 3 = 9 Important is that the final digits of each line count 0 to 9. Now you can build an answer right to left. Example: 123. Check the table to get the rightmost 1. 7 * 123 = 861 N

[algogeeks] Re: How to Solve This

2011-10-12 Thread vikas
well , I tried to solve it from Maths though half way through only :( N = number required i.e. (10^k -1)/9 given n = 10x + 3 by eq (10x + 3) * m = N= (10^k - 1)/9 implies k = 2log 3 + log m + log(10x + 3) i.e. k > 1 + log n This gives the lowerbound on minimum number of 1 to be start with, b

[algogeeks] Re: How to Solve This

2011-10-11 Thread vickywiz
Does "multiple 1" means that number with 3 in units place has all 1's or there can be other digits in the multiple of number like 34111232?... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit

[algogeeks] Re: How to Solve This

2011-10-11 Thread Dave
@Prasad: The number with 22 1s, 1,111,111,111,111,111,111,111, is divisible by 23. The quotient is 48,309,178,743,961,352,657. Dave On Oct 11, 5:00 pm, prasad jondhale wrote: > 23 has 3 in its unit place but it is not multiple of 111 or 11 or . > will u pls elaborate on the problem statement

[algogeeks] Re: How to solve this algorithm graph problem in polynomial time?

2011-09-27 Thread Alexandru Patranescu
I meant *Txy < Txz + Tzy* -- 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/-/HgHVuO5qNj8J. To post to this group, send email to algogeeks@googlegroups.com. To

[algogeeks] Re: How to solve this algorithm graph problem in polynomial time?

2011-09-27 Thread Alexandru Patranescu
one more detail: *Txy* is optimal distance so that *Txy > Txz + Tzy*, for any x, y and z between 1 and N. -- 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/-/A

[algogeeks] Re: How to solve this algorithm graph problem in polynomial time?

2011-09-26 Thread yamini gupta
i think steiner tree can be used On Sep 26, 10:05 pm, drealecs wrote: > I have a software problem and I'm searching for a solution but tried > different algorithm approach and nothing came out. > I'm not very familiar with all the graph algorithms and I hope there > is already a way to solve this

[algogeeks] Re: How to solve this problem

2011-08-15 Thread Dave
@Ankur: The least significant digit of a[i], base n, is a[i]%n. The middle digit is (a[i]/n)%n, and the most signficant digit is a[i]/ (n*n). So the code looks something like int b[n], c[n], i, j; for( i = 0 ; i < n ; ++i ) // sort by least significant digit c[i] = 0; for( i = 0 ; i < n ; ++i

Re: [algogeeks] Re: How to solve this problem

2011-08-15 Thread *$*
lets assume numbers are in range 0 - 4 ,and array is aarr . then range would be 0- 4^3 .. (0 - 64).. now allocate an arraay .. int *x = calloc(n^3,sizeof(int)) // can use even bits aalso .. but for simplicity of algo , using array for(int i=0;i<4;i++) { x[arr[i]] = 1; } for(int i=0;i<64;i++) { if(

Re: [algogeeks] Re: How to solve this problem

2011-08-15 Thread Ankur Garg
@Dave Dude can u provide a sample code...What do u mean by radix n ..also radix sort requires some other sorting algo to sort digits Regards Ankur On Sun, Aug 14, 2011 at 1:33 PM, Dave wrote: > @Ankur: Use a radix sort with radix n. It will take 3 passes to sort > the 3 base-n digits, each of

Re: [algogeeks] Re: How to solve this problem

2011-08-14 Thread Kunal Patil
Yes..i agree with Dave..Here is what i think. As you have integers upto n^3 in your input, it would need [3*lg(n) + 1] bits to represent each integer. So take each group of r = ceil(lg(n)) bits at a time. So this becomes number of bits needed to represent single digit. Each digit thus can take 2^r

[algogeeks] Re: How to solve this problem

2011-08-14 Thread Dave
@Gopi: Explain how a counting sort can be done without zeroing out an array of size n^3, and then scanning it, or explain how to do these operations in O(n). Dave On Aug 14, 10:52 am, "*$*" wrote: > if extra space is allowed .. can use counting sort > > > > > > On Sun, Aug 14, 2011 at 8:38 PM, A

[algogeeks] Re: How to solve this problem

2011-08-14 Thread Dave
@Ankur: Use a radix sort with radix n. It will take 3 passes to sort the 3 base-n digits, each of O(n), so the overall order will be O(n). On Aug 14, 10:08 am, Ankur Garg wrote: > This is one question from Coreman > > 3rd Edition - > > 8-3-4 --  Sort n integers in the range 0 to n^3 -1 in O(n) ti

[algogeeks] Re: How to solve this problem efficiently?

2007-10-07 Thread Sticker
I guess it is binary search tree. Try this and you will get what you want. On Sep 26, 5:12 am, "mukesh agrawal" <[EMAIL PROTECTED]> wrote: > What is binary index tree ? I googled it finding irrelevent information ... > help needed .. > > On 9/25/07, Mohammad Naser Zandy <[EMAIL PROTECTED]> wrote:

[algogeeks] Re: How to solve this problem efficiently?

2007-09-28 Thread mukesh agrawal
What is binary index tree ? I googled it finding irrelevent information ... help needed .. On 9/25/07, Mohammad Naser Zandy <[EMAIL PROTECTED]> wrote: > > I am agree with Sticker, > I comes to write exactly what Sticker wrote. ;) > It's O(N^2 / 2) that is 1+2+3+4+5+...+N. > > On 9/25/07, Sticker <

[algogeeks] Re: How to solve this problem efficiently?

2007-09-27 Thread vivek garg
To store N we can make a binary tree with extra data store is the no of left nodes in tree. now search cost is O(logN) and O(1) is the cost of finding no less than that particular no. also , we can update tree in O(logN) tIme. On Sep 25, 6:16 am, Sticker <[EMAIL PROTECTED]> wrote: > I saw your id

[algogeeks] Re: How to solve this problem efficiently?

2007-09-24 Thread Mohammad Naser Zandy
I am agree with Sticker, I comes to write exactly what Sticker wrote. ;) It's O(N^2 / 2) that is 1+2+3+4+5+...+N. On 9/25/07, Sticker <[EMAIL PROTECTED]> wrote: > > > I saw your ideas. Some of them are correct some are not. Here is what > I am thinking. > > >From the question we know that 1 ≤ M ≤

[algogeeks] Re: How to solve this problem efficiently?

2007-09-24 Thread Sticker
I saw your ideas. Some of them are correct some are not. Here is what I am thinking. >From the question we know that 1 ≤ M ≤ 100 and 1 ≤ N ≤ 4000. So notice that M >> N. Using a linked list to store M, you have to travel it from either end, so at least M/2 travels each time, still larger than

[algogeeks] Re: How to solve this problem efficiently?

2007-09-22 Thread Jun
I already know how to solve it. Binary Index Tree is good approach to solve this problem. Thanks very body involved in this discussion! On Sep 22, 6:31 am, KK <[EMAIL PROTECTED]> wrote: > On Sep 5, 11:07 am, jliang <[EMAIL PROTECTED]> wrote: > > > how about a doubled linked list where you can re

[algogeeks] Re: How to solve this problem efficiently?

2007-09-21 Thread KK
On Sep 5, 11:07 am, jliang <[EMAIL PROTECTED]> wrote: > how about a doubled linked list where you can remove item at any > index. the removing is O(1). you can also keep track of the current removing from a doubled linked list is O(1)? How? > size S so if you are borrowing book at index greate

[algogeeks] Re: How to solve this problem efficiently?

2007-09-07 Thread MD
I can think of an o(n lg n) implementation that uses linked lists. Maintain LL of original book array: 26-> 1-> 42-> 15 ->3 this shrinks as books are removed. maintan LL of borrowed books: 3->4 .. Original LL now becomes 26->1->15 Sort the borrowed LL --(borrwored order may be 3->4->1 == 1->3->4)

[algogeeks] Re: How to solve this problem efficiently?

2007-09-05 Thread adak
Of course, the index numbers lower than the book being checked out, don't need to be changed, just the higher numbers. I like using an array of structs with structure members which can group all the relevant data together that I want for that book, or student, etc. So Books[] might have: title,

[algogeeks] Re: How to solve this problem efficiently?

2007-09-05 Thread jliang
how about a doubled linked list where you can remove item at any index. the removing is O(1). you can also keep track of the current size S so if you are borrowing book at index greater than S/2, you traverse the list from the end, if index < S/2, you traverse from the beginning. every time a boo

[algogeeks] Re: How to solve this problem efficiently?

2007-09-04 Thread Ray
I know the naive method. It's very straight. Just maintain an index array which records the index of the books. whenever one book is removed then update all elements in the index array after its index. It runs O (M N). I'd like to know is there any efficent data structure to speedup it? Thanks.

[algogeeks] Re: how to solve this problem about minimal result?

2005-11-28 Thread pramod
Nevermind. I found the solution. Thanks anyway. I think the problem is called "post office location problem" instead of "post office problem" which is quite complex.

[algogeeks] Re: how to solve this problem about minimal result?

2005-11-27 Thread pramod
Hi Arunachalam, Can you please explain that algorithm on how to find the weighted median? and what is the proof that weighted median is the answer?

[algogeeks] Re: how to solve this problem about minimal result?

2005-11-27 Thread Arunachalam
Search the net for the post office problem.   The answer is find the weighted median.  On 11/22/05, fangvv <[EMAIL PROTECTED]> wrote: Given n point coordinate value {x1,y1}.{xn,yn} andweight w1.wn, How to find point P(X,Y) meet : X >= min{x1,x2,xn} , X <= max{x1, x2,.xn}Y >= min{y1,