Google OA | SDE1 | CTC 60 LPA! | Hardest in 2023!

Question

Answer 1

After analyzing 78 OA problems asked in Google for SDE role in 2023; this is one of the most difficult and interesting one which involves DP at its core!

You are given an array A of N elements and an integer K. A subsequence is good if it is a non-decreasing subsequence and the sum of its elements at least K.

Find the minimum length of a good subsequence, or return -1 if there is no such subsequence.

Notes:

A subsequence of array A is a sequence that can be derived from array  A by deleting some or no elements without changing the order of the remaining elements.
. For example, [2, 4, 6] is a subsequence of [1, 2, 3, 4, 5, 6, 7] but [3, 4, 1] is not.

• A subsequence is non-decreasing if every element in the subsequence is greater or equal to its previous element.

• The length of the subsequence is the number of elements in it.

Input Format

The first line contains an integer, N. denoting the number of elements in A.

The next line contains an integer, K, denoting the minimum sum of the subsequence elements.

Each line i of the N subsequent lines (where 0<i<N) contains an integer scribing A[i].

1<=N<=500
1<=K<=100000000

Comments

Please share the segment tree approach

Answer 2

O(N*N*N) Approach: vector> dp(n+1, vector(n+1, -1)); for(int i = 0; i < n; i++){ dp[i][1] = nums[i]; } int ans = 1e9; for(int i = 0; i < n; i++){ for(int j = 0; j < i; j++){ if(nums[j] > nums[i]) continue; for(int k = 1; k < n; k++){ if(dp[j][k] != -1) { dp[i][k+1] = max(dp[i][k+1], nums[i] + dp[j][k]); if(dp[i][k+1] >= K){ ans = min(ans, k+1); } } } } }