Site Message

Only Premium Users can view the Question

Question: Amazon ML Summer School, Online Assessment Questions | Minimum Cost to reach the Destination | Mean Median and Mode | 2023
1
Entering edit mode

ADD COMMENTlink 22 months ago Delta 3.0k
0
Entering edit mode

Problem Editorial: Minimum Cost to Reach the Destination
Logic and Approach:

We treat the problem as a Dynamic Programming problem with:

  • States defined by the current city (index).

  • Transitions defined by allowed jumps: i → i+1 and i → i+3.

  • The cost is the sum of differences in ticket costs at each step.


💡 Recursive DP with Memoization:

  1. Base Case:
    If we're at the last city (i == n-1), the cost to reach the destination is 0.

  2. Memoization:
    If the answer from city i is already computed (dp[i] != -1), return that to avoid recomputation.

  3. Recursive Transitions:

    • Try jumping to i+1 and add the transition cost.

    • Try jumping to i+3 if within bounds.

    • Take the minimum of both paths.

Code:

#include<bits/stdc++.h>

using  namespace std;



int solve(int i,vector<int> &arr,vector<int> &dp){

    if (i == arr.size()-1 ){
        return 0;
    }
    if(dp[i] != -1) return dp[i];
    int ans = INT_MAX;

    if (i+1 < arr.size()){
        ans = min(ans,abs(arr[i+1]-arr[i]) + solve(i+1,arr,dp));
    }
    if (i+3 < arr.size()){
        ans = min(ans,abs(arr[i+3]-arr[i]) + solve(i+3,arr,dp));
    }
    return dp[i]=ans;
}

int main(){


    int n;
    cin >> n;

    vector<int> arr(n);
    for(int i = 0 ; i < n;i++){
        cin >> arr[i] ;
    }
    vector<int> dp(n+1,-1);
    cout << solve(0,arr,dp) << endl;

}

Time and Space Complexity:

  • Time Complexity:
    O(N), because each state (city index) is computed only once.

  • Space Complexity:
    O(N), for the dp array and recursion stack.

ADD COMMENTlink 11 days ago Suryansh Rishit • 0
0
Entering edit mode

Problem Editorial: Mean, Median and Mode

Approach:

  1. Mean: Just accumulate the sum and divide by n.

  2. Median: Sort the array.

    • If odd, take middle element.

    • If even, average of two center elements.

  3. Mode: Use a map<int, int> to count frequencies. Track:

    • Max frequency.

    • Smallest number with max frequency.

Code:

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

vector<double> findMeanMedianMode(int n, vector<int> &arr) {
    double sum = 0.0;
    map<int, int> freq;

    for (int i = 0; i < n; i++) {
        sum += arr[i];
        freq[arr[i]]++;
    }

    double mean = sum / n;

    sort(arr.begin(), arr.end());

    double median;
    if (n % 2 == 1) {
        median = arr[n / 2];
    } else {
        median = (arr[n / 2] + arr[n / 2 - 1]) / 2.0;
    }

    int mode = arr[0];
    int maxFreq = 0;

    for (auto &p : freq) {
        if (p.second > maxFreq || (p.second == maxFreq && p.first < mode)) {
            maxFreq = p.second;
            mode = p.first;
        }
    }

    return {mean, median, static_cast<double>(mode)};
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    vector<double> res = findMeanMedianMode(n, arr);

    cout << fixed << setprecision(6);
    cout << res[0] << ", " << res[1] << ", " << (int)res[2] << endl;

    return 0;
}

Time Complexity:

  • The sorting step takes O(n log n) time.

  • Calculating the sum and building the frequency map takes O(n) time.

  • Scanning the map to find the mode also takes O(n) time.

Since O(n log n) dominates, the overall time complexity is:

O(n log n)


Space Complexity:

  • You use extra space for:

    • The input array → O(n)

    • The frequency map → O(n) (in the worst case, when all elements are unique)

So, the total space complexity is:

O(n)

ADD COMMENTlink 11 days ago Suryansh Rishit • 0

Login before adding your answer.

APPLY NOWSimilar Posts
Loading Similar Posts