@Kishen
The inner while loop increments the lower bound from where we are taking
product and sum. Total number of iterations of inner while loop can be n in
the worst case (when magnitude of last element is greater than that of given
product). So the array will be traversed twice.
Thanks,
- Ravin
How do you claim that its O(n) when you have a while-loop inside the
for-loop?
What is the complexity of the inner while loop ?
What is the worst case complexity, if only the last element of the array
matches the product and the sum?
Kishen
On Wed, Oct 27, 2010 at 2:01 PM, ravindra patel wrote:
@ravindara yeah this works perfect
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For mo
Here is a simple implementation. Complexity O(n). Please let me know if you
find any issues with this.
Assumptions as stated in original problem -
1- Required sub array is contiguous
2- Given array has only integers (+ve and -)
// Params are array arr, length of array n, given sum and product
v
@Ravindra, Ligerdave
You guys are all right. But with GPUs, you can literally have thousands of
threads running in parallel.
Again, my aim was not to prove that my O(n ^ 2) algorithm is O ( n) on a
single processor system.
It was more towards making the members of this group to think on the lines
o
@saurabh koar : no it will give that sub array .. but "kishan das" solution
is good...
btw my code explanation is
A: 2 4 356
PRODUCT:2 8 24 120 720
SUM 2 6 9 14 20
suppose i want sum 8 and product 15
make hash table for product array (in hashtable
@ravindra
agree!
On Oct 24, 2:20 pm, ravindra patel wrote:
> @ Kishen
> So lets say you have 100 parallel processors and you are given an array of
> 100 elements, then the loop will execute in 1 clock. Now lets say on the
> same machine you are given a problem array of 1 million elements. So how
@Mohit: What I understand that in your solution the sum and product array
contains the sum and products of contiguous sub-array starting from 0 to i
(index of array A). What happens when the expected sub array starts form an
index other than 0?
--
You received this message because you are subscri
>> It has nothing to do with time complexity.
My bad. Wrong choice of words. So in the PRAM model you can say the time
complexity is O(1), a pure theoretical concept. But the cost still remains
O(n), isn't it.
I guess now onwards we'll have to specifically ask interviewers whether they
are asking
@ Kishen
So lets say you have 100 parallel processors and you are given an array of
100 elements, then the loop will execute in 1 clock. Now lets say on the
same machine you are given a problem array of 1 million elements. So how
many clocks are you gonna consume, assuming all your 100 processors a
@Kishen
i think parallel computation means when you have two tasks, instead
having only one person working on both, you have two persons working
simultaneously. however, that doesnt mean you dont have to do the job
right? the problem isn't in the inner loop.
when you have one loop inside of anothe
Ok, if you look at the inner loop, it is -
for ( j = i to j = 0 ) {
sum[j] += A[ i]
product[j] *= A [ i]
}
This is as good as executing -
sum[i] = sum [ i ] + A[ i ] ---> ( 1 )
sum[i-1]= sum[i-1]+ A[i] > ( 2 )
--
---
---
sum[0] = sum[ 0]+A[i] --> ( i )
E
@Kishen
I don't have much knowledge on parallel computation in OpenCL or CUDA.
Do you mean parallelised="not have to do the computation at all"?
did you mean without knowing the boundary of the inner loop which is
depended on the outer loop, the inner loop would be smart enough to
figure out the i
Well, looks like people are not understanding when I say "run a loop in
parallel "!!!
Please look at some of the examples on Nvidia website on how computations
can be parallelised in OpenCL or CUDA.
And also some of the high level programming languages like Scala which is
also providing these para
@Kishen
as long as you have one for loop in another, you wont have O(n). it
will most likely run O(n^2)
On Oct 19, 7:41 pm, Kishen Das wrote:
> In the below code the jth and kth inner for loops can be run in parallel
> making them O(1) and the entire thing O(n).
>
> for ( i=0 to i=N-1 )
> {
>
> f
i wanna get a clear picture of this before start.
when you say min length of contiguous sub of an array
let's say array A=[3,1,2,3,4,5], N=6
are below both good solutions?
A[0] to A[m] where m<=N
A[i] to A[m] where i<=m m<=N
On Oct 19, 3:58 am, Abhishek Kumar Singh
wrote:
> Given an array of
@W Karas
Can you please give an example and explain your approach.
Anurag Sharma
On Tue, May 18, 2010 at 12:17 AM, W Karas wrote:
> One (space-intensive) idea:
>
> Re-represent each string as a set of pairs (character, position of
> character). Then sort each set of pairs by character. Then f
One (space-intensive) idea:
Re-represent each string as a set of pairs (character, position of
character). Then sort each set of pairs by character. Then find
corresponding sequences in the sorted lists of pairs, where the
character and the difference between position is the same from pair to
pa
18 matches
Mail list logo
