[Solution] Square Sort CodeChef Solution

Problem

You are given an array $A$ of $N$ positive integers.

In one operation, you can do the following:

• Choose an index $i$ $(1 \le i \le N)$, and change the value of $A_i$ to either $(A_i)^2$ or $\lfloor \sqrt{A_i} \rfloor$.

Find the minimum number of operations required, such that, for the final array $A$:

• $A$ is sorted in non-decreasing order;
• $A_N \le 10^{18}$.

NOTE: The elements of the array might not fit in a 32-bit integer.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of two lines of input:
  • The first line of each test case contains $N$ - the size of the array.
  • The next line contains $N$ integers, $A_1, A_2, A_3, \ldots, A_N$ - the elements of the array.

Output Format

For each test case, output on a new line, the minimum number of operations required.

Explanation:

Test case $1$: The array is already sorted, no operation is required.

Test case $2$: Using one operation, we can change $A_2$ to $\lfloor \sqrt{A_2}\rfloor = 3$. The final array is $A = [1, 3, 3, 9]$ which is sorted in non-decreasing order.

Test case $3$: We make the following operations:

• Change $A_2$ to $\lfloor \sqrt{A_2}\rfloor = 1$.
• Change $A_1$ to $\lfloor \sqrt{A_1}\rfloor = 2$.
• Change $A_1$ to $\lfloor \sqrt{A_1}\rfloor = 1$.

The final array is $A = [1, 1, 1]$ which is sorted in non-decreasing order.