#### Am i assuming right value of sum in each recursion?

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