Problem of The Day 3 January — Candy Piles

Alice is celebrating the New Year with n piles of candies! Each pile i contains ci candies, and she defines her happiness factor as the minimum number of candies in any pile. As this is a special day, Alice wants to try to maximize her happiness factor by choosing exactly one pile and doubling the number of candies in it.

Find the following two values and print them as space-separated integers on a single line:

1. The maximum happiness factor Alice can achieve after doubling the number of candies in one of her piles.
2. The number of ways Alice can choose a pile to achieve the maximum happiness factor. In other words, this is the total number of piles that still result in the same maximum happiness factor if Alice chooses to double them.

Input Format

The first line contains an integer n.
The second line contains n space-separated integers describing c0,c1 ,…..cn-1 .

Constraints

1<=n<=100

1<=ci<=105

Output Format

Print the following two space-separated integers on a single line:

1. The maximum happiness factor Alice can achieve after doubling the number of candies in one of her piles.
2. The number of ways Alice can choose a pile to achieve the maximum happiness factor.

Sample Input 0

3
6 3 7

Sample Output 0

6 1

Explanation 0

Alice’s candy piles initially look like this:

We then find the happiness factor (i.e., the minimum number of candies in any pile), which is 3. Alice chooses the second pile and doubles its candies:

After doubling the second pile, the happiness factor becomes 6; this is maximal, because the happiness factor would’ve remained at 3 if Alice had chosen any of the other piles to double. We then print the maximum happiness factor, 6 , followed by the number of piles that result in that happiness factor when doubled, which is 1.

Sample Input 1

2
3 3

Sample Output 1

3 2

Explanation 1

We have two piles with three candies each, so our initial happiness factor is 3. No matter which pile Alice chooses to double, she will end up with one pile that has 3 candies and one pile that has 6 candies. This means the happiness factor will remain at 3 regardless of which of the n piles Alice chooses to double.

We then print the maximum happiness factor, 3, followed by the number of piles that result in that happiness factor when doubled, which is 2.

Problem Link: Candy Piles

Solution will be posted tomorrow.

SOLUTION

You have to maximize the minimum value after doubling any value of the array.
So all you have to do is find the frequency of minimum value.
if it is one then the number of ways will be 1 as if we double any of the value other than this minimum
value we will get the minimum value as the minimum of original array.
and if frequency of the minimum value is more than 1 then no matter whichever value we double minimum value will remain the same as
that of original array thus the number of ways will be N

now for maximum happiness double the minimum value element and then find the new minimum it will be our maximum happiness.

CODE

#include<iostream>
using namespace std;
int main()
{
    int N; cin>>N;
    int a[N];
    int min = 100000;
    int minIndex;
    // FINDING THE MINIMUM ELEMENT AND THEN ITS INDEX
    for(int i=0;i<N;i++) { cin>>a[i];
        if(a[i] < min ) {
            min = a[i];
            minIndex =i;
        }
    }
int count=0,maxHappiness,way;
    // COUNTING THE FREQUENCY OF MINIMUM ELEMENT
    for(int i=0;i<N;i++)
    {
        if(a[i]==min)
            count++;
    }
// IF MINIMUM ELEMENT FREQUENCY IS 1 THEN NUMBER OF WAYS WILL BE 1 ELSE N AS WE CAN DOUBLE ANY OF THE ELEMENT THE MINIMUM WILL REMAIN SAME
    way = (count==1)?1:N;
// DOUBLING THE MINIMUM VALUE AND THEN FINDING THE MINIMUM ELEMENT IT WILL BE OUR MAXHAPPINESS
    a[minIndex] = a[minIndex]*2;
    maxHappiness = 100000;
    for(int i=0;i<N;i++) {
        if(a[i] < maxHappiness )
            maxHappiness = a[i];
    }
cout<<maxHappiness<<" "<<way<<endl;
}