Last Updated: 27 May, 2025

Largest Subsequence

Moderate

Asked in company

Solve now

Problem statement

You are given an array of integers 'A' of size 'N' and a maximum score 'M'.

The score of a subsequence [ A[i1-1], A[i2-1] ... A[ik-1] ] is defined as the sum of ( i * k + A[i-1] ) for each element in the subsequence, where 'i' is the 1-based index of the element in the original array 'A' and 'k' is the length of the subsequence.

Your task is to find the length of the largest subsequence whose score is less than or equal to 'M'.

For Example :

Let 'N' = 4, 'A' = [3, 5, 1, 2] and 'M' = 20.
Let's check if a subsequence of length k = 2 is possible. To minimize the score, we choose the elements that have the smallest contribution ( i * k + A[i-1] ).
The contributions for k = 2 are:
For index 1 (value 3): 1 * 2 + 3 = 5
For index 2 (value 5): 2 * 2 + 5 = 9
For index 3 (value 1): 3 * 2 + 1 = 7
For index 4 (value 2): 4 * 2 + 2 = 10
The two smallest contributions are 5 and 7. The minimum score for a subsequence of length 2 is 5 + 7 = 12.
Since 12 <= 20, a subsequence of length 2 is possible.
Let's check for k = 3. The contributions would be ( i * 3 + A[i-1] ). The sum of the three smallest contributions is (1*3+3) + (3*3+1) + (2*3+5) = 6 + 10 + 11 = 27.
Since 27 > 20, a subsequence of length 3 is not possible.
Therefore, the answer is 2.

Input Format :

The first line of input contains two space-separated integers, 'N' and 'M'.
The second line of input contains 'N' space-separated integers, representing the elements of array 'A'.

Output Format :

Return an integer representing the length of the largest subsequence whose score is less than or equal to 'M'.

Note :

You don’t need to print anything. Just implement the given function.

Constraints :

1 <= 'N' <= 10^5
1 <= 'M' <= 10^18
1 <= A[i] <= 10^9

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

The problem asks for the maximum possible length 'k'. This structure suggests that we can use binary search on the answer 'k', where 'k' ranges from 0 to 'N'.
For the binary search to work, we need a monotonic property. Let min_score(k) be the minimum possible score for a subsequence of length 'k'. If min_score(k) > M, then for any k' > k, it must be that min_score(k') > M. This is because both the number of terms in the sum and the value of each term (i * k + A[i-1]) increase with 'k'. This monotonic property allows us to binary search.
Our binary search will require a helper function, is_possible(k), that checks if a subsequence of length 'k' can have a score less than or equal to 'M'.
To implement is_possible(k):
- For a fixed 'k', the score is the sum of i * k + A[i-1] for 'k' chosen indices.
- To minimize the total score, we should choose the 'k' elements that have the smallest values of i * k + A[i-1].
- We can create a temporary array to store these N possible contribution values.
- Then, we find the sum of the smallest 'k' values in this temporary array.
- If this sum is less than or equal to 'M', is_possible(k) returns true; otherwise, it returns false.

Algorithm:

Initialize low = 0, high = N, and ans = 0.
Start a while loop that runs as long as low <= high.
- Calculate k = low + (high - low) / 2.
- If k == 0, continue the loop.
- Check if a subsequence of length 'k' is possible:
  - Create a temporary array, COSTS, of size 'N'.
  - For each index i from 1 to N, calculate COSTS[i-1] = A[i-1] + i * k.
  - Find the sum of the 'k' smallest elements in COSTS. This can be done efficiently in O(N) time using a selection algorithm (like nth_element). Let this sum be current_score.
- If current_score <= M:
  - A subsequence of length 'k' is valid. We store this as our potential answer and try for a larger length.
  - Set ans = k and low = k + 1.
- Else (current_score > M):
  - The length 'k' is too large. We need to try a smaller length.
  - Set high = k - 1.
Return ans.

Solve now