The Chosen One - Hackerrank Problem Solution

The Chosen One

Hackerrank Problem Solution

PROBLEM STATEMENT

You are given a sequence of  integers, . Find and print any integer  such that  is divisor of every  except for exactly one element.

Input Format

The first line contains an integer, , denoting the length of the sequence.
The second line contains  positive space-separated integers describing .

Constraints

• It is guaranteed that a solution exists.

Output Format

Print any positive integer denoting  such that  is a divisor of exactly  of the sequence's elements.  must be between  and 

Sample Input 0

4
3 6 18 12

Sample Output 0

6

Explanation 0

We are given the array . There are two possible answers:

1.  is a divisor of , , and  but not a divisor of .
2.  is a divisor of , , and  but not a divisor of .

Thus, we can print either  or  as our answer.

---

SOLUTION

#!/bin/python3 import math import os import random import re import sys if __name__ == '__main__': n = int(input()) a = list(map(int, input().rstrip().split())) if n==1: print(a[0]+1) else: pre=[0] suf=[0] p=0 s=0 dup=a.copy() dup.reverse() for i in range(len(a)): pre.append(math.gcd(pre[p],a[i])) p+=1 for i in range(len(dup)): suf.append(math.gcd(suf[s],dup[i])) s+=1 suf.reverse() for i in range(len(a)): g=math.gcd(pre[i],suf[i+1]) if a[i]%g!=0: print(g) break

Share Share Tweet Share Share Share

LIKE?

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