Re: [algogeeks] Re: how to solve this?
@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 make the equation
with a degree of 0..
Now, say if root is 't' and 'delta1' and 'delta2' being positive values, we
know f(t - delta1) * f (t - delta2) < 0.
Why ?
f (t) = 0
All f (t - delta1) will share a common sign (either positive or negative).
Same for all f (t - delta2), however the sign here will be reverse. It
depends upon m (slope) but the product of both is guaranteed to be negative.
The graph will be strictly increasing or decreasing. This provides an
ideal use case for *binary search. *
*
*
We take two extreme values assuming root should lie between them, and do a
binary search over it.
To do that, first of all we bring both side of expression to one side.
This is not hard even programmatically, can be done in one line of code.
In [1]: s = "2*x+5-(4*x-7+(4-2))=10*x-9"
In [2]: s.split ('=')[0] + "-1*(" + s.split ('=')[-1] + ")"
Out[2]: '2*x+5-(4*x-7+(4-2))-1*(10*x-9)'
Now, we do a binary search over the expression.
Below is the python code and codepad link [1] since some mail client don't
like indentations.
#!/usr/bin/env python
#-*- coding: utf-8 -*-
def bsearch (exp, lo, hi):
EPS = 0.01
ret = lo + (hi - lo) / 2
while (lo < hi):
mid = lo + (hi - lo) / 2.0
val_mid = eval (exp.replace ('x', str (mid)))
val_lo = eval (exp.replace ('x', str (lo)))
val_hi = eval (exp.replace ('x', str (hi)))
if (val_mid == 0):
return mid
elif (val_lo * val_mid < 0): // Root lies in between lo and mid.
ret = mid
hi = mid - EPS
else:// Root lies in between mid
and hi.
ret = mid
lo = mid + EPS
return ret
s = "2*x+5-(4*x-7+(4-2))-10*x+9"
print bsearch (s, -100, 100)
The output,
% python solve.py
1.5886935
Just like Newton bisection method used to calculate roots, we can use
Epsilon to take care of the fact that root does not vary by Epsilon. The
caveat here however is if we want the answer in the form of
numerator/denominator as in "19/12", it is tough (unless of course we use
fraction module and try some clever optimization, none of which strikes me
so far).
[1] http://codepad.org/85HJj0Eg
On Fri, Apr 5, 2013 at 2:51 AM, Don wrote:
> 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 one. Another way is to call the expression on
> > the left side of the equation f(x) and the expression on the right side
> of
> > the equation g(x), and calculate f(0), g(0), f(1), and g(1). Then
> >
> > x = (f(0) -g(0)) / (f(0) - g(0) - f(1) + g(1))
> >
> > In the original poster's example, f(0) = 10, f(1) = 8, g(0) = -9, and
> g(1)
> > = 1, so x = 19/12. Presuming that you want the exact answer, leave it in
> > fractional form, and if the denominator is negative, then negate both
> > numerator and denominator. Then divide both numerator and denominator by
> > their gcd. Finally, if the denominator is 1, report the numerator as the
> > answer; otherwise report the fraction numerator/denominator as the
> answer.
> >
> > Dave
> >
> >
> >
> >
> >
> >
> >
> > On Thursday, April 4, 2013 11:43:20 AM UTC-5, Don wrote:
> > > 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:
> > > > Given an expression in the form of a string, solve for x. The highest
> > > power
> > > > of x in the expression will be equal to 1. Operators allowed are +, *
> > > and
> > > > -. These are all binary operators. So, 2x would be written as 2*x.
> Every
> > > > operator will be followed by a single term or a constant.
> >
> > > > For example, consider the following equation:
> >
> > > > 2*x+5-(4*x-7+(4-2))=10*x-9 Given such an equation, we need to find a
> > > > solution to x
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails f
[algogeeks] Re: how to solve this?
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 one. Another way is to call the expression on > the left side of the equation f(x) and the expression on the right side of > the equation g(x), and calculate f(0), g(0), f(1), and g(1). Then > > x = (f(0) -g(0)) / (f(0) - g(0) - f(1) + g(1)) > > In the original poster's example, f(0) = 10, f(1) = 8, g(0) = -9, and g(1) > = 1, so x = 19/12. Presuming that you want the exact answer, leave it in > fractional form, and if the denominator is negative, then negate both > numerator and denominator. Then divide both numerator and denominator by > their gcd. Finally, if the denominator is 1, report the numerator as the > answer; otherwise report the fraction numerator/denominator as the answer. > > Dave > > > > > > > > On Thursday, April 4, 2013 11:43:20 AM UTC-5, Don wrote: > > 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: > > > Given an expression in the form of a string, solve for x. The highest > > power > > > of x in the expression will be equal to 1. Operators allowed are +, * > > and > > > -. These are all binary operators. So, 2x would be written as 2*x. Every > > > operator will be followed by a single term or a constant. > > > > For example, consider the following equation: > > > > 2*x+5-(4*x-7+(4-2))=10*x-9 Given such an equation, we need to find a > > > solution to x -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: how to solve this?
@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 expression on the right side of the equation g(x), and calculate f(0), g(0), f(1), and g(1). Then x = (f(0) -g(0)) / (f(0) - g(0) - f(1) + g(1)) In the original poster's example, f(0) = 10, f(1) = 8, g(0) = -9, and g(1) = 1, so x = 19/12. Presuming that you want the exact answer, leave it in fractional form, and if the denominator is negative, then negate both numerator and denominator. Then divide both numerator and denominator by their gcd. Finally, if the denominator is 1, report the numerator as the answer; otherwise report the fraction numerator/denominator as the answer. Dave On Thursday, April 4, 2013 11:43:20 AM UTC-5, Don wrote: > 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: > > Given an expression in the form of a string, solve for x. The highest > power > > of x in the expression will be equal to 1. Operators allowed are +, * > and > > -. These are all binary operators. So, 2x would be written as 2*x. Every > > operator will be followed by a single term or a constant. > > > > For example, consider the following equation: > > > > 2*x+5-(4*x-7+(4-2))=10*x-9 Given such an equation, we need to find a > > solution to x > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: how to solve this?
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: > Given an expression in the form of a string, solve for x. The highest power > of x in the expression will be equal to 1. Operators allowed are +, * and > -. These are all binary operators. So, 2x would be written as 2*x. Every > operator will be followed by a single term or a constant. > > For example, consider the following equation: > > 2*x+5-(4*x-7+(4-2))=10*x-9 Given such an equation, we need to find a > solution to x -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: How to solve this
@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 each p(i) = c for some nonzero constant c. This is a contradiction. Dave On Dec 24, 2:20 am, Ankur Garg wrote: > 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 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 traverse two nodes at a time: > > 1. one pointing to first node (lets call it odd pointer) > > 2. other pointing to second node (lets call it even pointer) > > > So, depending on the value returned by random number generator(even or > > odd), we can decide which pointer to pick. > > > -- > > 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/-/N-5i9YH4AkYJ. > > > 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?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 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?hl=en.
Re: [algogeeks] Re: How to solve this
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 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 traverse two nodes at a time: > 1. one pointing to first node (lets call it odd pointer) > 2. other pointing to second node (lets call it even pointer) > > So, depending on the value returned by random number generator(even or > odd), we can decide which pointer to pick. > > -- > 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/-/N-5i9YH4AkYJ. > > 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?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 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?hl=en.
Re: [algogeeks] Re: How to solve this
@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 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 traverse two nodes at a time: > 1. one pointing to first node (lets call it odd pointer) > 2. other pointing to second node (lets call it even pointer) > > So, depending on the value returned by random number generator(even or > odd), we can decide which pointer to pick. > > -- > 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/-/N-5i9YH4AkYJ. > > 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?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 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?hl=en.
[algogeeks] Re: How to solve this
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 traverse two nodes at a time: 1. one pointing to first node (lets call it odd pointer) 2. other pointing to second node (lets call it even pointer) So, depending on the value returned by random number generator(even or odd), we can decide which pointer to pick. -- 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/-/N-5i9YH4AkYJ. 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?hl=en.
[algogeeks] Re: How to solve this
@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 the n-th node of the list, where n = int(- log(random())), where random() generates uniform (0,1) random numbers. I presume that there are many more ways to do this. Dave On Dec 23, 1:54 pm, Ankur Garg wrote: > Suggest an algo with which u can find a random node in an infinitely long > linked list -- 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?hl=en.
Re: [algogeeks] Re: How to Solve This
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 co-prime. So using Fermat's Little Theorem we can calculate
m = euler_totient_function(p)
However you can only get a valid solution, but if we want the smalled such
possible 'm', then we have to use Carmichael Function, which will give you
the lowest such possible 'm'.
http://math-it.org/Mathematik/Zahlentheorie/Carmichael.html
On Thu, Oct 13, 2011 at 6:26 PM, Gene wrote:
> 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 number )
>
> An unverified one because my machine ran out of memory while
> multiplying (but which took about .05 seconds to find) is:
>
> 1,638,726 1's = 9,876,543 times (a 1,638,719 digit number )
>
> On Oct 12, 4:35 pm, Gene wrote:
> > 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
> >
> > Now you need to add ...50 to make the 10's digit a 1. So
> >
> > 50 * 123 = 6150 + 861 = 7011
> >
> > And now add 100 to get the third 1...
> > 700 * 123 = 86,100 + 7011 = 93,111
> >
> > Following this pattern:
> > 6000 * 123 = 738,000 + 93,111 = 831,111
> > 6 * 123 = 7,380,000 + 831,111 = 8,211,111
> > 30 * 123 = 36,900,000 + 8,211,111 = 45,111,111
> >
> > Okay. That's enough. We stop when the carry digits finally turn out
> > to be all 1's.
> >
> > In a program once we've arranged for a rightmost 1 we can shift it out
> > of the calculation by dividing everything by 10. At the same time we
> > can shift out the trailing zeros in the multiplicands.
> >
> > So here's a quick implementation. Sorry in advance for mistakes, but
> > it seems to be working okay:
> >
> > #include
> >
> > // If x is all 1's (including zero of them), return
> > // how many there are. Otherwise return ~0u.
> > unsigned all_ones(unsigned x)
> > {
> > unsigned n = 0;
> > while (x) {
> > if (x % 10 != 1)
> > return ~0u;
> > x /= 10;
> > ++n;
> > }
> > return n;
> >
> > }
> >
> > // A table s.t. (x + 3 * mul[x % 10]) ends in 1.
> > unsigned mul[] = {7,0,3,6,9,2,5,8,1,4};
> >
> > // Return n s.t. x divides sum_{i=0 to n-1} 10^i .
> > // x must be congruent to 3 mod 10.
> > unsigned ones(unsigned x)
> > {
> > unsigned n, carry = x;
> > for (n = 0; all_ones(carry) == ~0u; n++) {
> > carry = (carry + mul[carry % 10] * x) / 10;
> > // printf("%d\n", carry);
> > }
> > return n + all_ones(carry);
> >
> > }
> >
> > int main(void)
> > {
> > unsigned x;
> > if (scanf("%u", &x) == 1 && x % 10 == 3)
> > printf("%u divides %u 1's\n", x, ones(x));
> > return 0;
> >
> > }
> >
> > On Oct 10, 9:20 am, VIHARRI wrote:
> >
> >
> >
> >
> >
> >
> >
> > > For every number that has 3 in its units place has one multiple which
> > > has all one's i.e. 111 is
> > > such multiple and 13 has a multiple 11. Write a program to find
> > > such multiple for any
> > > number that has 3 at its units place.
>
> --
> 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?hl=en.
>
>
--
B.Prabhat Kiran
CS08B014
4th Year UnderGrad
Comp Sci & Engg
IIT-Madras
--
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?hl=en.
[algogeeks] Re: How to Solve This
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 number )
An unverified one because my machine ran out of memory while
multiplying (but which took about .05 seconds to find) is:
1,638,726 1's = 9,876,543 times (a 1,638,719 digit number )
On Oct 12, 4:35 pm, Gene wrote:
> 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
>
> Now you need to add ...50 to make the 10's digit a 1. So
>
> 50 * 123 = 6150 + 861 = 7011
>
> And now add 100 to get the third 1...
> 700 * 123 = 86,100 + 7011 = 93,111
>
> Following this pattern:
> 6000 * 123 = 738,000 + 93,111 = 831,111
> 6 * 123 = 7,380,000 + 831,111 = 8,211,111
> 30 * 123 = 36,900,000 + 8,211,111 = 45,111,111
>
> Okay. That's enough. We stop when the carry digits finally turn out
> to be all 1's.
>
> In a program once we've arranged for a rightmost 1 we can shift it out
> of the calculation by dividing everything by 10. At the same time we
> can shift out the trailing zeros in the multiplicands.
>
> So here's a quick implementation. Sorry in advance for mistakes, but
> it seems to be working okay:
>
> #include
>
> // If x is all 1's (including zero of them), return
> // how many there are. Otherwise return ~0u.
> unsigned all_ones(unsigned x)
> {
> unsigned n = 0;
> while (x) {
> if (x % 10 != 1)
> return ~0u;
> x /= 10;
> ++n;
> }
> return n;
>
> }
>
> // A table s.t. (x + 3 * mul[x % 10]) ends in 1.
> unsigned mul[] = {7,0,3,6,9,2,5,8,1,4};
>
> // Return n s.t. x divides sum_{i=0 to n-1} 10^i .
> // x must be congruent to 3 mod 10.
> unsigned ones(unsigned x)
> {
> unsigned n, carry = x;
> for (n = 0; all_ones(carry) == ~0u; n++) {
> carry = (carry + mul[carry % 10] * x) / 10;
> // printf("%d\n", carry);
> }
> return n + all_ones(carry);
>
> }
>
> int main(void)
> {
> unsigned x;
> if (scanf("%u", &x) == 1 && x % 10 == 3)
> printf("%u divides %u 1's\n", x, ones(x));
> return 0;
>
> }
>
> On Oct 10, 9:20 am, VIHARRI wrote:
>
>
>
>
>
>
>
> > For every number that has 3 in its units place has one multiple which
> > has all one's i.e. 111 is
> > such multiple and 13 has a multiple 11. Write a program to find
> > such multiple for any
> > number that has 3 at its units place.
--
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?hl=en.
[algogeeks] Re: How to Solve This
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
Now you need to add ...50 to make the 10's digit a 1. So
50 * 123 = 6150 + 861 = 7011
And now add 100 to get the third 1...
700 * 123 = 86,100 + 7011 = 93,111
Following this pattern:
6000 * 123 = 738,000 + 93,111 = 831,111
6 * 123 = 7,380,000 + 831,111 = 8,211,111
30 * 123 = 36,900,000 + 8,211,111 = 45,111,111
Okay. That's enough. We stop when the carry digits finally turn out
to be all 1's.
In a program once we've arranged for a rightmost 1 we can shift it out
of the calculation by dividing everything by 10. At the same time we
can shift out the trailing zeros in the multiplicands.
So here's a quick implementation. Sorry in advance for mistakes, but
it seems to be working okay:
#include
// If x is all 1's (including zero of them), return
// how many there are. Otherwise return ~0u.
unsigned all_ones(unsigned x)
{
unsigned n = 0;
while (x) {
if (x % 10 != 1)
return ~0u;
x /= 10;
++n;
}
return n;
}
// A table s.t. (x + 3 * mul[x % 10]) ends in 1.
unsigned mul[] = {7,0,3,6,9,2,5,8,1,4};
// Return n s.t. x divides sum_{i=0 to n-1} 10^i .
// x must be congruent to 3 mod 10.
unsigned ones(unsigned x)
{
unsigned n, carry = x;
for (n = 0; all_ones(carry) == ~0u; n++) {
carry = (carry + mul[carry % 10] * x) / 10;
// printf("%d\n", carry);
}
return n + all_ones(carry);
}
int main(void)
{
unsigned x;
if (scanf("%u", &x) == 1 && x % 10 == 3)
printf("%u divides %u 1's\n", x, ones(x));
return 0;
}
On Oct 10, 9:20 am, VIHARRI wrote:
> For every number that has 3 in its units place has one multiple which
> has all one's i.e. 111 is
> such multiple and 13 has a multiple 11. Write a program to find
> such multiple for any
> number that has 3 at its units place.
--
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?hl=en.
[algogeeks] Re: How to Solve This
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, but
seeing the logarithmic eq, this simply seems not to add much value.
can any one figure out for upper bound ?
On Oct 12, 5:18 pm, anshu mishra wrote:
> @amol
> I was not sure that for every number that has 3 in its unit place has one
> multiple which has all one. So I used that is if the remainder is coming
> that already appeared stop there coz it will make stuck in a loop.
> for ex. remainders are
> 1 3 19 23 37 1 3 19 that will repeat.
>
> but it in this case u can remove the set. Code will look more simpler.
>
> string all1Multiple(int x)
> {
> string s;
> int r=1;
> do
> {
> s += '1';
> r = r % x;
> r = r * 10 + 1;
>
> } while(r != 1);
> return s;
> }
--
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?hl=en.
[algogeeks] Re: How to Solve This
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 https://groups.google.com/d/msg/algogeeks/-/rX0kwjCzOoQJ. 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?hl=en.
[algogeeks] Re: How to Solve This
@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?
>
> On Mon, Oct 10, 2011 at 2:17 PM, anshu mishra
> wrote:
>
>
>
>
>
> > string all1Multiple(int x)
> > {
> > string s;
> > set mySet;
> > mySet.push(0);
> > int psize, r=1;
> > do
> > {
> > psize = mySet.size();
> > s += '1';
> > r = r % x;
> > mySet.push(r);
> > r = r * 10 + 1;
> > } while(mySet.size() > psize);
>
> > if (r != 1) return "not Possible";
> > return s;
>
> > }
>
> > --
> > 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?hl=en.
>
> --
>
> Thanks & Regards
> Prasad Y.Jondhale
> M.Tech(software engg.),
> Delhi College Of Engineering,
> Main Bawana road,Delhi-110042
> Ph-09540208001
--
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?hl=en.
[algogeeks] Re: How to solve this algorithm graph problem in polynomial time?
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 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.
[algogeeks] Re: How to solve this algorithm graph problem in polynomial time?
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/-/Aj5bWWD59swJ. 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?hl=en.
[algogeeks] Re: How to solve this algorithm graph problem in polynomial time?
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 kind of problems in polynomial time. > > I need the algorithm for different task but I illustrated simple like > this: > > The are N cities and there is a wanderer. > The time it takes for him to go from a town to another town is known - > Txy (from town x to town y). > From any town he can go to another town so it is a complete graph. > In each town there is a an amount of money Mx the wanderer wants to > collect. > It isn't enough time to pass through all cities. > Having the total available time T and the starting point i, the > problem is to find the best route so that the money he collects will > be maximum. > > Input numbers range: > N is between 400 and 600 > Mx(M1, M2, ...) are between 50 and 500, x between 1 and N > Txy are between 1 and 200, x and y are between 1 and N, x!=y > T is between 1000 and 5000 > > The problems is shared > here:http://www.evernote.com/shard/s119/sh/79f47a65-c1e6-44da-bbc0-7d10e36... > > Thanks -- 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?hl=en.
[algogeeks] Re: How to solve this problem
@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 ) c[a[i]%n]++; c[n-1] = n - c[n-1]; for( i = n-2 ; i >= 0 ; --i ) c[i] = c[i+1] - c[i]; for ( i = 0 ; i < 0 ; ++i ) b[c[a[i]%n]++] = a[i]; for( i = 0 ; i < n ; ++i ) // sort by middle digit c[i] = 0; for( i = 0 ; i < n ; ++i ) c[(b[i]/n)%n]++; c[n-1] = n - c[n-1]; for( i = n-2 ; i >= 0 ; --i ) c[i] = c[i+1] - c[i]; for ( i = 0 ; i < 0 ; ++i ) a[c[(b[i]/n)%n]++] = b[i]; for( i = 0 ; i < n ; ++i ) // sort by most significant digit c[i] = 0; for( i = 0 ; i < n ; ++i ) c[a[i]/(n*n)]++; c[n-1] = n - c[n-1]; for( i = n-2 ; i >= 0 ; --i ) c[i] = c[i+1] - c[i]; for ( i = 0 ; i < 0 ; ++i ) b[c[a[i]/(n*n)]++] = a[i]; // sorted result is in b[]. Dave On Aug 15, 4:48 pm, Ankur Garg wrote: > @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 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) time > > > > Any ideas how to do this in O(n) > > > -- > > 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?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 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?hl=en.
Re: [algogeeks] Re: How to solve this problem
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(arr[i]!=0)
{
x[i]=arr[i];
}
}
// it can be optimized by using bits ..
please correct me if i am wrong in understaanding the qquestion of any
issues in algo .
On Tue, Aug 16, 2011 at 3:18 AM, Ankur Garg wrote:
> @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 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) time
>> >
>> > Any ideas how to do this in O(n)
>>
>> --
>> 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?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 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?hl=en.
>
--
Thx,
--Gopi
--
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?hl=en.
Re: [algogeeks] Re: How to solve this problem
@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 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) time > > > > Any ideas how to do this in O(n) > > -- > 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?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 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?hl=en.
Re: [algogeeks] Re: How to solve this problem
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 values. If you use counting sort to sort digits, it will take O(n+ 2^r ) time. You have 3 such groups. So 3 passes needed to sort whole input set. Overall complexity is 3*O(n+2^r) Correct me if i am wrong anywhere in the analysis. -- 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?hl=en.
[algogeeks] Re: How to solve this problem
@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, 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) time > > > Any ideas how to do this in O(n) > > > -- > > 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?hl=en. > > -- > Thx, > --Gopi -- 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?hl=en.
[algogeeks] Re: How to solve this problem
@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) time > > Any ideas how to do this in O(n) -- 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?hl=en.
[algogeeks] Re: How to solve this problem efficiently?
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: > > > > > > > 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 ≤ 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 N. So what if we keep M stored in an array(a simplest array > > > int[], called booArray) and do touch it. Rather we dynamically store > > > N? I use a linked list borLList to store all the borrowed books' > > > "original" position in booArray. > > > > Once we come across a borrowed index, we go through borLList, each > > > time a position smaller than the borrowed index, we increase the > > > borrowed index by one until we come across a position has a position > > > larger than it, then we insert this borrowed index to the current > > > position. Do another one and so on. > > > > Example: > > > 5 > > > 26 1 42 15 3 > > > 2 > > > 3 > > > 4 > > > > The booArray is 26, 1, 42, 15, 3, stored in booArray[1] to > > > booArray[5]. borLList is empty now. 3 is the first borrowed index, we > > > insert it into borLList and return booArray[3]. The next borrowed > > > index is 4, since the first element in borLList is 3, which is smaller > > > than 4, we increase this borrowed index by one, now it is 5, since no > > > larger element exists in borLList, we insert 5 into borLList and > > > return booArray[5]. Now the borLList is 3->5. > > > > As we can see, practically far less than 4000 times is required for > > > each borrowed index, which is definitely better than the double link > > > list solution (which is (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 as > > > given by jliang. > > > > I definitely do not agree the method to reorder the borrowed indexes. > > > This will give wrong answer. The order is important for this problem. > > > > I do not know how to use binary search tree to solve this problem, it > > > will be great if solution can be described here. > > > > On Sep 23, 12:17 pm, Jun <[EMAIL PROTECTED]> wrote: > > > > 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 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 greater than S/2, you > > > > > > traverse the list from the end, if index < S/2, you traverse from > > > the > > > > > > beginning. > > > > > > > every time a book is removed, S becomes 1 smaller, so the > > > traversal > > > > > > time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 > > > > > > > you can also put them in a binary tree, so every operation is > > > O(lgN) > > > > > > putting the original array in binary tree takes O(M lgM) time, and > > > you > > > > > will lose the original indices. So it's of no use. > > > > > > > so the total will be O(lgN M) > > > > > > I dont think so. correct me if I am wrong. > > -- > Mukesh Agrawal > Final Year UG CSE > IIT KGP --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to solve this problem efficiently?
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 <[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 ≤ 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 N. So what if we keep M stored in an array(a simplest array > > int[], called booArray) and do touch it. Rather we dynamically store > > N? I use a linked list borLList to store all the borrowed books' > > "original" position in booArray. > > > > Once we come across a borrowed index, we go through borLList, each > > time a position smaller than the borrowed index, we increase the > > borrowed index by one until we come across a position has a position > > larger than it, then we insert this borrowed index to the current > > position. Do another one and so on. > > > > Example: > > 5 > > 26 1 42 15 3 > > 2 > > 3 > > 4 > > > > The booArray is 26, 1, 42, 15, 3, stored in booArray[1] to > > booArray[5]. borLList is empty now. 3 is the first borrowed index, we > > insert it into borLList and return booArray[3]. The next borrowed > > index is 4, since the first element in borLList is 3, which is smaller > > than 4, we increase this borrowed index by one, now it is 5, since no > > larger element exists in borLList, we insert 5 into borLList and > > return booArray[5]. Now the borLList is 3->5. > > > > As we can see, practically far less than 4000 times is required for > > each borrowed index, which is definitely better than the double link > > list solution (which is (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 as > > given by jliang. > > > > I definitely do not agree the method to reorder the borrowed indexes. > > This will give wrong answer. The order is important for this problem. > > > > I do not know how to use binary search tree to solve this problem, it > > will be great if solution can be described here. > > > > > > On Sep 23, 12:17 pm, Jun <[EMAIL PROTECTED]> wrote: > > > 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 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 greater than S/2, you > > > > > traverse the list from the end, if index < S/2, you traverse from > > the > > > > > beginning. > > > > > > > > every time a book is removed, S becomes 1 smaller, so the > > traversal > > > > > time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 > > > > > > > > you can also put them in a binary tree, so every operation is > > O(lgN) > > > > > > > putting the original array in binary tree takes O(M lgM) time, and > > you > > > > will lose the original indices. So it's of no use. > > > > > > > > so the total will be O(lgN M) > > > > > > > I dont think so. correct me if I am wrong. > > > > > > > > > > > > > > -- Mukesh Agrawal Final Year UG CSE IIT KGP --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to solve this problem efficiently?
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 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 N. So what if we keep M stored in an array(a simplest array > int[], called booArray) and do touch it. Rather we dynamically store > N? I use a linked list borLList to store all the borrowed books' > "original" position in booArray. > > Once we come across a borrowed index, we go through borLList, each > time a position smaller than the borrowed index, we increase the > borrowed index by one until we come across a position has a position > larger than it, then we insert this borrowed index to the current > position. Do another one and so on. > > Example: > 5 > 26 1 42 15 3 > 2 > 3 > 4 > > The booArray is 26, 1, 42, 15, 3, stored in booArray[1] to > booArray[5]. borLList is empty now. 3 is the first borrowed index, we > insert it into borLList and return booArray[3]. The next borrowed > index is 4, since the first element in borLList is 3, which is smaller > than 4, we increase this borrowed index by one, now it is 5, since no > larger element exists in borLList, we insert 5 into borLList and > return booArray[5]. Now the borLList is 3->5. > > As we can see, practically far less than 4000 times is required for > each borrowed index, which is definitely better than the double link > list solution (which is (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 as > given by jliang. > > I definitely do not agree the method to reorder the borrowed indexes. > This will give wrong answer. The order is important for this problem. > > I do not know how to use binary search tree to solve this problem, it > will be great if solution can be described here. > > On Sep 23, 12:17 pm, Jun <[EMAIL PROTECTED]> wrote: > > > 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 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 greater than S/2, you > > > > traverse the list from the end, if index < S/2, you traverse from the > > > > beginning. > > > > > every time a book is removed, S becomes 1 smaller, so the traversal > > > > time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 > > > > > you can also put them in a binary tree, so every operation is O(lgN) > > > > putting the original array in binary tree takes O(M lgM) time, and you > > > will lose the original indices. So it's of no use. > > > > > so the total will be O(lgN M) > > > > I dont think so. correct me if I am wrong. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to solve this problem efficiently?
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 ≤ 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 N. So what if we keep M stored in an array(a simplest array > int[], called booArray) and do touch it. Rather we dynamically store > N? I use a linked list borLList to store all the borrowed books' > "original" position in booArray. > > Once we come across a borrowed index, we go through borLList, each > time a position smaller than the borrowed index, we increase the > borrowed index by one until we come across a position has a position > larger than it, then we insert this borrowed index to the current > position. Do another one and so on. > > Example: > 5 > 26 1 42 15 3 > 2 > 3 > 4 > > The booArray is 26, 1, 42, 15, 3, stored in booArray[1] to > booArray[5]. borLList is empty now. 3 is the first borrowed index, we > insert it into borLList and return booArray[3]. The next borrowed > index is 4, since the first element in borLList is 3, which is smaller > than 4, we increase this borrowed index by one, now it is 5, since no > larger element exists in borLList, we insert 5 into borLList and > return booArray[5]. Now the borLList is 3->5. > > As we can see, practically far less than 4000 times is required for > each borrowed index, which is definitely better than the double link > list solution (which is (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 as > given by jliang. > > I definitely do not agree the method to reorder the borrowed indexes. > This will give wrong answer. The order is important for this problem. > > I do not know how to use binary search tree to solve this problem, it > will be great if solution can be described here. > > > On Sep 23, 12:17 pm, Jun <[EMAIL PROTECTED]> wrote: > > 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 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 greater than S/2, you > > > > traverse the list from the end, if index < S/2, you traverse from > the > > > > beginning. > > > > > > every time a book is removed, S becomes 1 smaller, so the traversal > > > > time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 > > > > > > you can also put them in a binary tree, so every operation is O(lgN) > > > > > putting the original array in binary tree takes O(M lgM) time, and you > > > will lose the original indices. So it's of no use. > > > > > > so the total will be O(lgN M) > > > > > I dont think so. correct me if I am wrong. > > > > > --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to solve this problem efficiently?
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 N. So what if we keep M stored in an array(a simplest array int[], called booArray) and do touch it. Rather we dynamically store N? I use a linked list borLList to store all the borrowed books' "original" position in booArray. Once we come across a borrowed index, we go through borLList, each time a position smaller than the borrowed index, we increase the borrowed index by one until we come across a position has a position larger than it, then we insert this borrowed index to the current position. Do another one and so on. Example: 5 26 1 42 15 3 2 3 4 The booArray is 26, 1, 42, 15, 3, stored in booArray[1] to booArray[5]. borLList is empty now. 3 is the first borrowed index, we insert it into borLList and return booArray[3]. The next borrowed index is 4, since the first element in borLList is 3, which is smaller than 4, we increase this borrowed index by one, now it is 5, since no larger element exists in borLList, we insert 5 into borLList and return booArray[5]. Now the borLList is 3->5. As we can see, practically far less than 4000 times is required for each borrowed index, which is definitely better than the double link list solution (which is (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 as given by jliang. I definitely do not agree the method to reorder the borrowed indexes. This will give wrong answer. The order is important for this problem. I do not know how to use binary search tree to solve this problem, it will be great if solution can be described here. On Sep 23, 12:17 pm, Jun <[EMAIL PROTECTED]> wrote: > 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 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 greater than S/2, you > > > traverse the list from the end, if index < S/2, you traverse from the > > > beginning. > > > > every time a book is removed, S becomes 1 smaller, so the traversal > > > time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 > > > > you can also put them in a binary tree, so every operation is O(lgN) > > > putting the original array in binary tree takes O(M lgM) time, and you > > will lose the original indices. So it's of no use. > > > > so the total will be O(lgN M) > > > I dont think so. correct me if I am wrong. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to solve this problem efficiently?
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 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 greater than S/2, you > > traverse the list from the end, if index < S/2, you traverse from the > > beginning. > > > every time a book is removed, S becomes 1 smaller, so the traversal > > time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 > > > you can also put them in a binary tree, so every operation is O(lgN) > > putting the original array in binary tree takes O(M lgM) time, and you > will lose the original indices. So it's of no use. > > > so the total will be O(lgN M) > > I dont think so. correct me if I am wrong. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to solve this problem efficiently?
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 greater than S/2, you > traverse the list from the end, if index < S/2, you traverse from the > beginning. > > every time a book is removed, S becomes 1 smaller, so the traversal > time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 > > you can also put them in a binary tree, so every operation is O(lgN) putting the original array in binary tree takes O(M lgM) time, and you will lose the original indices. So it's of no use. > so the total will be O(lgN M) I dont think so. correct me if I am wrong. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to solve this problem efficiently?
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) using borrowed LL reconstruct the missing books links in Original LL. (by inserting empty nodes in index positions from borrowed LL) Indranil can fill the gaps and find out which books were borrowed. Only sorting takes o(n lg n) rest are o(n)/o(1) operations. Let me know any comments of above approach. -MD On Sep 5, 8:34 am, adak <[EMAIL PROTECTED]> wrote: > 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, origLocation, (on the bookshelf), > borrower, etc. The original location number shouldn't be needed here, > but in practice, it's too important not to have it duplicated. > Especially while coding it up and testing. > > Linked lists can be substituted for arrays, if memory is a problem, of > course. The other list or array would have the original index number, > as the value in the current bookshelf number's element. > > Since the weak link in this type of organization of the program is so > striking (the index numbers), in practice, it would be preferred to > give each book it's own unique ID number, and forget the "places from > the left", routine. Obviously this is just an exercise with that as a > "monkey wrench", to be worked out, but it's worth keeping in mind for > RL programs. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to solve this problem efficiently?
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, origLocation, (on the bookshelf), borrower, etc. The original location number shouldn't be needed here, but in practice, it's too important not to have it duplicated. Especially while coding it up and testing. Linked lists can be substituted for arrays, if memory is a problem, of course. The other list or array would have the original index number, as the value in the current bookshelf number's element. Since the weak link in this type of organization of the program is so striking (the index numbers), in practice, it would be preferred to give each book it's own unique ID number, and forget the "places from the left", routine. Obviously this is just an exercise with that as a "monkey wrench", to be worked out, but it's worth keeping in mind for RL programs. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to solve this problem efficiently?
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 book is removed, S becomes 1 smaller, so the traversal time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 you can also put them in a binary tree, so every operation is O(lgN) so the total will be O(lgN M) On Sep 5, 2:53 am, Ray <[EMAIL PROTECTED]> wrote: > 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. > > On Sep 5, 10:14 am, Ray <[EMAIL PROTECTED]> wrote: > > > He has lost many books, since many of his friends borrow his books and > > never bother to return them. He does not want to lose any more books > > and has decided to keep a record of all books that he lends to his > > friends. To make the task of borrowing a book a little difficult, he > > has given the following instructions to his friends: when they borrow > > a book, they must record in a register its position from the left > > among the books currently on the shelf. > > > Suppose there are 5 books in the library and they are arranged as > > follows: > > > 26 1 42 15 3 > > If someone walks in and borrows the book 42, then he will record 3 in > > the register because this book is the third from the left on the > > shelf. Now the shelf looks like this: > > > 26 1 15 3 > > If the next person borrow the book 3, he writes down 4 in the register > > since this is currently the fourth book from the left on the shelf, > > and so on. > > > Indraneel knows the initial arrangement of the books in his library at > > the time that he introduced the register system. After a while he > > examines his register and would like to know which books have been > > borrowed. Your task is to write a program to help Indraneel solve this > > problem. > > > Input format > > > The first line of the input contains a single integer M indicating the > > number of books in Indraneel's library. The next line contains M > > distinct positive integers describing the sequence in which the books > > are arranged on the library shelf. The third line of input contains a > > single integer N indicating the number of entries in the register. > > This, in turn, is followed by N lines (lines 4 to N+3), each > > containing one positive integer. The integer on line 3+i indicates the > > position from left of the book ith book borrowed. (You may assume that > > the number on line 3+i is at most M-i+1.) > > > Output format > > > N lines with one positive integer on each line. The number on line i > > is the book borrowed by the ith borrower. > > > Test Data: > > > You may assume that 1 ≤ M ≤ 100 and 1 ≤ N ≤ 4000. > > > Example: > > > Here is the sample input and output corresponding to the example > > discussed above. > > > Sample Input > > > 5 > > 26 1 42 15 3 > > 2 > > 3 > > 4 > > Sample Output > > > 42 > > 3 --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to solve this problem efficiently?
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. On Sep 5, 10:14 am, Ray <[EMAIL PROTECTED]> wrote: > He has lost many books, since many of his friends borrow his books and > never bother to return them. He does not want to lose any more books > and has decided to keep a record of all books that he lends to his > friends. To make the task of borrowing a book a little difficult, he > has given the following instructions to his friends: when they borrow > a book, they must record in a register its position from the left > among the books currently on the shelf. > > Suppose there are 5 books in the library and they are arranged as > follows: > > 26 1 42 15 3 > If someone walks in and borrows the book 42, then he will record 3 in > the register because this book is the third from the left on the > shelf. Now the shelf looks like this: > > 26 1 15 3 > If the next person borrow the book 3, he writes down 4 in the register > since this is currently the fourth book from the left on the shelf, > and so on. > > Indraneel knows the initial arrangement of the books in his library at > the time that he introduced the register system. After a while he > examines his register and would like to know which books have been > borrowed. Your task is to write a program to help Indraneel solve this > problem. > > Input format > > The first line of the input contains a single integer M indicating the > number of books in Indraneel's library. The next line contains M > distinct positive integers describing the sequence in which the books > are arranged on the library shelf. The third line of input contains a > single integer N indicating the number of entries in the register. > This, in turn, is followed by N lines (lines 4 to N+3), each > containing one positive integer. The integer on line 3+i indicates the > position from left of the book ith book borrowed. (You may assume that > the number on line 3+i is at most M-i+1.) > > Output format > > N lines with one positive integer on each line. The number on line i > is the book borrowed by the ith borrower. > > Test Data: > > You may assume that 1 ≤ M ≤ 100 and 1 ≤ N ≤ 4000. > > Example: > > Here is the sample input and output corresponding to the example > discussed above. > > Sample Input > > 5 > 26 1 42 15 3 > 2 > 3 > 4 > Sample Output > > 42 > 3 --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: how to solve this problem about minimal result?
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?
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?
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,y2,yn} , Y <= max{y1, y2,.yn}dis(i, P) = sqrt((yi - Y)*(yi - Y) + (xi - X)*(xi - X))min{ abs[w1*((y1-Y)/dis(1,P) + ... + wn*(yn - Y)/dis(n,P)] +
abs[w1*((x1-X)/dis(1,P) + ... + wn*(xn - X)/dis(n,P)] }-- ===want to know more about mehttp"//ww.livejournal.com/users/arunachalam
