Trees Height Solution Amazon OA SDE 2023

Trees Height Solution Amazon OA 2023 SDE

There are N trees in Jon’s backyard and height of tree i is h[i]. Jon doesn’t like the appearance of it and is planning to increase and decrease the height of trees such that the new heights are in strictly increasing order. Every day he can pick one tree and increase or decrease the height by 1 unit. Heights can be 0 or even negative (it’s a magical world).

Jon has guests coming after X days, hence he wants to know if it is possible to make heights strictly increasing in no more than X days?

Input format:

First line contains one integer N<=2000 number of trees, X<=5000 number of days Jon has.
Second line contains N space separated integers where ith integer is h[i]

Output Format:

YES or NO, if it is possible to make tree heights in strictly ascending order in no more than X days, if YES, also print the number of days it will take.

Sample Input 1:

5 13
5 4 3 2 1

Sample Output 1:

YES 12

Explanation:

For the first sample the final array will look like 1 2 3 4 5
Hence the number of days required will be 12.

Sample Input 2:

7 10
7 1 4 10 5 8 12

Sample Output 2:

NO

Trees Height Solution Amazon OA SDE
Trees Height Solution Amazon OA SDE

SOLUTION

Program: Trees Height Solution in C++

We read in the number of trees n and the number of days Jon has x, and the heights of the trees into a vector h.

We then iterate through the heights of the trees from the second tree to the last tree, checking if each height is greater than the previous height. If it’s not, we need to make adjustments to the height of the current tree.

To make the current height strictly increasing, we need to increase it by at least 1 unit above the previous height. The number of days needed to do this is equal to the difference between the previous height and the current height, plus 1. If the remaining number of days is less than the number of days needed to make the height strictly increasing, we can’t do it and we output “NO”.

Otherwise, we subtract the number of days needed from the remaining days, and add the number of days needed to the total number of days.

If we’ve made it through all the trees and we still have remaining days, we output “YES” followed by the total number of days needed to make the heights strictly increasing.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    int days = 0;
    for (int i = 1; i < n; i++) {
        // if the current height is greater than or equal to the previous height, we need to make adjustments
        if (h[i] <= h[i-1]) {
            // calculate the difference between the current height and the previous height, and add 1 to get the number of days needed to make them strictly increasing
            int diff = h[i-1] - h[i] + 1;
            // if the remaining number of days is less than the number of days needed to make them strictly increasing, we can't do it
            if (x < diff) {
                cout << "NO" << endl;
                return 0;
            }
            // otherwise, subtract the number of days needed from the remaining days
            x -= diff;
            // add the number of days needed to the total number of days
            days += diff;
        }
    }
    // if we've made it this far, we can make the heights strictly increasing in the remaining number of days
    cout << "YES " << days << endl;
    return 0;
}

Program: Trees Height Solution in Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
        }
        System.out.println(solve(h, x));
    }
    
    public static String solve(int[] h, int x) {
        int n = h.length;
        int minn = Arrays.stream(h).min().getAsInt();
        for (int i = 0; i < n; i++) {
            h[i] -= minn;
        }
        int maxn = Arrays.stream(h).max().getAsInt() + 1;
        
        int[] dp = new int[maxn];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = h[i]; j >= 0; j--) {
                dp[j + 1] = Math.min(dp[j + 1], dp[j] + 1);
            }
        }
        
        int ans = Arrays.stream(dp).min().getAsInt();
        return ans <= x ? "YES " + ans : "NO";
    }
}

Program: Trees Height Solution in Python

The solve function takes two arguments: nums, a list of integers representing the heights of the trees, and X, an integer representing the maximum number of days Jon has to make the trees strictly increasing. The function returns a string, either “YES” followed by the number of days it will take to make the trees strictly increasing in no more than X days, or “NO” if it is not possible to do so.

The function first subtracts the minimum value in the list nums from each element of nums to make it easier to work with. Then it initializes a 1D list dp of length maxn (where maxn is the maximum value in nums plus 1) to infinity, and sets the base case dp[j] = abs(nums[0]-j) for all j in the range [0, maxn). This represents the minimum number of operations required to make the first tree’s height equal to j.

The function then iterates over the remaining trees, updating dp for each tree. For each tree i, it sets min_so_far to the minimum value of dp[:i], and then iterates over the range [i, maxn) to compute the minimum number of operations required to make the height of the ith tree equal to j. This is given by the recurrence relation dp[j] = abs(nums[i]-j) + min_so_far. Finally, min_so_far is updated to the minimum value of dp[j] encountered so far.

After iterating over all the trees, the function returns “YES” followed by the minimum value of dp if it is less than or equal to X, and “NO” otherwise.

def solve(nums, X):
    N = len(nums)
    minn = min(nums)
    # Observe that making any element of our array less than the minimum or more than maximum would result in extra useless operation, hence j can be in the range of [min(nums), max(nums)], both inclusive. Here we can subtract min values from each element in array just to make the code more readable
    for i in range(len(nums)):
        nums[i] -= minn
    maxn = max(nums) + 1 
    
    # dp[i][j] is the minimum number of operations required to make nums[:i+1](till ith index) strictly sorted with nums[i] == j.
    # Hence, our recurrence relation would be: dp[i][j] = abs(nums[i]-j) + min(dp[i-1][:j])
    # This 2D table can be easily converted to 1D dp[j], since we only ever need to know the i-1th state for computing ith state.
    dp = [float('inf')]*(maxn)
    # Initialize base case
    for j in range(maxn):
        dp[j] = abs(nums[0]-j)
    
    for i in range(1, len(nums)):
        min_so_far = min(dp[:i])
        for j in range(i, maxn): # starting from i to ensure strictly increasing order
            dp[j] = abs(nums[i]-j) + min_so_far
            min_so_far = min(min_so_far, dp[j])
    return "YES " + str(min(dp)) if min(dp) <= X else "NO"
    
n,m=map(int,input().split())
l=list(map(int,input().split()))
print(solve(l,m))

Amazon OA 2023 Questions with Solution

  1. Shopping Patterns Solution Amazon OA 2023
  2. Reorder Data in Log Files Solution Amazon OA 2023
  3. Top K Frequent Words Solution Amazon OA 2023
  4. Counting Binary Substrings Amazon OA 2023
  5. Grid Connections Amazon OA 2023
  6. Shipment Imbalance Amazon OA 2023
  7. Max Profit Amazon OA 2023
  8. Find Lowest Price Amazon OA 2023
  9. Decode String Frequency Amazon OA 2023
  10. Simple Cipher Amazon OA 2023
  11. Valid Discount Coupons Amazon OA 2023 Solution
  12. Count Maximum Teams Amazon OA 2023
  13. Minimum Coin Flips Amazon OA 2023
  14. Max Average Stock Price Amazon OA 2023 Solution
  15. Robot Bounded In Circle Amazon OA 2023
  16. Shopping Options Amazon OA 2023 Solution
  17. Fill The Truck Maximum Units on a Truck Amazon OA Solution
  18. Maximize Score After N Operations Number Game Solution Amazon OA 2023
  19. Slowest Key Amazon OA 2023 Solution
  20. Five Star Seller Maximum Average Pass Ratio Amazon OA 2023
  21. Split String Into Unique Primes Amazon OA 2023 Solution
  22. Storage Optimization Amazon OA 2023 Solution
  23. Minimum Difficulty of a Job Schedule Amazon OA 2023 Solution
  24. Autoscale Policy Utilization Check Amazon OA 2023
  25. Optimal Utilization Solution Amazon OA 2023
  26. Merge Two Sorted Lists Solution Amazon OA 2023
  27. Two Sum Unique Pairs Solution Amazon OA 2023
  28. Amazon Music Pairs Amazon OA 2023 Solution
  29. Class Grouping Amazon OA 2023 Solution
  30. Find Max products Amazon OA 2023 Solution
  31. Get encrypted number Amazon OA 2023 Solution
  32. Find Total Imbalance Amazon OA 2023 Solution
  33. Find Total Power Amazon OA 2023 Solution

4 thoughts on “Trees Height Solution Amazon OA SDE 2023”

    • Input must be in this format n: The number of Trees; m: The number of Days
      As per your shared info
      5
      1 2 2 2 3

      It’s not a correct format as it’s missing m: number of Days.

      If their is any other issues with the solution do let us know, we will share new solution.

      Reply

Leave a Comment

17 + nine =