I have been practising algorithmic questions and I came across this one.
Given an array(of both +ve and -ve) numbers, I have to find a contiguous subarray such that, the sum is divisible by any number K, and the subarray should be of possibly maximum sum. For eg.a={1,2,2,1,1,4,5,3} and k=5 and the maximum sum subarray divisible by k would be{2,2,1,1,4,5}, sum = 15
Presently all I can think of is, each element is having two possibilities, either include it in the target subarray or not. But this would be an exponential algorithm.
EDIT: is it possible to solve this in Linear Time. Please Help
3
votes
4 Answers
3
votes
The keyword for this problem is prefix sum.
The pseudo code to compute them will look like this:
int prefix_sum[N];
prefix_sum[0] = array[0];
for (i = 1; i < n; i++)
prefix_sum[i] = prefix_sum[i-1] + array[i];
Now we have the prefix sum, the only thing remaining is to find the sub array. We can look at the sum of subarray just by subtracting the (previous to) first prefix sum value for the subarray from the last.
The properties we care for, are sum and the divisibility by K. To find now the max sum subarray we look at each element once. While we look at each element once, we do 4 things:
Divide the prefix sum modulo K:
rem[i] = prefix_sum[i] % K;. This way we knew that a sub array is valid if and only ifrem[start_subarray] + rem[end_subarray] == K. But we not only use it to check whether the sub array is divisible, no we can also use it to find for the sub array (see below).We use an array
max_startof the sizeK. When we compute the remainder ofprefix_sum[i]we store the indexiinmax_start[rem[i]]when the prefix_sum[i] is greater that prefix_sum of the current index inmax_start[rem[i]]. Now we have the ability to look up in O(1) the index with the greatest prefix sum, that has an given remainder.For our element
array[i]we look at therem[i]and lookup the element with the greatest prefix_sum that has an remainder ofK-rem[i]. When we do that we get the sub array that a) is divisible by K and b) has the greatest sum (for all arrays that end with this elementarray[i]).We check if the sum of this array is bigger than our current biggest found array, and when, set this array as our new top scorer.
The details are very hairy, as you have to look for the right indices and you have to care for all the exception cases (like when nothing is found...), but I guess you will get the idea of the algorithm. The run time for this is O(n), and thanks to the prefix sum it should work for negative and positive numbers.
1
votes
If not negative numbers, every continuous subarray with sum divisible by K should of been consisting of smaller sum-divisible subarrays of at most K elements. But with negative numbers it's not true.
So basically the only option is to check every subarray for its sum to be divisible. Like this:
a = [1,2,2,1,1,4,5,3]
K = 5
max_a = []
max_len = 0
for i in range(len(a)):
for j in range(i+1, len(a)+1):
s = sum(a[i:j])
if s % K == 0 and j-i > max_len:
max_len = j-i
max_a = a[i:j]
print max_a
Well, it's polynomial, but still not very effective.
0
votes
I wrote a divide-and-conquer algorithm for this.
If FindMaxSubarrayDivisible(array,start,end,maxStart,maxEnd,sum,k) is a function for calculating the max contiguous subarray divisible by k, then:
FindMaxSubarrayDivisible(array, start, end, out maxStart, out maxEnd, out sum, k)
mid=(start+end)/2;
FindMaxSubarrayDivisible(array, start, mid, out leftMaxStart, out leftMaxEnd, out leftSum, k)
FindMaxSubarrayDivisible(array, mid, end, out rightMaxStart, out rightMaxEnd, out rightSum, k)
FindMaxCrossingSubarrayDivisible(array, start, end, out crossMaxStart, out crossMaxEnd, out crossSum, k)
Determine the max of the three above, if exists
FindMaxCrossingSubarrayDivisible can be done in O(max(n,k)) time using O(k) storage. My idea is to have an array of k integers, where each element stores the max cross sum of the right side of the array of remainder i where 0 <= i < k. Do the same for left side of the array, then merge in O(k) time. If k << n, then this algorithm is O(n lg n) time.
I've written the following C# code for this.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication3
{
class Program
{
static int k;
static void Main(string[] args)
{
k = 5;
int maxStart;
int maxEnd;
int sum;
int[] a = new int[] { };
f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);
a = new int[] { 1 };
f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);
a = new int[] { 2,1 };
f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);
a = new int[] { 2,3 };
f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);
a = new int[] { 3,2,3,2 };
f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);
a = new int[] { -5,10,15,-5 };
f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);
a = new int[] { 1, 2, 2, 1, 1, 4, 5, 3 };
f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);
a = new int[] { -1,-2,-3,-4,-5 };
f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);
}
static void f(int[] a, int start, int end, out int maxStart, out int maxEnd, out int sum)
{
if (end - start < 0)
{
throw new ArgumentException();
}
else if (end - start == 0)
{
maxStart = start;
maxEnd = end;
sum = 0;
}
else if (end - start == 1)
{
if (a[start] % k == 0)
{
maxStart = start;
maxEnd = end;
sum = a[start];
}
else
{
maxStart = -1;
maxEnd = -1;
sum = 0;
}
}
else
{
int leftMaxStart;
int leftMaxEnd;
int leftMaxSum;
int rightMaxStart;
int rightMaxEnd;
int rightMaxSum;
int mid = (start + end) / 2;
f(a, start, mid, out leftMaxStart, out leftMaxEnd, out leftMaxSum);
f(a, mid, end, out rightMaxStart, out rightMaxEnd, out rightMaxSum);
int[] r = new int[k];
int[] rightEnds = new int[k]; //right end index array
for (int i = 0; i < k; ++i)
{
rightEnds[i] = -1;
}
int midSum = a[mid - 1] + a[mid];
int midRightSum = midSum;
int mod = Math.Abs(midRightSum % k);
if (midRightSum > r[mod] || rightEnds[mod] == -1)
{
r[mod] = midRightSum;
rightEnds[mod] = mid + 1;
}
for (int i = mid + 1; i < end; ++i)
{
midRightSum += a[i];
mod = Math.Abs(midRightSum % k);
if (midRightSum > r[mod] || rightEnds[mod] == -1)
{
r[mod] = midRightSum;
rightEnds[mod] = i + 1;
}
}
int[] l = new int[k];
int[] leftStarts = new int[k]; //left end index array
for (int i = 0; i < k; ++i)
{
leftStarts[i] = -1;
}
int leftSum = 0;
for (int i = mid - 2; i >= start; --i)
{
leftSum += a[i];
mod = Math.Abs(leftSum % k);
if (leftSum > l[mod] || leftStarts[mod] == -1)
{
l[mod] = leftSum;
leftStarts[mod] = i;
}
}
int crossMaxSum = int.MinValue;
int crossMaxStart = -1;
int crossMaxEnd = -1;
if (rightEnds[0] != -1)
{
crossMaxSum = r[0];
crossMaxStart = mid - 1;
crossMaxEnd = rightEnds[0];
if (leftStarts[0] != -1)
{
int crossSum = l[0] + r[0];
if (crossSum > crossMaxSum)
{
crossMaxSum = crossSum;
crossMaxStart = leftStarts[0];
crossMaxEnd = rightEnds[0];
}
}
}
for (int i = 1; i < k; ++i)
{
int crossSum = l[i] + r[k-i];
if (crossSum > crossMaxSum)
{
crossMaxSum = crossSum;
crossMaxStart = leftStarts[i];
crossMaxEnd = rightEnds[k-i];
}
}
if (crossMaxStart != -1)
{
if (leftMaxStart != -1)
{
if (rightMaxStart != -1)
{
if (leftMaxSum >= rightMaxSum && leftMaxSum >= crossMaxSum)
{
maxStart = leftMaxStart;
maxEnd = leftMaxEnd;
sum = leftMaxSum;
}
else if (crossMaxSum >= leftMaxSum && crossMaxSum >= rightMaxSum)
{
maxStart = crossMaxStart;
maxEnd = crossMaxEnd;
sum = crossMaxSum;
}
else
{
maxStart = rightMaxStart;
maxEnd = rightMaxEnd;
sum = rightMaxSum;
}
}
else
{
if (leftMaxSum >= crossMaxSum)
{
maxStart = leftMaxStart;
maxEnd = leftMaxEnd;
sum = leftMaxSum;
}
else
{
maxStart = crossMaxStart;
maxEnd = crossMaxEnd;
sum = crossMaxSum;
}
}
}
else
{
if (rightMaxStart != -1)
{
if (rightMaxSum >= crossMaxSum)
{
maxStart = rightMaxStart;
maxEnd = rightMaxEnd;
sum = rightMaxSum;
}
else
{
maxStart = crossMaxStart;
maxEnd = crossMaxEnd;
sum = crossMaxSum;
}
}
else
{
maxStart = crossMaxStart;
maxEnd = crossMaxEnd;
sum = crossMaxSum;
}
}
}
else
{
if (leftMaxStart != -1)
{
if (rightMaxStart != -1)
{
if (leftMaxSum >= rightMaxSum)
{
maxStart = leftMaxStart;
maxEnd = leftMaxEnd;
sum = leftMaxSum;
}
else
{
maxStart = rightMaxStart;
maxEnd = rightMaxEnd;
sum = rightMaxSum;
}
}
else
{
maxStart = leftMaxStart;
maxEnd = leftMaxEnd;
sum = leftMaxSum;
}
}
else
{
if (rightMaxStart != -1)
{
maxStart = rightMaxStart;
maxEnd = rightMaxEnd;
sum = rightMaxSum;
}
else
{
maxStart = -1;
maxEnd = -1;
sum = 0;
}
}
}
}
}
}
}
0
votes
at first i too thinked about using prefixes (which have been already mentioned)
but...i think there is a more simple way:
before i describe the given problem i solve a simpler(i expect negative numbers in the input):
find the subarray in a vector having the maximal sum:
min_sum=0
max_sum=0
sum=0
for x in elements{
sum+=x
if sum < min_sum { min_sum=sum }
if sum > max_sum { max_sum=sum }
}
result=max_sum-min_sum
i will do this for all k classes during a single pass
min_sum= [ array, k zeros]
max_sum= [ array, k zeros]
sum=0
for x in elements{
sum+=x
s = sum % k // current numberclass
if sum < min_sum[s] { min_sum[s]=sum }
if sum > max_sum[s] { max_sum[s]=sum }
}
mx=0
for x in [0:k){
s=max_sum[x]-min_sum[x]
if(mx<s) mx=s
}
result is in mx
complexity O(n+k)
{3,2,2,3}andk=4. How would you check divisibility ? – Bond