Bob And The Magic Count

4.8

8 votes
Greedy Algorithms, Basics of Greedy Algorithms, Algorithms
Problem

Bob is a brilliant student in the class and hence his teacher assigned him a problem. He has been given an array \(A\) of \(N\) positive integers and has been asked to make the magic count of the whole array equal to \(1\) by performing the below operation some number of times. The magic count of the array is the greatest common divisor (GCD) of all numbers in it.

  • In one operation Bob is allowed to choose some integer \(i\) \((1 <= i <= N)\) and replace \(A[i]\) with \(GCD(A[i], i)\) the cost of this operation is \(N - i + 1\). The total cost will be the sum of the costs of all the performed operations.

Help Bob in finding the minimum total cost to make the magic count of all the whole array equal to \(1\).

Note: Consider 1-based array indexing for the above problem.

Input Format:

  • The first line contains a single integer \(T\), denoting the number of test cases.
  • The first line of each test case contain the integer \(N\), denoting the number of elements in the array \(A\).
  • The second line of each test case contains \(N\) space-separated integers, denoting the elements of the array \(A\).

Output Format:

For each test case, print the minimum total cost to make the magic count of the whole array equal to \(1\).

Constraints:

\(1<= T <=10\)

\(1 <= N <= 10^5\)

\(0 <= A[i] <= 10^9\)

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For test case 1:
The magic count of the whole array is already \(1\) hence the cost needed will be \(0\).

For test case 2:
If we apply the operation on the \(3^{rd}\) index the updated array will be \([2,3,1]\) and its magic count will be \(1\), Hence, the minimum possible cost that can be obtained is \(1\).

Editor Image

?