Quiz 10

Problem Statement:

Yesterday was a very auspicious day for Raphael: guess what, he got engaged with the love of his life, Haruka. He was on the ninth cloud, planning out his future! Since his fiancée is a very needy girl, he plans on giving her presents periodically. However, his schedule is quite random, and his sources of income sporadic. So he can only prepare these presents at some specific points of time into the future.

Raphael knows that in the next few years, he will be able to buy presents n times, and he can buy them at times a[0], a[1], ... , a[n-1]. These numbers are not sorted in order. Every present has a duration value, which specifies how long a present can keep Haruka happy without having to get the next present. He will also prepare an additional present today.

Being head over heels for Haruka, Raphael wants to always keep her happy. He needs your help to find the maximum duration of a present that he should prepare so that she is kept happy for the next few years.

Raphael wants you to write a program that does the following: it asks him to enter the value of n, followed by a[0], a[1], ... , a[n-1], which are the times (in months from today's date) when he can prepare a present. These numbers are not necessarily sorted. The program then prints out the largest duration of a present that he needs to prepare.

Sample Run:

Enter the number of presents (excluding the one today): 5
Enter the times when you can prepare the presents: 10 3 12 7 17
The largest duration required is: 5 months

Explanation: Raphael can prepare presents today, and on the 3rd, 7th, 10th, 12th, and 17th months from now. The required duration of the first present is 3 months, the second is 4 months, the third is 3 months, the fourth is 2 months, and the fifth is 5 months. Thus the present with the biggest duration that he needs to prepare, needs to last for 5 months.

Sample Run 2:

Enter the number of presents (excluding the one today): 6
Enter the times when you can prepare the presents: 9 3 8 5 12 18
The largest duration required is: 6 months

Explanation: Raphael can prepare presents today, and on the 3rd, 5th, 8th, 9th, 12th and 18th months from now. The required duration of the first present is 3 months, the second is 2 months, the third is 3 month, the fourth is 1 month, the fifth is 3 months, and the sixth is 6 months. Thus the present with the biggest duration that he needs to prepare, needs to last for 6 months.

Solution

First, given the array a[0],...,a[n-1], we need to sort it so that we now have the times of the presents in order. Next, we need to find max{a[0],a[1]-a[0],a[2]-a[1],...,a[n-1]-a[n-2]}, and this number is what we are searching for!

Let's begin coding!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cout << "Enter the number of presents (excluding the one today): ";
    cin >> n;
    vector<int> a;
    cout << "Enter the the times when you can prepare the presents: ";
    for (int i = 0; i < n; i++) {
        int month;
        cin >> month;
        a.push_back(month);
    }
	
    sort(a.begin(),a.end()); // C++11 sort function, sorts everything from a.begin() to a.end().
	// For arrays, you can call it as sort(a,a+n)
	
	//Find max{a[0],a[1]-a[0],a[2]-a[1],...,a[n-1]-a[n-2]}
    int max = a[0];
    for (int i = 1; i < n; i++) {
        if (max < a[i] - a[i - 1])
            max = a[i] - a[i - 1];
    }

    cout << "The largest duration required is: "<< max << " months." << endl;
    return 0;
}