DP
Problem
Submissions
Hints & solutions
Discuss
Subsequences of length K
Hard
0/120
Average time to solve is 50m
Contributed by
0 upvote
Problem statement
You are provided with an array of integers having length ‘N’. All you have to do is to find the number of subsequences of length ‘K’ such that for a particular subsequence Sq[i+1] - Sq[i] should be constant for that complete subsequence.
For Example :‘ARR’ = [1, 3, 8, 5, 13]
‘K’ = 3
Here, the required subsequences are:
[1, 3, 5] => 3 - 1 = 5 - 3 = 2 (constant throughout the subsequence)
[3, 8, 13] => 8 - 3 = 13 - 8 = 5 (constant throughout the subsequence)
Hence, the final answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case has two single space-separated integers ‘N’ and ‘K’ representing the length of the array ‘ARR’ and the integer ‘K’ as per the description, respectively.
The second line of each test case has the ‘N’ single space-separated integers representing the elements of the array ‘ARR’.
For each test case, print a single integer representing the total number of subsequences as per the given conditions in the description.
You don't need to print the output, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N, K <= 50
0 <= ARR[i] <= 50
Time Limit: 1 sec
Sample Input 1:
1
5 3
1 3 8 5 13
Sample Output 1:
2
Explanation For Sample Input 1:
For the first test case, the explanation is given in the description.
Sample Input 2:
2
2 2
0 2
2 4
0 10
Sample Output 2:
1
0
Hint
Hint 1
Hint 2
Hint 3
Can you think of finding the solution using the concept of the Longest Airthematic Subsequence?
Approaches (3)
Approach 1
Approach 2
Approach 3
Brute Force
The basic idea here is to find the Airthematic subsequences of length ‘K’ as if Sq[i+1] - Sq[i] is constant for the complete subsequence then it means the subsequence is arithmetic in nature.
Prerequisite:
https://www.codingninjas.com/codestudio/problems/longest-ap_1235209?leftPanelTab=0
The steps are as follows:
- Check the corner cases, if ‘K’ = 1 return ‘N’ or ‘N’ = 1, return 0.
- Declare a variable to store the required result, say ‘ANSWER’.
- Run a loop from ‘i’ = 0 to ‘N’ . Here ‘N’ is the length of the array.
- Run a loop from ‘j’ = ‘i’ + 1 to ‘N’.
- Call ‘findAP’ function to get the required subsequences starting at index ‘i’ and have a common difference as ‘ARR[j]' – 'ARR[i]’.
- Return the ‘ANSWER’.
Description of ‘findAP’ function:
This function will take six parameters :
- ‘INDEX’: An integer to keep track of the current index of the array.
- ‘DIFFERENCE’: An integer denoting the current common difference of subsequence.
- ‘ARR’: An array ‘ARR’ is given in the problem.
- ‘CUR’: Current length of subsequence having the difference ‘DIFFERENCE’.
- ‘K’: The required length of subsequences.
- ‘ANSWER’: Variable to store the final answer.
void findAP('INDEX', ‘DIFFERENCE’, ‘ARR’, ‘CUR’, ‘K’, ‘ANSWER’):
- If 'INDEX' >= size of the array then return 0 as we have reached the end of the subsequence.
- Check if ‘CUR’ is equal to the ‘K’ then increment ‘ANSWER’ by 1.
- Run a loop from 'INDEX' + 1 to the size of the array
- If ‘ARR’[i] – ‘ARR’['INDEX'] is equal to the index that shows we have found a valid next term of our current AP. So recursively call ‘findAP(i, ‘DIFFERENCE', ‘ARR’, ‘CUR’ + 1, ‘K’, ‘ANSWER’)’.
Time Complexity
O(N ^ N), where ‘N’ is the total number of elements in the array ‘ARR’.
Since we need to check all possible differences and our ‘findAP’ function takes O(N ^ N) time as at each step we are making O(N) recursive calls. Thus the time complexity will be O(N ^ N).
Space Complexity
O(N), where ‘N’ is the total number of elements in the array.
Since our ‘findAP’ function requires O(N) space in the form of recursive stack space. Thus the space complexity will be O(N).
Code Solution
(100% EXP penalty)
Subsequences of length K
All tags
Sort by
C++ (g++ 5.4)
Console