Discussion on Unfriendly Numbers Challenge

4 years ago+ 1 comment

Full Solution in Python:

I didn't find a single proper solution or even hint in discussion, so I wrote this.

hint: If factor of f divides an unfriendly number, then factor of f also divides gcd(unfriendly number, f)

Solution in python:

import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))

#sets to hold gcds and factors
gcds = set()
factors = set()

#find gcds of f and each unfriendly number
for i in l:
    gcds.add(math.gcd(i, f))


#find factors of f
for i in range(1,math.ceil(math.sqrt(f))):
    if f%i == 0:
        factors.add(i)
        factors.add(f//i)

# keeps count of number of factors not dividing unfriendly numbers
ans = 0

#find those numbers
for i in factors:
    for j in gcds:
        if j%i == 0:
            break
        else:
            continue
    
    else:
        ans+=1

print(ans)

Cookie support is required to access HackerRank