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
void subarr( int* arr, int n, int sum, int prod)
{
int lb = 0; // Lower bound of sub array
int s = 0; // Temporary sum
int p = 1; // Temporary prod
int mod_p = (prod > 0) ? prod : (prod * -1); // |prod|
int min_p = mod_p * -1; // -|prod|
int i=0;
int found = 0;
for(i=0; i<n; i++)
{
// Zero can't be sub array element if given product in not zero
if((arr[i] == 0) && (prod != 0))
{
lb = i+1;
s = 0;
p = 1;
continue;
}
s += arr[i];
p *= arr[i];
// If product is out of range bring it back in
while (p < min_p || p > mod_p)
{
p /= arr[lb];
s -= arr[lb];
lb++;
}
if( s== sum && p == prod)
{
printf ("Sub array is from index %d to %d\n", lb, i);
found = 1;
break;
}
}
if(!found)
printf("No Matching sub-array found\n");
}
Thanks,
- Ravindra
On Mon, Oct 25, 2010 at 2:04 AM, Kishen Das <[email protected]> wrote:
> @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
> of Parallelism.
> I long back agreed that the worst case for my algorithm is O(n^2 ) on
> single processor systems.
>
> The current problem is a variation of original subset problem which is
> NP-complete. ( http://en.wikipedia.org/wiki/Subset_sum_problem )
>
> I really appreciate a O(n) solution to this problem on a single-processor
> system.
>
> Kishen
>
> On Sun, Oct 24, 2010 at 1:50 PM, ravindra patel
> <[email protected]>wrote:
>
>> >> 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 for time complexity on scalar machine or on a parallel
>> machine. Unless specified otherwise, my assumption by default would be a
>> scalar one though.
>>
>> - Ravindra
>>
>>
>> On Sun, Oct 24, 2010 at 11:50 PM, ravindra patel <
>> [email protected]> 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
>>> many clocks are you gonna consume, assuming all your 100 processors are
>>> running in parallel.
>>>
>>> Buddy, with parallel processors you can reduce total computation time at
>>> most by a factor of number of processors you have (which will always be a
>>> constant, no matter how big it is). It has nothing to do with time
>>> complexity.
>>>
>>> Thanks,
>>> - Ravindra
>>>
>>>
>>> On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das <[email protected]>wrote:
>>>
>>>> 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 )
>>>>
>>>> Each of these assignments doesn't have any dependency with other
>>>> computations i.e.,
>>>> ( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) , ....
>>>> ( i )
>>>> and hence each of this can be assigned to a different processor.
>>>> So, each of these statements( iterations) of the inner-loop j can be run
>>>> in different processors, making it O(1).
>>>>
>>>> I am sorry, if people are still not getting my point !!!
>>>> This is the best I can do !!!
>>>>
>>>> Kishen
>>>>
>>>> On Thu, Oct 21, 2010 at 9:08 AM, ligerdave <[email protected]>wrote:
>>>>
>>>>> @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 and j?
>>>>>
>>>>> On Oct 20, 7:33 pm, Kishen Das <[email protected]> wrote:
>>>>> > 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 parallel constructs.
>>>>> >
>>>>> > If you don't understand GPUs or not familiar with parallel constructs
>>>>> in
>>>>> > Java, then my algorithm will definitely look like O ( n ^ 2 ).
>>>>> >
>>>>> > Kishen
>>>>> >
>>>>> >
>>>>> >
>>>>> > On Wed, Oct 20, 2010 at 4:25 PM, ligerdave <[email protected]>
>>>>> 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 <[email protected]> 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 )
>>>>> > > > {
>>>>> >
>>>>> > > > for ( j = i to j = 0 ) {
>>>>> > > > sum[j] += A[ i]
>>>>> > > > product[j] *= A [ i]
>>>>> >
>>>>> > > > }
>>>>> >
>>>>> > > > for( k=0 to k= i )
>>>>> > > > if ( sum[k] == S and product[k] == P ) {
>>>>> > > > Answer is the sub array A[k to i ]
>>>>> > > > break
>>>>> >
>>>>> > > > }
>>>>> > > > }
>>>>> >
>>>>> > > > Kishen
>>>>> >
>>>>> > > > On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh <
>>>>> [email protected]
>>>>> > > >wrote:
>>>>> >
>>>>> > > > > @ Rahul patil ofcourse array may have negative or positive
>>>>> integers
>>>>> >
>>>>> > > > > @ Kishen both O(n) and O(n logn) solutions was asked in this
>>>>> yahoo
>>>>> > > coding
>>>>> > > > > round question
>>>>> >
>>>>> > > > > On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh <
>>>>> > > > > [email protected]> wrote:
>>>>> >
>>>>> > > > >> Given an array of length N. How will you find the minimum
>>>>> length
>>>>> > > > >> contiguous sub - array of whose sum is S and whose product is
>>>>> P . Here
>>>>> > > > >> S and P will be given to you.
>>>>> >
>>>>> > > > >> --
>>>>> > > > >> You received this message because you are subscribed to the
>>>>> Google
>>>>> > > Groups
>>>>> > > > >> "Algorithm Geeks" group.
>>>>> > > > >> To post to this group, send email to
>>>>> [email protected].
>>>>> > > > >> To unsubscribe from this group, send email to
>>>>> > > > >> [email protected]<algogeeks%[email protected]>
>>>>> <algogeeks%2bunsubscr...@googlegroups .com>
>>>>> > > <algogeeks%2bunsubscr...@googlegroups .com>
>>>>> > > > >> .
>>>>> > > > >> For more options, visit this group at
>>>>> > > > >>http://groups.google.com/group/algogeeks?hl=en.
>>>>> >
>>>>> > > > > --
>>>>> > > > > ABHISHEK KUMAR SINGH
>>>>> > > > > BTECH (INFORMATION TECHNOLOGY)
>>>>> > > > > IIIT ALLAHABAD
>>>>> > > > > 9956640538
>>>>> >
>>>>> > > > > --
>>>>> > > > > You received this message because you are subscribed to the
>>>>> Google
>>>>> > > Groups
>>>>> > > > > "Algorithm Geeks" group.
>>>>> > > > > To post to this group, send email to
>>>>> [email protected].
>>>>> > > > > To unsubscribe from this group, send email to
>>>>> > > > > [email protected]<algogeeks%[email protected]>
>>>>> <algogeeks%2bunsubscr...@googlegroups .com>
>>>>> > > <algogeeks%2bunsubscr...@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 [email protected].
>>>>> > > To unsubscribe from this group, send email to
>>>>> > > [email protected]<algogeeks%[email protected]>
>>>>> <algogeeks%2bunsubscr...@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 [email protected].
>>>>> To unsubscribe from this group, send email to
>>>>> [email protected]<algogeeks%[email protected]>
>>>>> .
>>>>> 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected]<algogeeks%[email protected]>
>>>> .
>>>> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
