Problem Statement
Kaede is going to travel to N locations. She has already planned everything and she knows all the travel costs.
The travel costs for Kaede's trip turned out to be quite special: the costs of all tickets are powers of the same integer a.
More precisely, the ticket to location i costs anum[i] (that is, a to the num[i]-th power) units of money.
Kaede must pay for all N tickets at the same time, and her payment must also be a power of a.
To avoid paying more than necessary, she now needs to find smallest non-negative integer k such that a payment of ak (a to the k-th power) is enough to pay for all the tickets. In other words, ak must be greater than or equal to the total cost of all tickets, and k must be as small as possible.
You are given the int a and the int[] num. Please help Kaede and calculate and return the smallest k she seeks.
Definition
- Class:
- PlanningTrips
- Method:
- find
- Parameters:
- int, int[]
- Returns:
- int
- Method signature:
- int find(int a, int[] num)
- (be sure your method is public)
Constraints
- a will be between 2 and 10^9, inclusive.
- N will be between 1 and 50, inclusive.
- num will contain exactly N elements.
- Each element in num will be between 0 and 10^9, inclusive.
Examples
10
{5, 6, 3}Returns: 7
The individual trips have costs 10^5 = 100000, 10^6 = 1000000, and 10^3 = 1000. The total cost of all trips is 1101000. The smallest k such that 10^k is enough to pay for all the trips is k=7: 10^7 >= 1101000.2
{13, 13}Returns: 14
Each of the two tickets costs 2^13. The total cost of tickets is 2^13 + 2^13 = 2 * 2^13 = 2^14. Kaede can pay exactly this amount, so the smallest k in this situation is k = 14.2
{13, 0, 13}Returns: 15
The total cost of all three tickets in this example is 2^14 + 1. Kaede should pay 2^15.