974. Subarray Sums Divisible by K

Given an integer array nums and an integer k, I want to return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

To efficiently find the sum of a contiguous subarray, we first calculate the sum of the entire array. If this total sum modulo kkk equals 0, we increment a counter. Next, we recursively determine the sum of subarrays.

What is a subarray?

A subarray is a contiguous part of an array defined by a starting index (low) and an ending index (high). To generate subarrays, we adjust the low and high indices:

1. Subtract from low

2. Subtract from high

3. Subtract from both low and high simultaneously

For each resulting subarray, we perform the same operations recursively to find and count those subarrays whose sums modulo k equals 0.

Code:

class Solution {
    int subarrayfunc(vector<int>nums,int low,int high,int k,int sum){
        if(low<=high){
            if(sum%k==0){
                return 1+subarrayfunc(nums,low,high-1,k,sum-nums[high])+subarrayfunc(nums,low+1,high,k,sum-nums[low])+subarrayfunc(nums,low+1,high-1,k,sum-nums[high]-nums[low]);
            }
            else{
                return subarrayfunc(nums,low,high-1,k,sum-nums[high])+subarrayfunc(nums,low+1,high,k,sum-nums[low])+subarrayfunc(nums,low+1,high-1,k,sum-nums[high]-nums[low]);
            }
        }
        return 0;
    }
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int sum=0;

        for(int i=0;i<nums.size();i++){
            sum=sum+nums[i];
        }

        return subarrayfunc(nums,0,nums.size()-1,k,sum);
    }
};

OUTPUT:

Input

nums =

[4,5,0,-2,-3,1]

k =

5

Output

57

Expected

7

Time of implementation , getting wrong answer