CareerCup

Find the longest non-negative subarray

intuitive answer: k would be the index where Ak-Bk is maximum.
iterate through array, find Ak-Bk, compare with max so far, save k with max.

There was one problem such that there are n gas stations in a circle.

Now the amount of fuel he can fill up at each gas station is given by array a[n]
and distances is given by b[n-1]

Now he can choose any gas station and we have to find out the gas station at which he can start and can traverse all gas stations.
Note: He can only refill at gas station and if fuel end up in between he cant go any further.

So , in the similar way in this problem we can take each a[i]-b[i] as a gas station node.

Now our objective will be to find a point k such that he can traverse farthest enough starting from that point.

That problem was solved as suppose he start from some arbitrary station a[k] and it tries to trverse in forward direction from that point.
If he runs out of fuel in between than he should have started from some point before k and include all points before point k until he had got enough fuel to start his journey in forward.

So in the same take any index i.

Make summation until u are getting summation (a[i]-b[i]) as positive.

If we are getting -ve at some point than move backward until the summation a[i]-b[i] is again positive.

for code

for(int i=0;i<n;i++)
c[i]=a[i]-b[i];
int count=n;
int sum=0,i=0,k=0;
while(count){
while(c[i]+sum>=0){
i++;
count--;
}
while(a[k-1%n]+sum<0){
k--;
count--;
}

}

Hi Jan,

If you have subscribed to this question or if you ever happen to vist this page again, please explain the question with example, it's not very clear.

Question 1) Did they want you to find you cummilative 'non negative sum' from k
to end of array.... or


Question 2) Did they want you to find cumilative 'non negative sum' from
begining to k?

a={ 6 3 4 7 9 1 0}
b={ 5 2 6 6 4 6 1}

a-b={ 1 1 -2 1 5 -5 -1}

Answer 1) If they asked you Question 1, certainly 0 is one answer
to find other indexx... do the cumulative sum of a-b from back

SUM = {0-1,-2,0,-1,-6,-1}
so the answer is all indices with non-negative value
in this case it's 0 and 3

Answer 2: if they asked you question 2, for sure one answer is n-1....
and for other answers... do the cummulative sum of {a-b} from begining

SUM= {1,2,0,1,6,1,0}
so the answer is all indices with non-negative value ,
in this case all indices are the answer....

Please correct me I got you wrong...

@Crime_master_gogo

I guess the question is we have to find an index k such that starting from index k we will be able to sum all the array elements to zero such that we don't get sum as -ve in between.

suppose if we start from index k

than seq of summation would be

k,k+1 ,k+1 ....n...1,2 ,3 ...k-1+

for the original question.

Init:
for (i=0;i<n;i++)
c[i]=a[i]-b[i];
sum = 0;
start = 0;
i = start;
Then scan C from index i, sum=sum+c[i];

keep increasing i if sum>=0;

otherwise if sum<0; it means that any index between i and start is not our answer
so reset sum = 0; start = (i++)%n;

until that i==start, which means all summations has been checked.

So similar to nitin's answer:

the code:

int findIndex(int a[], int b[], int n)
{
for(int i=0;i<n;i++)
c[i]=a[i]-b[i];

int count=n;
int sum=0,i=0,start=0;
while(count)
{
while(c[i]+sum>=0)
{
sum = sum + c[i];
i++;
count--;
}

start = (i++)%n;
i = start;
sum = 0;
count = n;
}
return start;
}

I didn't read all the answers... one possible soln in O(n)

This question is very similar to Increasing Sum which can be done in O(n).

here find ai-bi and store in an array. Reverse the signs and find the increasing Sum. Since the sign was reversed it will be actually min sum. We can find the end index of this series.

The next number would be k. Reasoning: For reversed sign increasing sum let the start index be m and let the end index be n. Means Summation(m,n) leads to a big negative no say -M. And it also indicates that summation of all other nos = M and for the other nos at no point it will lead to a negative summation if that was the case then Summation(m,n) != M

Note: Special care needs to be taken since its circular...Increasing sum sequence we cannot find in 1 pass it might need 2 pass but still it is O(n).

I think this should work....

Step 1: Create a new array containing A[i] - B[i] elements. O(n)
Step 2: k=0, have a variable sum and add the values from i=0 to n from this new array. If the value goes negative at index j, reset k to j+1 and sum to 0. At the end k will be our index. One pass O(n)

Sample example:
A = [ 4 3 9 7 ]
B = [ 6 2 5 10 ]

Diff = [ -2 1 4 -3 ]

sum=0
k=0
sum=sum+Diff[0] = -2
reset k=1 and sum=0
sum=sum+Diff[1] = 1
Keep the sum to be 1 and k=1
sum=sum+Diff[2] = 5
Keep the sum=5 and k=1
sum=sum+Diff[3] = 2
Sum is still +ve, keep it and k=1 as well.

Array ends, we have k=1 --- answer.

Suppose the array d contains the n differences i.e. d[i] = a[i] - b[i]. For the below d[i..j] detones the sum of elements in d from index i to j inclusive.

Without loss of generality assume d[n] > 0. There has to be one such d[n]. Otherwise all values are 0 and every index is a solution.

Starting from d[n] go backwards to find the max sum sequence that includes d[n]. This means going back as long as the running sum is positive while keeping track of the max sum. This is O(n). Suppose d[i..n] is the max sum. d[n] > 0 implies d[i..n] > 0.

The index i is our solution i.e. starting index such that all cumulative sums are >= 0.

Proof:

For all i <= j <= n, d[i..j] >= 0 :
If d[i..j] < 0 then d[i..n] = d[i..j] + d[j+1..n] < d[j+1..n]. This violates the premise that d[i..n] is the max sum.

For all j < i, d[i..n] + d[1..j] >= 0 :
If d[i..n] + d[1..j] < 0 then 0 = d[1..n] = d[i..n] + d[1..j] + d[j+1..i-1] and so d[j+1..i-1] > 0. This means d[j+1..i-1] + d[i..n] = d[j+1..n] > d[i..n]. Once again the premise that d[i..n] is max sum is violated.

Done in O(n)

public static int findIndex(int[]a,int[]b){
		int sum = 0;
		int end = a.length;
		int start = 0;
		int i = 0;
		for(i=0;i <= end-1 ;i++){
		  sum = sum + a[i]-b[i];
		  System.out.println("sum in main" + sum);
		   if(sum<0){
			   sum=0;
			   start = start+1;
			   continue;
		   }else if(start != 0 && i == end-1){
			   System.out.println(sum+"::::"+ start +"::");
			   if(sum ==0)
				   break;
			  i=-1;
		      end = start;
		      continue;
		   }
		}
		return start;
	}

This is O(n) solution -

void findindex()
{
int a[]={6,3,4, 7 ,9 ,1, 0};
int b[]={5 ,2 ,6 ,6 ,4 ,6 ,1};
int c[]={1 ,1 ,-2, 1, 5, -5, -1};

int n=7;
int k,sum;
int start =0;

do
{
k=start;
sum =0 ;
while(k<n)
{
sum +=c[k];
if (sum<0) break;
else k++;
}
if (k==n) {
printf("start=%d\n",start);
start = start+1;
}
else
start = k+1;
}
while(start!=n);

}

In O(N) time, it works I tested it...

(defn find-k [a b]
  (let [N (count a)]
    (loop [kl 0
	   kr kl 
	   s (diff a b kr)
	   n 1]
      (cond
       (= n N) kl
       (> s 0) (let [krn (mod (inc kr) N)]
		 (recur kl krn (+ s (diff a b krn)) (inc n)))
       :else   (let [kln (mod (dec kl) N)]
		 (recur kln kr (+ s (diff a b kln)) (inc n)))))))

Basic idea is to start walking (it doesn't matter where from) remembering the starting position kl (k-left) and current position kr (k-right). If sum s becomes negative, decrease the kl wrapping if necessary and add it to the sum, if sum is positive continue increasing kr.

Compute a prefix sum of (ai - bi) in another array (or can use a or b if no extra space but array modification is permissible). At index i in the prefix sum, you will have the sum of all (ak - bk) for 0 <= k <= i.

Find the minimum value in the prefix sum. This is where you want to start.

For example lets say you have two arrays that both sum to 100 of length 20. At index 10, lets say you have the minimum value in the prefix sum of the differences, say its -67. Then from 10 to 20 you know that the sum of the differences is 67.

If you start with k at 11, then from 11 to 20 you will sum to 67. Then you will sum back down to 0 from 1 to 10, ensuring that the summation is never negative.

You ask, but how can you guarantee that the sum will not dip below zero? Because we start at the minimum value in the prefix summation, you can guarantee this.

Time: O(n) Space: O(n) ( or O(1) if array modification is permitted)

@ki: As I understood the algorithm, you need to calculate the prefix sum values on D, which would be:

D = (0 0 88 88 6 -68 -68 -73 9 0)

and here the minimum number is -73, so you start your summation from the next index that is the second last index. The algorithm works from there. Good job Arnab!!

<pre lang="java" line="1" title="CodeMonkey97053" class="run-this">simple algorithm:

Say A = 2 1 7 5 3 2
Say B = 4 1 3 8 1 3
Diff D = -2 0 4 -3 2 -1
Sum (A-B) S1 = -2 -2 2 -1 1 0 (use k=1 here)
Min (S1): M = -2
Add -ve M to S1 to get S2
S2 = 0 0 4 1 3 2
Find k where S[k] == D[k]
k = 2 or 3

Another example

A = 5 1 2 1 5
B = 1 6 1 5 1
D = 4 -5 1 -4 4
s1= 4 -1 0 -4 4
M = -4
s2= 8 3 4 0 4

at k==5, d[k] == s2[k]
</pre><pre title="CodeMonkey97053" input="yes">
</pre>

1. Find C[i] = A[i] – B [i].
2. C will contain both positive and negative numbers. Repeat following:
a) Add consecutive positive numbers are added (including rolled over numbers), and add the result as one number back into C. Similarly add consecutive negative numbers. For each such a composite number keep track of starting index in the original array.
b) The new array C will contain equal number of positive and negative numbers.
c) If C contains exactly one positive and one negative number, then the trace back from positive number to derive at original index where it came from. That index is k and break the loop.
 Else C[i] = C[2*i] + c[2*i – 1]. This means two successive numbers (one will be positive and one negative) are added and stored back into C. Now again keep track of starting index for each composite number.

For ex:
A = 12 7 10 2 4 9 8
B = 4 9 8 12 2 10 7
C= 8 -2 2 -10 2 -1 1
C= 9 -2 2 -10 2 -1
C= 7 -8 1
C= 8 -8
Now trace back from which number 8 originated from (8 <= 1 <= 2 <= 2 <= (4-2)), which is at the index 4 in this example.

Total complexity O(n) = O(n) for subtraction and O(n) for the rest of the derivation (at each operation the size of C goes down by at least one).

1. Find C[i] = A[i] – B [i].
2. C will contain both positive and negative numbers. Repeat following:
a) Add consecutive positive numbers are added (including rolled over numbers), and add the result as one number back into C. Similarly add consecutive negative numbers. For each such a composite number keep track of starting index in the original array.
b) The new array C will contain equal number of positive and negative numbers.
c) If C contains exactly one positive and one negative number, then the trace back from positive number to derive at original index where it came from. That index is k and break the loop.
 Else C[i] = C[2*i] + c[2*i – 1]. This means two successive numbers (one will be positive and one negative) are added and stored back into C. Now again keep track of starting index for each composite number.

For ex:
A = 12 7 10 2 4 9 8
B = 4 9 8 12 2 10 7
C= 8 -2 2 -10 2 -1 1
C= 9 -2 2 -10 2 -1
C= 7 -8 1
C= 8 -8
Now trace back from which number 8 originated from (8 <= 1 <= 2 <= 2 <= (4-2)), which is at the index 4 in this example.

Total complexity O(n) = O(n) for subtraction and O(n) for the rest of the derivation (at each operation the size of C goes down by at least one).

eg. same example as above.
A = 12 7 10 2 4 9 8
B = 4 9 8 12 2 10 7

Find C which is C[i] = (A[i] - B[i])
C= 8 -2 2 -10 2 -1 1

k=0;
round2=0;

For(i=1;i<n;i++)
{
if(C[i]+C[k]>=0)
{ C[k]+=C[i]; C[i]=0; }
else
{ k=i; }

if(i+1==n && round2==0)
{ round2=1; i=0; }

}

if(C[k]==0)
return k; //solution
else
return NO_POSSIBLE_SOLUTION;

Algorithm: O(2n)

C[i] = A[i]-B[i], N is the length of A or B, -- O(N) to finish
for i = 0; i < N; i++
{
j = i
do{ //circle sum from i
sum += C[j]
if (sum<0):
sum = 0
i = j+1 //i is the next starting point
break
j = (j+1==N) ? 0:j+1
}
while j != i
if j==i return i
}
return None

You can keep a variable contains summation of ( Ai - Bi ); once this variable becomes negative then you set the k with the following index

note: there is always solution for this problem as long as sum(A) = sum(B)

int getKIndex ( int a[], int b[], int N)
{
int s = 0 ; int k = 0 ;
for ( int i = 0 ; i < N ; i++)
{
s += a[i] - b[i] ;
if ( s < 0 )
{
s = 0;
k = ( i + 1 ) % N ;
}
}
return k ;
}

The task is to find the minimum sum of Products of two arrays of the same size, given that k modifications are allowed on
the first array. In each modification, one array element of the first array can either be increased or decreased by 2.
Notethe
product sum is Summation (A[i]*B[i]) for all i from 1 to n where n is the size of both arrays