## ThoughtWorks Interview Question for SDE1s

- 3of 3 votes

AnswerBob And GCD

- uppubhai December 11, 2017 in India

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 KK ?

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≤T≤10

1≤N≤10^6

1≤A[i]≤10^6

1≤K≤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

Ans - 2| Report Duplicate | Flag | PURGE

ThoughtWorks SDE1

**Country:**India

**Interview Type:**Written Test

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

My approach which turned out to be wrong

- uppubhai December 11, 2017