Last Updated: 25 Jun, 2021

Split Array Into K Subarrays

Easy

Asked in company

Solve now

Problem statement

You have given an integer array ‘arr’ size ‘N’. You have to split the array into ‘K’ consecutive non-overlapping subarrays of length ‘M’ such that every subarray contains a single distinct element.

You are required to check if it is possible to split the array with the above condition and print the answer in the binary format 1 if it is possible or 0 if it is not possible to split the array.

For Example:

Input:
N = 4 
M = 1 
K = 3
A[] = {5, 4, 1, 1}

Output 
1

The given array can be split like this [5], [4], [1] there are three consecutive non-overlapping subarrays.

Input Format:

The first line contains a single integer 'T' denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains three space-separated integers ‘N’, ‘M’, and ‘K’, where  ‘N’ denotes the size of the array, ‘M’ denotes the size of subarray required and ‘K’ denotes the number of subarrays required.

The second line of each test case contains ‘N’ space - separated 
integers denoting the elements of the given array.

Output Format:

For each test case, print an integer  0 or 1. 1 if it is possible to split the array or 0 if it is not possible.

Output for each test case will be printed in a separate line.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints:

1 <= T <= 50
1 <= N, M, K <= 100000
1 <= A[i] <= 100000

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

We will be solving this problem using a simple array traversal. At each position, we will check if the element at the current index i and (i + M) are the same or not. Moreover, if it is the same, then we will increment the counter, and as soon as our counter becomes equal to K, it means the array can be split, and we will return the answer at that step. If, after all, iterations are still if the count is not equal to K, it means the array can not be split.

Algorithm

Initialize two variables, ‘CTR’ and ‘T’, with 1 and 0 respectively, ‘CTR’ will store the total count of pattern matched, and ‘T’ will store the current length of pattern matching.
Iterate on the input array on the range [0, 'N' – ‘M’ – 1].
- if arr[i] == arr[i + ‘M’] then increase ‘T’ by 1. if ‘T’ is the same as ‘M’, then make ‘T’ = 0 and increase ‘CTR’ by 1 and if ‘CTR’ == ‘K’ then return 1.
Else, if ‘T’ is ‘M’, then increase the ‘CTR’ by 1.
After the above steps, if the value of ‘CTR’ is not the same as ‘K’, then return 0.

Solve now