Only Premium Users can view the Question
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.
Base Case:
If we're at the last city (i == n-1
), the cost to reach the destination is 0
.
Memoization:
If the answer from city i
is already computed (dp[i] != -1
), return that to avoid recomputation.
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.
#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 Complexity:
O(N), because each state (city index) is computed only once.
Space Complexity:
O(N), for the dp
array and recursion stack.
Mean: Just accumulate the sum and divide by n
.
Median: Sort the array.
If odd, take middle element.
If even, average of two center elements.
Mode: Use a map<int, int>
to count frequencies. Track:
Max frequency.
Smallest number with max frequency.
#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;
}
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)
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)