Given an array, print all possible contiguous subsequences whose sum is divisible by a given number x

Question

Given an array, print all possible contiguous subsequences whose sum is divisible by a given number x.

I can see some related question :- [Find numbers of subarray of an array whose sum is divided by given number

[how to find the length of the longest contiguous subarray whose sum is divisible by a given number

All ask to either print the largest array or length of largest array. I want to print all combinations of those contiguous array with are divisible by a given number. I tried to9 solve this and came up with this solution

#include<iostream>
using namespace std;

void function(int arr[], int start, int end, int div, int sum)
{
    if(start>end)
        return;
    if(!(sum%div))
    {
        if(start<end)
        {
            for(int i=start;i<=end;i++)
            {
                cout<<"  "<<arr[i];
            }
            cout<<endl;
        }
    }
    function(arr, start+1, end, div, sum-arr[start]);
    function(arr, start, end-1, div, sum-arr[end]);
}

int main()
{
    int arr[] = {2, 6, 3, 8, 5, 7, 4, 1};
    int div;
    int size = sizeof(arr)/sizeof(*arr);
    cout<<"  Enter divisor :- ";
    cin>>div;
    int sum = 0;
    for(int i=0;i<size;i++)
        sum+=arr[i];
    function(arr, 0, size-1, div, sum);

    cout<<endl;
    system("PAUSE");
    return 0;
}

This code has HORRIBLE complexity, i can think of one more solution using two loops with complexity O(n^2). Can we do this in better that n^2 time complexity?

I don't understand. Do you want the largest array, the length of the largest array, all the subarrays or the count of subarrays? Because if you want all the subarrays (not only the count) there is no better solution than O(n^2) because there can be at most O(n^2) subarrays (think of an input array full of even numbers and x=2). — Juan Lopes
@JuanLopes , yeah i need all the possible combination of subarrays, fulfilling the given condition. — instance
So there is no better solution than O(n^2) as the result itself has O(n^2) items. — Juan Lopes
Actually, as every subarray has O(n) elements, there is no algorithm better than O(n^3). — Juan Lopes
(which is why we usually switch to output-sensitive bounds here; there's a difference between O(n + s) where s is the size of the output, which is achievable here, and straight-up O(n^3)). — David Eisenstat

noman pouigt noman pouigt · Accepted Answer · 2015-08-13T19:56:09

I assume you would have read the answer Find numbers of subarray of an array whose sum is divided by given number .

If yes, then you can modify the aforementioned algorithm as below:

Input:    0  5  3  8  2  1
X = 3
Sum:   0  0  5  8 16 18 19
Mod 3: 0  0  2  2  1  0  1

All you need to do is to print the array whenever you see same value in "mod 3" output array. So in the above case you will print array from index [0], [2], [0, 4], [1, 4] and [4 ,5].

0  5  3  8  2  1
-                     0                 =  0 % 3 = 0
-------------         0 + 5 + 3 + 8 + 2 = 18 % 3 = 0
   ----------         5 + 3 + 8 + 2     = 18 % 3 = 0
      -               3                 =  3 % 3 = 0
            ----      2 + 1             =  3 % 3 = 0

Given an array, print all possible contiguous subsequences whose sum is divisible by a given number x

1 Answers