@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
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
@ 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
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
@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
@ravindra
agree!
On Oct 24, 2:20 pm, ravindra patel ravindra.it...@gmail.com 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
@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
@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
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 )
@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
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 iiita2007...@gmail.com
wrote:
@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 kishen@gmail.com 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
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
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
14 matches
Mail list logo
