Salary Blues - Hackerrank Problem Solution in Python

Salary Blues

Hackerrank Problem Solution

Salary Blues - Hackerrank Problem Solution

PROBLEM STATEMENT

YManager of HackerX company is having big trouble. Workers are very unhappy with the way salary is given to them. They want every worker to have the same salary, otherwise they will go on a strike.

Their current salaries are denoted by a sequence of N integers: A1, A2, A3 ... AN . Manager has decided to take action and make their salaries equal. He uses the following process until all salaries are equal. This method is called normalization:

a) Select any two different values from A.

b) Replace larger value with the difference of the two. Difference of two positive integers B and C is defined as |B-C|.

He knows that the final value will always be unique.
Now, Q queries are given. In each query you are given an integer K. K is the amount to be added to everyone's salary as bonus, before the normalization.

Input Format
First line contains, N and Q, the number of employees and the number of queries. Next line contains N space seperated positive integers denoting the array A. Next Q lines contain queries. Each query consists of one integer per line denoting K.

Output Format
For each query, print the normalized salary (which is same for everyone in the end) in one line.

Constraints
1 ≤ N ≤ 105
1 ≤ Q ≤ 105
1 ≤ A[i] ≤ 1014
0 ≤ K ≤ 109

Sample Input

4 2
9 12 3 6
0
3

Sample Output

3
3

Explanation
for sample input:
If 0 is added to every element of array A, it will remain same.
One way to normalise A is this:
1. Picking 12 and 3 gives: 9 9 3 6
2. Picking 3 and 6 gives: 9 9 3 3
3. Picking 9 and 3 gives: 6 9 3 3
4. Picking 9 and 3 gives: 6 6 3 3
5. Picking 6 and 3 gives: 3 6 3 3
6. Picking 6 and 3 gives: 3 3 3 3

---

SOLUTION IN PYTHON

from math import gcd n, q = map(int, input().split()) s = set(map(int, input().split())) s = list(s) n = len(s) for i in range(1, n): s[i] -= s[0] if n > 1: g = s[1] else: g = s[0] for i in range(2, n): g = gcd(g, s[i]) while (q != 0): p = int(input()) if n == 1: print(s[0]+p) else: print(gcd(g, s[0]+p)) q -= 1

Share Share Tweet Share Share Share

LIKE?

SHARE If you find this useful, please share with your friends and Community.
CODE TOGETHER..GROW TOGETHER.