1

The general problem: Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays.

My question: I want to solve this problem recursively. The part I'm struggling to implement is how do I use the count from every previous recursive call and sum up all the counts, and return one last count like it is shown in the attempt.

Example:

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

My attempt:

int helperFunction(vector<int> &nums, int k, int starter, int count)
{
    int sum=0;
    if (starter >= nums.size())
    {
        return count;
    }
    for (int i = starter; i < nums.size(); i++)
    {
        if (nums[i] % 2 == 1)
        {
            if (++sum == k)
            {
                count += nums.size() - i;
                sum = 0;
            }
        }
    }
    return helperFunction(nums, k, starter + 1, count);
}
int numberOfSubarrays(vector<int> &nums, int k)
{
    return helperFunction(nums, k, 0, 0);
}

int main()
{
    vector<int> mine;
    int myints[] = {1, 1, 2, 1, 1};

    mine.assign(myints, myints + 5);
    cout << "Output : " << numberOfSubarrays(mine, 3);
    return 0;
}

Return Value:

The return value of this actual attempt is 0 means the program is at least not wrong syntactically.

Improve this question
5
  • A perhaps-related question. What on earth is the purpose of sum if all you do is declare it as indeterminate, bump it once (to something just-as-indeterminate), compare it to k (which means all you're really doing is saying if (k == <something??>), conditionally resetting it to zero, then letting it scope expire anyway. That var seems utterly unnecessary. At a minimum to be proper, I would expect sum to be initialized, and if it was, it quickly becomes completely pointless. Commented Jan 30, 2022 at 6:50
  • 1
    The short answer is "you don't". This is not a recursive problem. Trying to do something recursively that's not a natural fit for a recursive solution will always end in tears. Commented Jan 30, 2022 at 6:50
  • @WhozCraig you're right, sum should be declared one block ahead. The point of sum is that once I get k condition checks I should start counting the sub-arrays, so if a the "minimal" sub-array M verifies it that means every sub-array in this form [M,...] verifies it without even checking Commented Jan 30, 2022 at 6:55
  • @SamVarshavchik Why do you think that? It is never good to use recursion if you're relying on values from previous recursion calls ? Commented Jan 30, 2022 at 6:57
  • No, it's just that it's never good to use recursion for problems that are not recursive problems. Commented Jan 30, 2022 at 6:59

1 Answer 1

Reset to default
1

it's not particularly good candidate for recursion. might be possible to solve with just one pass on the array.

That said, small adjustments to your code could make it work. There is no reason to pass count into the recursive method.

Your method calculates the number of subarrays that are 'nice' starting with the given index. Add that to the number that start at the next index and return it.

int helperFunction(vector<int> &nums, int k, int starter)
{
    int sum=0, count=0;
    if (starter >= nums.size())
    {
        return 0;
    }
    for (int i = starter; i < nums.size() && sum <= k; i++)
    {
        if (nums[i] % 2 == 1)
        {
            sum++;
        }
        if (sum == k)
        {
            count++;
        }        
    }
    return helperFunction(nums, k, starter + 1) + count;
}

I'm not sure your counting was correct. This could be optimized a lot, but this should demostrate the recursive approach.

Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

I was completely oblivious to this return helperFunction(...) + count . Thanks for your time. It is exactly what I needed
There is one very, very good reason to pass count as recursive argument: tail recursion.
@Dúthomhas Yes but it is extremely costly, the other guy in the comment made a fair statement...Also, I just wanted to use recursion to get more familiar with it, I wasn't intending to solve the problem the "best way"..
tail recursion efficiency would outweigh any other efficiency that could be gained. For efficiency, rewrite as a single pass on the array.
It’s worth noting a recursive function can easily reach max recursive depth, especially when you have an algorithm with large complexity. However, a nicely optimized tail recursive function can bypass the recursive depth as they can be treated more like an index-based for loop.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.