CODEWITHSUNDEEP
arraysalgorithmdynamic-programming
instance
instance

Reputation: 1374

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

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?

Upvotes: 2

Views: 3712

Answers (1)

noman pouigt
noman pouigt

Reputation: 976

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

Upvotes: 1

Related Questions