All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Bob And GCD
Tag(s):

Ad-Hoc, Algorithms, Basic Programming, Basics of Greedy Algorithms, Easy, Greedy Algorithms

Problem
Editorial
Analytics

Bob has an array A of size N. He doesn't like arrays in which the \(GCD\) of all elements is not K. He can perform multiple operations on an array. In each operation, he can either increase or decrease the value of an element by 1.
You have to tell the minimum operation Bob will take to make \(GCD\) of all elements in an array equal to K or any multiple of K?

Note: The smallest value up to which you can decrease any element is 1. You cannot make any element smaller than 1.

GCD here is Greatest Common Divisor.

Input Format

The first line contains T, the number of test cases.

For Each Testcase :
The first line contains 2 integers - K and N respectively, separated by a space.
The second line contains N integers, separated by a space, in order of their position in array.

Input Constraints

\( 1 \le T \le 10 \)
\( 1 \le N \le 10^{6} \)
\( 1 \le A[i] \le 10^{6} \)
\( 1 \le K \le 10^6 \)

Output Format

For each test case, print minimum number of operations Bob take in a new line.

SAMPLE INPUT
1
5 3
4 5 6 
SAMPLE OUTPUT
2
Explanation

Testcase 1:
In first operation, increase value of 4 by 1.
In second operation, decrease value of 6 by 1.
MInimum operations = \( 1+1=2 \)

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

ThoughtWorks

Challenge Name

ThoughtWorks Application Developer Hiring Challenge for Women

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?