GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Wednesday 3 August 2022

[Solution] Beautiful Array Codechef Solution



Problem

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

  • 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.

No comments:

Post a Comment