> Your solution really parses terms on what it means to be performing
> asymptotic analysis... you cannot say that this storage is constant in
> 32 bits, when it is not said that you are using 32 bit numbers. If you
> are speaking asymptotically at all, saying that something is O(n) or
> O(log(n)
> so, does 135,000,000 distinct integers work for any size of input?
Always (notice my stipulation of 32 bit). However, regardless of the
size of an integer (in bits) there is _always_ a fixed number of bits
that can represent it in the manner I explained.
> (Nowhere in the original problem did
I personally would agree that there is probably not a solution. If you
really wanted to stick with the constant space -- you are probably
stuck with the O(n^2) algorithm. I do not think there is probably a
solution in O(nlog(n)) in constant space either... I will see if I can
find a bound to tie i
"That number wont ever change. Regardless if you have 2 numbers or
257 numbers in your array. If you scale that to 32 bit numbers, you
get the following requirement ~ 135,000,000 distinct integers. It is a
large requirement, but it is constant and capable of determining what
you want regardless i
On Aug 24, 10:19 pm, wbspresslyjr <[EMAIL PROTECTED]> wrote:
> On Aug 21, 10:13 pm, L7 <[EMAIL PROTECTED]> wrote:
>
> > Sorry. I wrote too quickly. The amount you need is not determined by
> > log, but by division.
> > For the sake of argument, say you could hold the value 0 - 255. This
> > mean
On Aug 21, 10:13 pm, L7 <[EMAIL PROTECTED]> wrote:
> Sorry. I wrote too quickly. The amount you need is not determined by
> log, but by division.
> For the sake of argument, say you could hold the value 0 - 255. This
> means we are dealing with 8-bit storage, but it makes the example
> easier. Yo
Oops -- sorry, I have been working on that problem lately... I guess I
didn't see that the problem you were working on was different --
Cheers,
W
On Aug 24, 5:46 pm, L7 <[EMAIL PROTECTED]> wrote:
> On Aug 24, 1:00 am, wbspresslyjr <[EMAIL PROTECTED]> wrote:
>
> > I've heard this problem stated a
I should take my statement regarding the O(n) space for DP back ...
If we don't care storing each intermediate result, ... then space is also
O(1).
On 8/24/07, Lego Haryanto <[EMAIL PROTECTED]> wrote:
>
> For the DP recurrence, consider f(i) is the "best contiguous sum ending at
> this index i".
On Aug 24, 2:11 am, wbspresslyjr <[EMAIL PROTECTED]> wrote:
> Oops -- for approach 1. down here, I meant to say that the hash table
> breaks the constant space requirement... I guess I got ahead of
Depends on how you implement the hash. See above for a perfectly
constant-size hash approach.
-
On Aug 24, 1:00 am, wbspresslyjr <[EMAIL PROTECTED]> wrote:
> I've heard this problem stated as such: assume you have an array of N
> numbers, each ranging on the interval [1,N-1], only one of these
> elements repeating in Read-Only memory. You only have O(1) (constant)
> "scratch" space to work
Patents for Electromagnetics and Bioma nipulation
http://soleilmavis.spaces.live.com/blog/cns!9B6CD1D7F6F8F411!2177.entry
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this grou
For the DP recurrence, consider f(i) is the "best contiguous sum ending at
this index i".
f(i) = a[i], if i == 0
f(i) = max(a[i], f(i-1)+a[i]), on other cases
Basically, for each index i, to end a subarray ending at i, it's obvious
that we can either "extend" the best solution for previous index,
I thought I already answered earlier even thought it's just words and no
code.
sum = 0
best = -INF
FOREACH val IN a DO
sum = sum + val
best = MAX(best, sum)
IF sum < 0 THEN sum = 0;
ENDFOR
O(n) runtime, O(1) space.
DP can be done as well in O(n), but due to the nature of DP, you'll n
For all pairs shortest paths you could use Floyd Warshall. For single source
shortest paths, you can use Dijkstra's Algorithm, or even Bellman Ford
algorithm if negative cost cycles are allowed.
- Original Message -
From: "TheTravellingSalesman" <[EMAIL PROTECTED]>
To: "Algorithm Geeks"
int gcd(int a, int b) { return (b==0 ? a : gcd(b,a%b)); }
http://en.wikipedia.org/wiki/Euclidean_algorithm
On 8/17/07, Muntasir Azam Khan <[EMAIL PROTECTED]> wrote:
>
>
> On Aug 17, 6:53 pm, anshu <[EMAIL PROTECTED]> wrote:
> > Do you think sorting would help here?
> > I mean, arranging the numbe
Everyone ,
I have posted the solution for this problem in O(n) also with O(nlogn) .
Just check my previous mails in this loop mail.
---
Peeyush Bishnoi
On 8/16/07, Chonku <[EMAIL PROTECTED]> wrote:
>
> I think the only faster way I know off is by using a hashset which uses
> O(nlog(n/m)) time but
what is the DP recurrence?
On 8/23/07, ilija <[EMAIL PROTECTED]> wrote:
>
>
> If the subarray needs to be continuous, then you can do it using DP.
> If it doesn't, you can do it using an O(n) algo - simply sum all the
> positive integers.
>
> On 22 kol, 19:55, Ravi <[EMAIL PROTECTED]> wrote:
> > Y
I think the only faster way I know off is by using a hashset which uses
O(nlog(n/m)) time but the value comes out to be numerically closer to
O(nlogn).
On 8/16/07, dsha <[EMAIL PROTECTED]> wrote:
>
> Hi there,
>
> I'm interested in the following problem: there is an array of integers
> that conta
Amazing,
I love your solution. Good call Vaibhav
On Aug 17, 12:51 am, "Vaibhav Jain" <[EMAIL PROTECTED]> wrote:
> if u know the range of values stored in array then
> let me assume values 1 to k then u can calculate sum of numbers stored in
> array in O(n) complexity.
> after that apply formul
Hi all,
Please let me know if this pseudo code gives correct solution for iterative
post-order traversal of a binary tree.
void postOrderTraversal(Tree *root)
{
node * previous = null;
node * s = null;
push(root);
while( stack is not empty )
{
Since it s a DAG, just multiply all the edge weights by -1. Then use
dijkstra's to find the min shortest path.
Wether some of the edge weights are negative or not, it shouldn't
effect the solution as when using dijkstra's, we take the min node
potentials. ,--- This can be proven
On Aug
I'm trying to implement this in java.
Given N nodes and M arcs, whats the fastest known implementation for
the shortest path.
I'm currently making use of the jgrapht library for java. The link is
given below.
http://jgrapht.sourceforge.net/
Any suggestion will be much appreciated.
--~--~
can u please how to find in o(n* log n)?
On 8/16/07, dsha <[EMAIL PROTECTED]> wrote:
>
>
> Hi there,
>
> I'm interested in the following problem: there is an array of integers
> that contains each element only once except for one element that
> occurs exactly twice. Is there a way to find this
Hi all,
Please let me know if this pseudo code solution is correct for iterative
post-order traversal of a binary tree.
void postOrderTraversal(Tree *root)
{
node * previous = null;
node * s = null;
push(root);
while( stack is not empty )
{
s
I would like to see your code for the first case.
I really doubt that there exists an O(n) algo for this.
On 23 kol, 16:11, "Lego Haryanto" <[EMAIL PROTECTED]> wrote:
> Either case is O(n), in fact.
>
> On 8/23/07, ilija <[EMAIL PROTECTED]> wrote:
>
>
>
> > If the subarray needs to be continuous,
adding the numbers together is not constant space! that is logarithmic
space! As in log base 2 of N bits to represent the number... Thus, as
n grows large, your storage to hold the sum of the numbers is growing
logarithmically in the number of bits per element... Not to mention
that if the number
Here is the solution in PERL (this takes an Integer arg for the size
of the list of numbers, and outputs the list, the walks through the
lists, and the single repeating element) :
#!/usr/bin/perl
# setup problem -- this will embed the numbers 1...(N-1) into cells
1...N with one duplicate
# first
27 matches
Mail list logo
