[Solution] Beautiful Array solution codechef

Beautiful Array solution codechef – You’re given an array A of N integers. You need to find the minimum cost of creating another array B of N integers with the following properties

Table of Contents

[Solution] Beautiful Array solution codechef

  • B_i \ge 0 for each 1 \leq i \leq N
  • The GCD of adjacent elements of B is equal to 1, i.e, \gcd(B_i, B_{i+1}) = 1 for each 1 \leq i \lt N

The cost of creating B is defined as follows:

\sum_{i=1}^{N} 2^{|A_i – B_i |}

Find the minimum possible cost to create the array B. Since the answer can be huge print it modulo 10^9+7

Note: You need to minimize the value of total cost of creating the array B, and then print this minimum value modulo 10^9 + 7. For example, suppose there is a way to create the required B with a cost of 500, and another way to do it with a cost of 10^9 + 7 (which is 0 \pmod {10^9 + 7}). The output in this case would be 500 and not 0.

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • The first line of each test case contains an integer N – the length of the array A
  • The second line of each test case contains N space-separated integers A_1,A_2,\ldots,A_N

Output Format

For each test case, output on a new line the minimum cost of creating the array B, modulo 10^9 + 7.

Beautiful Array solution codechef

  • 1 \leq T \leq 150
  • 1 \leq N \leq 10^4
  • 1 \leq A_i \leq 10^6
  • The sum of N over all test cases won’t exceed 10^4.

Sample 1:

Input

Output

3
3
15 16 19
2
5 10
7
9 15 7 19 10 7 1

 

3
3
8

 

Beautiful Array solution codechef Explanation

Test case 1: The given input already satisfies all the conditions, hence we can take B = A with a cost of 2^0 + 2^0 + 2^0 = 3.

Test case 2: One optimal way is to choose B as [ 5, 11 ], with a cost of 2^0 + 2^1 = 3.

For Solution

Click Here

Leave a Comment