 ZCO14003

# Smart Phone

how it can be solved ?

Follow these steps to solve the problem.

1. Sort the array elements in Non-Decreasing Order
3. Now, start iterating over the array elements.
• Pick the current element and choose it as price for current stage. Now, what is the total revenue you can generate if you choose cost of this element as price?
A: The number of elements that are greater than or equal to this element times the price.
How do you find the number of elements greater than or equal to this element in O(1)?
A: It is simply (number of elements to the right) + 1.
1. So, for each element in the array, we update our answer with the max of existing answer and current value.

Pseudo Code:

``````n = readInt();
sort(a);
ans = 0;
for(i=0;i<n;i++) {
currentCost = (a[i] * (n-i));
ans = max(ans, currentCost);
}
return ans;
``````

Note: YOU MUST TAKE CARE OF BOUNDS. YOU MIGHT WANT TO USE LONG OR LARGER DATA TYPES (by larger I mean which can store bigger values, say 10^{18}) FOR THIS PROBLEM, IT WAS MENTIONED TOO.

1 Like

Thank you so much.