A subarray is a continuous part of an array. In other-words, a subarray is an array that is inside another array.

In general, for an array of size n, there are n*(n+1)/2 non-empty subarrays.

For example, in the array [1, 2, 3, 4], there are 10 non-empty sub-arrays, which are:

[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], and [1,2,3,4]

Two Pointers Technique

Two pointers refer to left (i) and right (j) indexes, such that left points to the start of the array and right points to the end of the array, initially. The opposite pointers move towards the center of the array during iterations, until a condition is met.

A Sliding Window

A sliding window is a sub-array that moves from one end of the array to the other end, one element at a time. The left end of the window is typically identified by the variable, i or left or back. The right end of the window is typically identified by the variable, j or right or front.

As the window moves, its size (length) may be fixed or variable. This module of the full course deals only with fixed size windows. With fixed size window, the size of the last window can be less than the size of each of the previous windows.

The sliding window is a specialized application of the two-pointers technique.

Problem

Given an array A[] containing N elements, the task is to divide the array into K subarrays, such that the sum of elements of each subarray is odd. Print the starting index (1 based indexing) of each subarray after dividing the array, and -1 if no such subarray exists.

Note: For all subarrays S1, S2, S3, ..., SK:
- The intersection of S1, S2, S3, ..., SK should be NULL.
- The union of S1, S2, S3, ..., SK should be equal to the array.

Examples:

Input: N = 5
A[] = {7, 2, 11, 4, 19}
K = 3
Output: 1 3 5
Explanation: When the given array A[] is divided into K = 3 parts, the possible subarrays are: {7, 2}, {11, 4} and {19}, leading to the array start indexes of 1, 3, 5 (zero based index plus 1).

Input: N = 5
A[] = {2, 4, 6, 8, 10}
K = 3
Output: -1
Explanation: It is impossible to divide the array A[] into K = 3 subarrays as all the elements are even and the sum of every subarray is even.

Assume that K is not greater than N.

Clarification

k here is not the size of each window (sub-array). To obtain the size of each window, do integer division by k, and modulus division by k, from N, then round up or down as explained below. Integer division accepts the whole number part of the quotient and abandons the remainder of the quotient. Modulus division accepts the remainder part of the quotient and abandons the whole number part of the quotient.

The start index of a subarray returned, should be the zero-based index in the whole array, plus 1 .

Strategy

Let m be the fixed size of each subarray (window).

    m = N / k    //integer division

    remainder = N % k

If remainder is equal to or greater than half of m from integer division, then m becomes m+1. If remainder is less than half of m from integer division, then m remains m from integer division. The comparison here has to be done by float (double) numbers, so convert m and remainder to float (double). Allow N and k as integers. See details in the program below.

To determine if the sum of a subarray is odd, divide the sum by 2. This has to be modulus division. That is:

    remainder = sum % 2

If the remainder is 0, then the sum of the subarray is even, If the remainder is 1, then the sum of the subarray is odd.

Since the subarrays are disjoint, there is no need to attempt the brute-force approach. Just use sliding window, though in this occasion, the sliding window skips along, in the array by m intervals. That is, the window (subarray) is a skipping window, not really a sliding window.

Since the window is a skipping window of intervals m (disjoint subarrays), to obtain the sum of a window, just iterate over the window, adding the numbers. That will lead to O(n) time for the whole algorithm, and array scan.

Efficient Solution in O(n) Time

The program for the efficient solution is as follows. Read through the code and comments and note the incremental expression, "i=i+m" in the second for-loop parentheses, and also note the while condition, "j<m && (i+j) < n" in the nested for-loop parentheses.

#include <stdio.h>
#include <stdbool.h>

void split(int A[], int n, int k){
    //fixed size width
    int m = n / k;    //integer division
    int rem = n % k;
    double mInt = m;
    double remInt = rem;
    if (remInt >= mInt/2)
        m = m + 1;
    else
        m = m;

    //the first k sum
    int sum = 0;
    for (int i = 0; i < m; i++)
        sum = sum + A[i];    
    if (sum%2 == 1)    //if sum of first window is odd.
        printf("%i, ", 0+1);    //0 based index to 1 based index

    // Address sums of remaining windows
    bool aSubArrExist = false;
    for (int i = m; i < n; i=i+m) {    //intervals with skip of m
        int sum = 0;
        for (int j=0; j<m && (i+j) < n; j++) {
            sum = sum + A[i+j];
        }
        if (sum%2 == 1) { 
            printf("%i, ", i+1);    //0 based index to 1 based index
            aSubArrExist = true;
        }
    }
    if (aSubArrExist == false)
        printf("-1");
    
    printf("\n");
}

int main(int argc, char **argv) {
    int A[] = {7, 2, 11, 4, 19};
    int k = 3;
    int n = sizeof(A) / sizeof(A[0]);
    
    split(A, n, k);
    
    
    int A2[] = {2, 4, 6, 8, 10};
    int k2 = 3;
    int n2 = sizeof(A2) / sizeof(A2[0]);
    
    split(A2, n2, k2);
        
    return 0;
}

The output is:

    1, 3, 5, 
    -1

The time complexity is O(n): within m all the numbers are added one-by-one, m intervals are skipped. Summing all the m's gives O(n) time, for the whole array. The space complexity is O(n) because the array in the calling function is the same as the array in the called function.

Thanks for reading.