Split Array Into K Subarrays

Easy
0/40
Average time to solve is 25m
profile
Contributed by
5 upvotes
Asked in company
Adobe

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
6 1 3
6 1 3 3 3 3
6 2 3
3 5 3 5 3 1
Sample Output 1:
1
0
Explanation For Sample Output 1:
In test case 1:

Here for this test case for the given test cases K consecutive 
non-overlapping subarrays are {6}, {1}, {3}}. hence the answer is 
1.

In test case 2:

For this test case, there is no possible way to divide the array, 
So the answer is 0.
Sample Input 2:
2
5 3 2
4 3 5 2 5
5 1 2
3 2 2 2 2
Sample Output 2:
0
1
Hint

Try iterating and simultaneously checking for consecutive subarrays of length ‘M’.

Approaches (1)
Array Traversal.

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.
Time Complexity

O(N) where ‘N’ is the number of elements in an array.

 

Here we are iterating over all ‘N’ the elements of an array so that it will take ‘N’ steps, and hence time complexity will be O(N)

Space Complexity

O(1) 

 

Constant extra space is used.

Code Solution
(100% EXP penalty)
Split Array Into K Subarrays
Full screen
Console