6.3 Jash and the Sorting Challenge
In the brightly lit corridors of Thadomal Shahani Engineering College in Bandra, Jash sat cross-legged on the floor of the computer lab during lunch break, his prized collection of numbered cards spread before him like a cryptic puzzle. Each card bore a positive integer, and today they lay in a sequence that gnawed at his perfectionist soul— numbers dancing chaotically, refusing to bow to the sacred law of non-decreasing order. As his classmates chatted about the upcoming hackathon, Jash remained fixated on his cards, his mind racing through possibilities. He possessed an unusual gift discovered during a sleepless night of competitive programming: he could fracture any card bearing number X into precisely two new cards whose values, when combined, would resurrect X—a mathematical mitosis of sorts. A card showing 7 might split into 2 and 5, or perhaps 3 and 4, or any pair whose sum equaled 7, but once split, those fragments would remain forever, unable to merge back.
The challenge haunting Jash wasn't merely aesthetic—it was algorithmic. He needed to transform this rebellious sequence into one where each position held a value greater than or equal to its predecessor, using the minimum number of his splitting operations. Every split meant inserting a new card into the sequence at the position where the original card once lived, shifting everything rightward. But here lay the paradox: splitting a large number into smaller parts might fix one violation while creating others downstream, and splitting too many times would be inefficient. As the afternoon sun filtered through the TSEC windows, casting geometric shadows across his cards, Jash stared at the sequence, his engineering mind grappling with the question: what is the minimum number of splitting operations required to achieve perfect non-decreasing harmony?
Constraints
Input Format
The first line contains a single integer n 1 <= n <= 10^5 the number of cards Jash has.
The second line contains n space-separated integers nums[0], nums[1], ..., nums[n-1] 1 <= nums[i] <= 10^9 the numbers on Jash's cards in their current order.
Output Format
Print a single integer - the minimum number of operations needed to make the array non-decreasing.
When replacing a number X with two numbers that sum to X, you can choose any valid split. The goal is to achieve a non-decreasing sequence with the minimum number of operations.
After all operations, the array should satisfy: nums[0] ≤ nums[1] ≤ nums[2] ≤ ... ≤ nums[n-1]
Example 1
Input:
3
3 9 3
Output:
2
Explanation:
Initially, Jash has cards: 3, 9, 3
Operation 1 Replace 9 with 3 and 6 Array becomes 3, 3, 6, 3
Operation 2: Replace 6 with 3 and 3 → Array becomes [3, 3, 3, 3, 3]
Now the array is non-decreasing! Total operations: 2
Example 2
Input:
5
1 2 3 4 5
Output:
0
Explanation:
The array 1, 2, 3, 4, 5 is already in non-decreasing order. No operations needed!
Example 3
Input:
4
5 6 7 4
Output:
3
Explanation:
Initially, Jash has cards: 5, 6, 7, 4
Operation 1 Replace 5 with 2 and 3 Array becomes 2, 3, 6, 7, 4
Operation 2 Replace 6 with 3 and 3 Array becomes 2, 3, 3, 3, 7, 4
Operation 3 Replace 7 with 3 and 4 Array becomes 2, 3, 3, 3, 3, 4, 4
Now the array is non-decreasing! Total operations: 3
Log In to solve the Question