Skip to main content

Uber

Uber OA-4 2023

Problem Description

You are tasked with ensuring that the prices of cars, initially arranged in a line, become non-decreasing as quickly as possible. The price of each car is given as an array. You can perform operations over multiple chances to adjust the car prices.

At each chance X, you can select one or more distinct cars at indices
(i_1, i_2, ..., i_k) where (k>=0) and add 2^{X-1} to the prices of those cars, Formally C[i]=C[i] + 2^{X-1}.

Your objective is to find the smallest number (T) such that after (T) chances, the prices of all cars are non-decreasing.

Input Format:

  • t: An integer representing the number of test cases.
  • For each test case:
    • n: An integer representing the number of cars.
    • carPrices: An array of (n) integers, where C[i] represents the price of the
      ith car.

The sum of (n) across all test cases does not exceed 10^6.

Output Format:

  • For each test case, output the minimum number of chances (T) required to make the car prices non-decreasing.

Constraints:

  • 1 <= t <= 10^4
  • (n>0) (for each test case)
  • The sum of (n) over all test cases does not exceed (10^6)
  • -10^5 < C[i] < 10^5

Example 1:

Input:

1
4
[1, 7, 6, 5]

Output:

2

Explanation:

  • After the 1st chance, you select indices 3 and 4 to increase their prices, resulting in [1, 7, 7, 6].
  • After the 2nd chance, you select index 4, resulting in [1, 7, 7, 8].
  • The prices are now non-decreasing, and it took 2 chances.

Example 2:

Input:

1
2
[6, 2]

Output:

3

Explanation:

  • After the 1st chance, you select index 2, resulting in [6, 3].
  • After the 2nd chance, you skip (do nothing), so prices remain [6, 3].
  • After the 3rd chance, you select index 2 again, resulting in [6, 7].
  • The prices are now non-decreasing, and it took 3 chances.