CareerCup

I believe it could be done in O(n) as below:

//pseudo code
    pivot1 points to start of subsequence
    pivot2 moves forward accumulating elements
    vector sequences to store sequences that match S and P
    int maxLength=size(array);

    initially pivot1 = pivot2 = 0, sum = array[0], product = array[0].
    while(pivot2<size)
       ++pivot2, 
       sum = sum+array[pivot2]; product = product*array[pivot2];
       		while((sum>S || product>P)){ //move pivot1 if sum or product exceeded
			sum=sum-array[pivot1]; product = product/array[pivot1]; ++pivot1;
			if(pivot1<size) break;
		}
          add pivot1 and pivot2 to sequences, //i.e. elements between pivot1 and pivot2 satisfy
          if(pivot2-pivot1 < maxLength) maxLength = pivot2-pivot1;

pivot1 moves n and pivot2 moves n => total is 2n => O(n)

//!Complexity O(2n+1) = O(n).
//The code is written to demonstrate the algorithm and might fail for certain inputs
#include <iostream>
using namespace std;
int numcomputs = 0;
int main(){
	int array[] = {2,3,4,5,4,1,2,3,1,1,1,2,2,4,6,2,2,4,5,1,2,3,8,8};
	int S = 21, P = 384,pivot1, pivot2,size = sizeof(array)/sizeof(int);
	long sum = 0, product = 0;
	int minLength=size,minLenP1 = 0,minLenP2=0;
	pivot1 =0; pivot2 = 0; sum = array[0]; product = array[0];

	while(pivot2<size){
		++pivot2;
		sum = sum+array[pivot2]; product = product*array[pivot2];
		++numcomputs;
		while((sum>S || product>P)){ //move pivot1 if sum or product exceeded
			sum=sum-array[pivot1]; product = product/array[pivot1]; ++pivot1;
			++numcomputs;
			if(pivot1>size) break;
		}
		if(sum==S && product==P && ((pivot2-pivot1) < minLength)){
			if((pivot2-pivot1) < minLength){
				minLength = pivot2-pivot1;
				minLenP1 = pivot1,minLenP2=pivot2;
			}
		}
	}
	if(minLength==size && minLenP1==0 && minLenP2==0)
		cout<<"No string found!!"<<endl;
	else{
		cout<<"Length of sequence: "<<minLength;
		cout<<".    array["<<minLenP1<<"] to array["<<minLenP2<<"]"<<endl;
		for(;minLenP1<=minLenP2;++minLenP1)
			cout<<array[minLenP1]<<" ,";
		cout<<endl<<"size of array: "<<size<<", Total number of loopings: "<<numcomputs<<" .";
	}

}

gud work chennavarri

but YAHOO needs that this problem must run for all cases negative, zero as well as positive numbers too :( :(

Can anyone suggest solving this by divide and conquer approach? I mean recursion. THat should do it with more efficiency.

How about this approach that works with both zeros and -ve numbers?

Create two more arrays Sum[] and Product[] such that
Sum[i] = a[0]+a[1]+...+a[i]
Product[i] = a[0]*a[1]*...*a[i]

Now for every element in Sum[i] check if Sum[i]-S is present in the sub-array from 0 to i-1. If it is present check if the product also matches using the Product array.

We can decide on how to perform this repetitive search in Sum[i] to be better.

guys i think Kadane's algorithm would work just fine for this problem....

looks like there are 2 conditions
- A[i] should be a perfect divisor of P
- |curr_product| < |P| every iteration

If any of the above is not true you cannot take that chunk and need to reset curr_start and curr_end = i+1


This is only assuming u have +- integers

If u have array of real numbers then u would need a brute force and then optimization by DP for getting the product or sum

assuming positive values

int sub_array_with_sum(int s[], int n, int sum, int product)
{
	int currentSum, currentProduct;
	int i, j;

	currentSum = 0;
	i = j = 0;
	currentProduct = 1;

	while(j < n)
	{
		currentSum += s[j];

		if(currentSum < sum)
		{
			currentProduct *= s[j];
			j++;
		}
		else if(currentSum > sum)
		{
			if(i == j)
			{
				i++;
				j++;
				currentSum = 0;
				currentProduct = 1;
			}
			else
			{
				currentSum = currentSum - s[i] - s[j];
				currentProduct /= s[i];
				i++;
			}
		}
		else
		{
			currentProduct *= s[j];
			if(currentProduct == product)
				return j-i+1;

			currentSum -= s[i];
			currentProduct /= s[i];
			i++;
			j++;
		}
	}

	return -1;
}

It can be done in O(nlogn)
consider the array {2,-1,3,-4,5,1}
A=cumulative-sum,index = {(2,0),(1,1),(4,0),(0,3),(5,4),(6,5)}
P=cumulative product {2,-2,6,24,120,120}
sort A array on the basis of sum
take two pointers p1=0,p2=0;
and proceed .....

There is pretty straight forward solution and goes like what is written below.
1) find sum and product of all contigious elements.
2) Check trivially if any contigious sum, product is same.
3) check for all ranges, j, i such that sum(i - j) = product (i/j). where 0 > j < i & 0 < i < |A|

public void printEqualSumMul(int [] arr) {
int len = arr.length;
int [] sum = new int[len];
int [] mul = new int[len];

for(int i = 1; i < len; i++) {
sum[i] = sum[i-1] + arr[i];
}
for(int i = 1; i < len; i++) {
mul[i] = mul[i-1]*arr[i];
}
//Check if there is any contigious sequence which has same sum and mul
for(int i = 1; i < len; i++) {
if (mul[i] == sum[i]){
System.out.print("Elements with equal sum and mul :" + i + " " + i);
}
}
//Check for any range is having same sum and mul
for(int i = 1; i < len; i++) {
for(int j = 0; j < i; j++) {
if (i == j) continue;
int s = sum[i] - sum [j];
int m = mul[i]/mul[j];
if (s == m) {
System.out.print("Elements with equal sum and mul :" + i + " " + j);
}
}
}
return;
}

#include<stdio.h>
#include<conio.h>

int main()
{
int i,j,pro,sum,s=0,num=100000,p1,p2;
int arr[24];
int n=24;
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
scanf("%d%d",&pro,&sum);
int p;
j=0;p=1;
for(i=0;i<24;i++)
{
p=p*arr[i];
if(pro%p==0)
{
s=s+arr[i];
if(pro==p)
if(s==sum)
if(num>(i-j+1))
{ p1=j;p2=i;p=1;s=0;j=i+1; }
else
{
j=i+1;
p=1;
s=0;
}
}
else
{
p=1;s=0;
j=i+1;
}
}
for(i=p1;i<=p2;i++)
printf("%d",arr[i]);
return 0;
getch();
}

using Kadane's algorithm , we can find a contiguous sub-array whose sum = S.
Now check if product of sub-array =P.
If yes , then update the variable min_length;
(min_length--> stores the requisite minimum length)