Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.
Return the two integers in any order.
 
Example 1:
Input: num = 8
Output: [3,3]
Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.

Example 2:
Input: num = 123
Output: [5,25]

Example 3:
Input: num = 999
Output: [40,25]

 
Constraints:

1 <= num <= 10^9

Difficulty: interview

Starter code:

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        

Solutions:
import collections
import itertools


def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            n /= i
            yield i
        else:
            i += 1

    if n > 1:
        yield n


def prod(iterable):
    result = 1
    for i in iterable:
        result *= i
    return result


def get_divisors(n):
    pf = prime_factors(n)

    pf_with_multiplicity = collections.Counter(pf)

    powers = [
        [factor ** i for i in range(count + 1)]
        for factor, count in list(pf_with_multiplicity.items())
    ]

    for prime_power_combo in itertools.product(*powers):
        yield prod(prime_power_combo)

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        d1 = sorted(list(get_divisors(num+1)))
        d2 = sorted(list(get_divisors(num+2)))
        
        if len(d1) % 2 == 1:
            mid = d1[int((len(d1) - 1)/2)]
            return [int(mid), int(mid)]
        
        if len(d2) % 2 == 1:
            mid = d2[int((len(d2) - 1)/2)]
            return [int(mid), int(mid)]
        
        l1, r1 = d1[int(len(d1)/2)],d1[int(len(d1)/2)-1]
        l2, r2 = d2[int(len(d2)/2)],d2[int(len(d2)/2)-1]
        
        if abs(l1-r1) < abs(l2-r2):
            return [int(l1),int(r1)]
        else:
            return [int(l2),int(r2)]


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        num+=2 #so values are num and num-1
        i = int(math.sqrt(num))
        while i>1:
            r = num%i
            if r<=1:
                return [i,(num-r)//i]
            i-=1
        return [1, num-1]


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        def divisors(n):
            for i in range(int((n+2)**0.5), 0, -1):
                if (n+1) % i == 0:
                    return [i, (n+1)//i]
                if (n+2) % i == 0:
                    return [i, (n+2)//i]
            return [1, n+1]

        return divisors(num)



class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        divisor_dict = {}
        
        def get_divisors(num):
            all_divisors = []
            divisor_set = set()
            for divisor_one in range(int(num**0.5),0,-1):
                divisor_two = int(num / divisor_one)
                if divisor_one in divisor_set or divisor_two in divisor_set:
                        continue
                if num % divisor_one == 0:
                    divisor_set.add(divisor_one)
                    divisor_set.add(divisor_two)
                    all_divisors.append((divisor_one, divisor_two))
            return all_divisors

        closest_divisor = num * 2
        
        all_divisors = []
        for divisor in get_divisors(num+1):
            all_divisors.append(divisor)
        for divisor in get_divisors(num+2):
            all_divisors.append(divisor)
        
        print(all_divisors)
        return_divisor_pair = None
        for divisor in all_divisors:
            difference = divisor[0] - divisor[1]
            if difference < 0:
                difference *= -1
            if difference < closest_divisor:
                closest_divisor = difference
                return_divisor_pair = divisor
        
        return list(return_divisor_pair)
            


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        i = 1
        while i < (num+2)**0.5+1:
            if ((num+1)%i) == 0:
                res = [i,(num+1)//i]
             
            if ((num+2)%i) == 0:
                temp = [i,(num+2)//i]
                if abs(temp[0]-temp[1]) < abs(res[0] - res[1]):
                    res = temp
            i += 1
        return res

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        i = 1
        while i < (num+2)**0.5+1:
            if ((num+1)%i) == 0:
                res = [i,(num+1)//i]
             
            if ((num+2)%i) == 0:
                if abs(i-(num+2)//i) < abs(res[0] - res[1]):
                    res = [i, (num+2)//i]
            i += 1
        return res

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        result = [None, None]
        i = 1
        while i*i<=num+2:
            if not (num+1)%i:
                result = [i, (num+1)//i]
            elif not (num+2)%i:
                result = [i, (num+2)//i]
            i += 1
        return result

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        for d in range(int((num+2)**0.5), 0, -1):
            if (num + 1)% d == 0:
                return [d, (num+1)//d]
            if (num+2)%d == 0:
                return [d, (num+2)//d]


class Solution(object):
    def closestDivisors(self, num):
        def fun(n):
            for i in range(int(n**.5),0,-1):
                if n%i==0:
                    return [n//i,i]
        
        n1=fun(num+1)
        n2=fun(num+2)
        if abs(n2[1]-n2[0])>abs(n1[1]-n1[0]):
            return n1
        return n2


class Solution:
    def closestDivisors(self, n: int) -> List[int]:
        def myfunc(n):
            for i in range(int(n**0.5),0,-1):
                if n%i == 0:
                    return [i,n//i]
        x,y=myfunc(n+1),myfunc(n+2)
        return x if abs(x[1]-x[0]) < abs(y[0]-y[1]) else y


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        x = num + 1
        y = num + 2
        a = []
        for i in range(int(x ** 0.5)+1, -1, -1):
            if x % i == 0:
                a.append([i, x // i])
                break
                
        for j in range(int(y ** 0.5)+1, -1, -1):
            if y % j == 0:
                a.append([j, y // j])
                break
        print(a)
        if abs(a[0][0] - a[0][1]) < abs(a[1][0] - a[1][1]):
            return a[0]
        return a[1]

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        def helper(k):
            for i in range(int(math.sqrt(k)),0,-1):
                if k % i == 0:
                    return [i, k//i]
        return sorted([helper(num+1), helper(num+2)], key=lambda c: abs(c[0]-c[1]))[0]


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        l1,r1 = self.cldv(num+1)
        l2,r2 = self.cldv(num+2)
        d1=r1-l1
        d2=r2-l2
        if d1<d2:
            return [l1,r1]
        else:
            return [l2,r2]

    def cldv(self, n):
        s = int(n**0.5)
        while n%s!=0:
            s-=1
        return s,n//s

def f(n):
    for i in range(int(n**.5),0,-1):
        if n%i==0:return [i,n//i]
class Solution:
    def closestDivisors(self, n: int) -> List[int]:
        a,b=f(n+1),f(n+2)
        return a if abs(a[1]-a[0])<abs(b[0]-b[1]) else b

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        
        def find(n):
            for i in range(int(n**(0.5)),0,-1):
                if n % i == 0:
                    return (i, n//i)
            return None, None
        
        a,b = find(num+1)
        c,d = find(num+2)
        return [a,b] if b - a < d  - c else [c,d]

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        
#         If I have 8, I will check for 9 also. For checking 9, I will check till half value of the number. so that i can #confirm that, its not a prime number, if it gor divided by any number. 
# In case of 10, first, I divide with 2, so the quotient will be 5. My limit will be set between 2 and 5. If there is #another couple of factors exist in between. I will take them. I will follow these steps, till divisor is less than #quotient. If I didnt get a suiatble pair, I will jump to num+2 and follow the same steps.

#         N = num+1 
#         dvsr = 2
#         quo = N
#         flag = 0
#         while(dvsr < quo and dvsr < N // 2):
#             if N % dvsr == 0:
#                 quo = int(N / dvsr)
#                 flag = 1
#             else:
#                 dvsr += 1
        
#         if flag == 1:
#             return [dvsr, quo]
        
#         N = num+2 
#         dvsr = 2
#         quo = N
#         while(dvsr < quo and dvsr < N // 2):
#             if N % dvsr == 0:
#                 quo = int(N / dvsr)
#             else:
#                 dvsr += 1
        

#         return [dvsr, quo]

# This approch is tedious, so, lets get the sqrt of the num+1 and num+2. If tehre exists a perfect square root, return that. Else, keep on decreasing the valaue unless you find one

        N1 = num + 1
        N2 = num + 2
        sqrt1 = int(N1**0.5)+1
        sqrt2 = int((N2)**0.5)+1
        
        while sqrt1 >= 2 or sqrt2 >= 2:
            if (N2) % sqrt2 == 0:
                return [sqrt2, int(N2/sqrt2)]
            if N1 % sqrt1 == 0:
                return [sqrt1, int(N1/sqrt1)]
            else:
                sqrt1 -= 1
                sqrt2 -= 1
        
        return [1, sqrt1]


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        def maxFactor(n):
            if n < 3:
                return n
            for i in range(int(math.sqrt(n)), 0, -1):
                if not n % i:
                    return i
            return 1
        res = [] 
        for n in [num + 1, num + 2]:
            a = maxFactor(n)
            b = n // a
            res.append((abs(a - b), [a, b]))
        return min(res, key = lambda x:x[0])[1]

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        for k in range(int(math.sqrt(num+2)), 0, -1):
            for x in (num+1, num+2):
                if not x % k:
                    return x // k, k

class Solution:
    def closestDivisors(self, x: int) -> List[int]:
        for a in range(int((x+2) ** 0.5), 0, -1):
            if (x + 1) % a == 0:
                return [a, (x + 1) // a]
            if (x + 2) % a == 0:
                return [a, (x + 2) // a]
        
        return []

import math
class Solution:
    def helper(self, num):
        sqrt = int(math.sqrt(num))
        gmin = float('inf')
        ans = None
        for i in range(1, sqrt + 1):
            if num % i == 0 and abs(i - num/i) < gmin:
                gmin = abs(i - num/i)
                ans = [i, int(num/i)]
        return ans
        
    def closestDivisors(self, num: int) -> List[int]:
        ans1 = self.helper(num + 1)
        ans2 = self.helper(num + 2)
        if ans1 == None:
            return ans2
        elif ans2 == None:
            return ans1
        if abs(ans1[0] - ans1[1]) < abs(ans2[0] - ans2[1]):
            return ans1
        return ans2

class Solution:
    def divizor(self, num):
        for i in range( int(math.sqrt(num)), 0, -1):
            n1 = num / i
            if n1.is_integer():
                return [int(n1), int(num / n1)]

    def closestDivisors(self, num: int) -> List[int]:
        r = []
        diff = None
        for i in [num + 1, num + 2]:
            d = self.divizor(i)
            if not d:
                continue
            abs_diff = abs(d[0] - d[1])
            if diff == None or abs_diff < diff:
                diff = abs_diff
                r = d
        return r


from math import sqrt, ceil

class Solution:
    def closestDivisors(self, num):
        closeDivs = []
        closeDivDiff = 10000000000

        if int(sqrt(num+1)) == sqrt(num+1):
            sqrtNum = int(sqrt(num+1))
            return [sqrtNum, sqrtNum]
        elif int(sqrt(num+2)) == sqrt(num+2):
            sqrtNum = int(sqrt(num+2))
            return [sqrtNum, sqrtNum]

        num += 1
        for i in range(1, ceil(sqrt(num))):
            if num % i == 0 and int(num/i) - i < closeDivDiff:
                closeDivDiff = int(num/i) - i
                closeDivs = [i, int(num/i)]

        num += 1
        for i in range(1, ceil(sqrt(num))):
            if num % i == 0 and int(num/i) - i < closeDivDiff:
                closeDivDiff = int(num/i)
                closeDivs = [i, int(num / i)]

        return closeDivs

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        return min([divs(num+1), divs(num+2)], key = lambda t: t[1]-t[0])   

def divs(n):
    ans = []
    for i in range(1,1+int(n**.5)):
        if n%i==0:
            ans = [i,n//i]
    return ans

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        for i in range(int((num+2) ** (0.5)), 0, -1):
            if not (num + 1) % i:
                return [i, (num + 1) // i]
            if not (num + 2) % i:
                return [i, (num + 2) // i]
        return []

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        n=num+1
        m=num+2
        size=int(math.sqrt(m)+1)
        holder = m
        result = [0]*2
        
        for i in range(1, size):
            if n%i == 0:
                temp = n//i
                if holder>abs(temp-i):
                    holder = abs(temp-i)
                    result[0]=temp
                    result[1]=i
            if m%i == 0:
                temp = m//i
                if holder>abs(temp-i):
                    holder=abs(temp-i)
                    result[0]=temp
                    result[1]=i
        return result

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        
        n = int((num+2)**0.5+1)
        d = num
        res = [1, num]
        for i in range(n, 0, -1):
            if not (num+1)%i: 
                if d>=abs(i - (num+1)//i):
                    res[0], res[1] = i, (num+1)//i
                    d = abs(i - (num+1)//i)
            
            if not (num+2)%i:
                if d>=abs(i - (num+2)//i):
                    res[0], res[1] = i, (num+2)//i
                    d = abs(i - (num+2)//i)
        return res

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        num1,num2=num+1,num+2
        i=int(math.sqrt(num1))
        m=int(math.sqrt(num2))
        while i>0:
            if num1%i==0:
                j=num1//i
                res1=j-i
                break
            else:
                i-=1
        while m>0:
            if num2%m==0:
                n=num2//m
                res2=n-m
                break
            else:
                m-=1
        if res1<res2:
            return [i,j]
        else:
            return [m,n]

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        if num==1: return [1,2]
        a=num+1
        b=num+2
        adiv=[]
        bdiv=[]
        for i in range(1,int(math.sqrt(b)+1)):
            if a%i==0:
                min_a=abs(a//i-i)
                adiv.append([min_a,b//i,i])
            if b%i==0:
                min_b=abs(b//i-i)
                adiv.append([min_b,b//i,i])

        m=min(adiv)
        return [m[1],m[2]]

from math import sqrt, ceil

class Solution:
    def closestDivisors(self, num):
        closeDivs = []
        closeDivDiff = 10000000000

        if int(sqrt(num+1)) == sqrt(num+1):
            sqrtNum = int(sqrt(num+1))
            return [sqrtNum, sqrtNum]
        elif int(sqrt(num+2)) == sqrt(num+2):
            sqrtNum = int(sqrt(num+2))
            return [sqrtNum, sqrtNum]

        num += 1
        for i in range(1, ceil(sqrt(num))):
            if num % i == 0 and int(num/i) - i < closeDivDiff:
                closeDivDiff = int(num/i) - i
                closeDivs = [i, int(num/i)]

        num += 1
        for i in range(1, ceil(sqrt(num))):
            if i == 19284:
                print('Yes')
            if num % i == 0 and int(num/i) - i < closeDivDiff:
                closeDivDiff = int(num/i)
                closeDivs = [i, int(num / i)]

        return closeDivs

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        n1=num+1
        n2=num+2
        h1=int(n1**0.5)
        h2=int(n2**0.5)
        stack=[]
        def run(n1,h1):
            for i in range(h1,0,-1):
                if n1%i==0:
                    tmp=n1//i
##                    print(i)
                    stack.append((abs(i-tmp),i,tmp))
        run(n1,h1)
        run(n2,h2)
        stack.sort(key=lambda x:x[0])
        return [stack[0][1],stack[0][2]]


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        need1=num+1
        need2=num+2
        
        def factors(num):
            mi=float('inf')
            ans=[]
            for i in range(1,int(num**(0.5))+1):
                if(num%i==0):
                    if(num//i-i<mi):
                        ans=[i,num//i]
                        
            return ans
        
        ls1=factors(need1)
        ls2=factors(need2)
        print((ls1,ls2))
        if(ls1[1]-ls1[0]<ls2[1]-ls2[0]):
            return ls1
        else:
            return ls2
        
        


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        res = [-math.inf, math.inf]
        min_dist = math.inf
        for i in range(1, int(math.sqrt(num+1))+2):
            if (num+1) % i == 0:
                if ((num+1)//i) - i < min_dist:
                    res = [i, (num+1)//i]
                    min_dist = (num+2)//i - i
        for i in range(1, int(math.sqrt(num+2))+2):
            if (num+2) % i == 0:
                if ((num+2)//i) - i < min_dist:
                    res = [i, (num+2)//i]
                    min_dist = (num+2)//i - i
        return res

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        for i in range(int((num+2) ** (0.5)), 0, -1):  # only check sqrt, reduce the time complexity
            if not (num+1) % i: return [i, (num+1)//i] # check if `i` is divisible by num+1
            if not (num+2) % i: return [i, (num+2)//i] # check if `i` is divisible by num+2
        return []

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        for i in range(int((num + 2)**0.5), 0, -1):
            if (num + 1) % i == 0:
                return [i, int((num + 1) / i)]
            
            if (num + 2) % i == 0:
                return [i, int((num + 2) / i)]

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        x, y = self.get_factors(num+1)
        z, t = self.get_factors(num+2)
        return [x, y] if abs(x-y) <= abs(z-t) else [z, t]
    
    def get_factors(self, n):
        y = n
        for x in range(1, int(sqrt(n))+1):
            # y = int(n/x) if (n/float(x)).is_integer() else y
            # alternatively:
            y = int(n/x) if n % x == 0 else y

        return int(n/y), y

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        vals = (num + 1, num + 2)
        for lo in itertools.count(int((num + 2) ** 0.5), -1):
            for val in vals:
                if val % lo == 0:
                    return lo, val // lo
        


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        
        def find_closest(cur):
            nonlocal mini
            nonlocal ans
            
            y = int(sqrt(cur+2))
            flag = False
            while y*y >= 1:
                mod = cur%y
                if(not mod):
                    other = cur//y
                    if((other - y) < mini):
                        mini = other - y
                        ans = [y, other]
                        flag = True
                elif((mod + 1) == y):
                    other = (cur+1)//y
                    if((other - y) < mini):
                        mini = other - y
                        ans = [y, other]
                        flag = True
                y -= 1
                if(flag):
                    break
        mini = float('inf')
        ans = None
        
        find_closest(num+1)

        return ans

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        a,b = None,None
        minDiff = float('inf')
        for i in range(1,int(num**(1/2))+10):
            if (num+1) % i == 0:
                cand1 = i
                cand2 = (num+1) // i
                if abs(cand1-cand2) < minDiff:
                    a,b = cand1,cand2
                    minDiff = abs(cand1-cand2)
            if (num+2) % i == 0:
                cand1 = i
                cand2 = (num+2) // i
                if abs(cand1-cand2) < minDiff:
                    a,b = cand1,cand2
                    minDiff = abs(cand1-cand2)
        return [a,b]

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        ans = num + 1
        val = None
        for i in range(1, ceil(sqrt(num+3))):
            if (num + 1) % i == 0:
                j = (num + 1) // i
                if abs(i-j) <= ans:
                    ans = abs(i-j)
                    val = [i, j]
            if (num + 2) % i == 0:
                j = (num + 2) // i
                if abs(i-j) <= ans:
                    ans = abs(i-j)
                    val = [i, j]
        return val


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        result = []
        difference = float(\"inf\")
        for i in range(int((num + 2)**0.5) + 1, 0, -1):
            if (num + 1) % i == 0:
                a = i
                b = (num + 1) // a
                if abs(a - b) < difference:
                    difference = abs(a - b)
                    result = [a, b]
            if (num + 2) % i == 0:
                a = i
                b = (num + 2) // a
                if abs(a - b) < difference:
                    difference = abs(a - b)
                    result = [a, b]
        return result

#
# @lc app=leetcode id=1362 lang=python3
#
# [1362] Closest Divisors
#
# https://leetcode.com/problems/closest-divisors/description/
#
# algorithms
# Medium (55.74%)
# Total Accepted:    10.2K
# Total Submissions: 17.9K
# Testcase Example:  '8'
#
# Given an integer num, find the closest two integers in absolute difference
# whose product equals num + 1 or num + 2.
#
# Return the two integers in any order.
#
#
# Example 1:
#
#
# Input: num = 8
# Output: [3,3]
# Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 =
# 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.
#
#
# Example 2:
#
#
# Input: num = 123
# Output: [5,25]
#
#
# Example 3:
#
#
# Input: num = 999
# Output: [40,25]
#
#
#
# Constraints:
#
#
# 1 <= num <= 10^9
#
#
#
from math import sqrt
from typing import List
from bisect import bisect_left

def insert(collector, solution):
    insertion_point = bisect_left(collector, abs(solution[0] - solution[1]))
    collector.insert(insertion_point, solution)

class Solution:
    \"\"\"
    >>> Solution().closestDivisors(0)
    [1, 1]

    >>> Solution().closestDivisors(1)
    [1, 2]

    >>> Solution().closestDivisors(8)
    [3, 3]

    >>> Solution().closestDivisors(123)
    [5, 25]

    >>> Solution().closestDivisors(999)
    [25, 40]

    \"\"\"
    def closestDivisors(self, num: int) -> List[int]:
        found_solutions = []
        ref_table = {}
        for i in range(1, int((sqrt(num + 2))) + 1):
            if (num + 1) % i == 0:
                distance = abs(i - (num + 1) // i)
                insertion_point = bisect_left(found_solutions, distance)
                found_solutions.insert(insertion_point, distance)
                ref_table[distance] = (i, (num + 1) // i)
            if (num + 2) % i == 0:
                distance = abs(i - (num + 2) // i)
                insertion_point = bisect_left(found_solutions, distance)
                found_solutions.insert(insertion_point, distance)
                ref_table[distance] = (i, (num + 2) // i)
        return list(ref_table[found_solutions[0]])





import math
class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        d=int(math.pow(num+1,0.5))
        e=int(math.pow(num+2,0.5))
        if (num==1):
            return ([1,2])
        ans=24839749234923385
        ll=[-1,-1]
        for i in range(2,d+1):
            if((num+1)%i==0):
                if (ans>((num+1)//i - i)):
                    ans=(num+1)//i - i
                    ll=[i,(num+1)//i]
        for i in range(2,e+1):
            if((num+2)%i==0):
                if (ans>((num+2)//i - i)):
                    ans=(num+2)//i - i
                    ll=[i,(num+2)//i]
        
        return (ll)


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        n1 = {}
        n2 = {}
        n1[tuple([1, num + 1])] = abs((num + 1) - 1)
        for i in range(2, int(sqrt(num + 1)) + 1):
            if (num + 1) % i == 0:
                n1[tuple([i, int((num + 1) / i)])] = abs(int((num + 1) / i) - i)
        n2[tuple([1, num + 2])] = abs((num + 2) - 1)
        for i in range(2, int(sqrt(num + 2)) + 1):
            if (num + 2) % i == 0:
                n2[tuple([i, int((num + 2) / i)])] = abs(int((num + 2) / i) - i)
        r1 = sorted(n1.items(), key=lambda x: x[1])
        r2 = sorted(n2.items(), key=lambda x: x[1])
        if r1[0][1] < r2[0][1]:
            return list(r1[0][0])
        return list(r2[0][0])     

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        diff=num+1
        for i in range(1,int((num+1)**0.5)+1):
            if (num+1)%i==0:
                    num1_,num1__=i,(num+1)//i
        diff=num+2
        for i in range(1,int((num+2)**0.5)+1):
            if (num+2)%i==0:
                    num2_,num2__=i,(num+2)//i
        diff1=num1__-num1_
        diff2=num2__-num2_
        return [num1_,num1__] if diff1<diff2 else [num2_,num2__]
                


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        fpairs1, fpairs2 = [], []
        for i in range(1, int((num+1)**0.5) + 1):
            if (num+1)%i == 0:
                fpairs1.append([i, int((num+1)/i)])
        for i in range(1, int((num+2)**0.5) + 1):
            if (num+2)%i == 0:
                fpairs2.append([i, int((num+2)/i)])

        return fpairs1[-1] if abs(fpairs1[-1][0] - fpairs1[-1][1]) < abs(fpairs2[-1][0] - fpairs2[-1][1]) else fpairs2[-1]
        


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        if num == 1:
            return [1,2]
        
        if num == 2:
            return [2,2]
        
        def getClose(val):
            yuh = set()
            for i in range (1, int(val**0.5)+1):
                if val % i == 0 and ((val//i, i) not in yuh or (i, val//i) not in yuh):
                    yuh.add((val//i, i))
            
            m = 10**9
            e = (-1,-1)
            for elem in yuh:
                if abs(elem[0]-elem[1]) < m:
                    e = elem 
                    m = abs(elem[0]-elem[1])
            return e
        
        a = getClose(num+1)
        b = getClose(num+2)
        
        if abs(a[0]-a[1]) < abs(b[0]-b[1]):
            return list(a)
        
        return list(b)


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        diff = math.inf
        ans = []
        n = num
        num = n+1
        
        def func(num):
            nonlocal diff, ans
            
            for i in range(1, math.ceil(math.sqrt(num))+1):
                if num%i == 0:
                    j = num//i
                    if abs(i - j) < diff:
                        diff = abs(i - j)
                        ans = [i, j]
            return ans
        
        func(n + 1)
        func(n + 2)
        
        return ans

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        fpairs1, fpairs2 = [], []
        for i in range(1, int((num+1)**0.5) + 1):
            if (num+1)%i == 0:
                fpairs1.append([i, int((num+1)/i)])
        for i in range(1, int((num+2)**0.5) + 1):
            if (num+2)%i == 0:
                fpairs2.append([i, int((num+2)/i)])

        if abs(fpairs1[-1][0] - fpairs1[-1][1]) < abs(fpairs2[-1][0] - fpairs2[-1][1]):
            return fpairs1[-1]
        else:
            return fpairs2[-1]   



import math

class Solution:
    def closestDivisors(self, num: int) -> List[int]:

        n1 = num+1
        n2 = num+2 
        
        
        def helper ( n ): 
            res = [1,n] 
            curr_diff = abs(res[0] - res[1])
            
            mid  = max ( int ( math.sqrt ( n )//1 ) ,1 ) 
            for i in range ( mid, 0,-1):
                if n % i ==0 : 
                    if abs ( i - (n//i) ) < curr_diff: 
                        res = [i,n//i]
                        curr_diff = abs ( i - (n//i) ) 
            
            return res
        
        
        n1_D = helper ( n1 )
        n2_D = helper ( n2 )
        #print(n1_D, n2_D )
        n1_D_diff =  abs ( n1_D [0] -  n1_D [1] ) 
        n2_D_diff =  abs ( n2_D [0] -  n2_D [1] )
        
        if n1_D_diff > n2_D_diff : return n2_D
        return n1_D

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        add1 = num + 1
        add2 = num + 2
        
        start = floor(sqrt(add2))
        
        for i in range(start, 0, -1):
            x1, r1 = divmod(add1, i)
            x2, r2 = divmod(add2, i)
            
            if r1 == 0:
                return i, x1
            if r2 == 0:
                return i, x2


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        vals = [num + 1, num + 2]
        sqrt = int((num + 2) ** 0.5)
        for lo in itertools.count(sqrt, -1):
            for val in vals:
                if val % lo == 0:
                    return lo, val // lo
        


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
 
        mini = float('inf')
        ans = None
        
        cur = num+1
        
        y = int(sqrt(cur+2))
        flag = False
        while y*y >= 1:
            mod = cur%y
            if(not mod):
                other = cur//y
                if((other - y) < mini):
                    mini = other - y
                    ans = [y, other]
                    flag = True
            elif((mod + 1) == y):
                other = (cur+1)//y
                if((other - y) < mini):
                    mini = other - y
                    ans = [y, other]
                    flag = True
            y -= 1
            if(flag):
                break

        return ans

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        x, y = self.get_factors(num+1)
        z, t = self.get_factors(num+2)
        return [x, y] if abs(x-y) <= abs(z-t) else [z, t]
    
    def get_factors(self, n):
        y = n
        for x in range(1, int(sqrt(n))+1):
            # y = int(n/x) if (n/float(x)).is_integer() else y
            # alternatively, using mod is faster than direct division:
            y = int(n/x) if n % x == 0 else y

        return int(n/y), y

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        for i in range(int((num+2) ** (0.5)), 0, -1):  # only check sqrt, reduce the time complexity
            if not (num+1) % i: return [i, (num+1)//i] # check if `i` is divisible by num+1
            if not (num+2) % i: return [i, (num+2)//i] # check if `i` is divisible by num+2
        return []


import math

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        for x in range(int(math.sqrt(num + 2)), 0, -1):
            if (num + 1) % x == 0:
                return [x, (num + 1) // x]
            if (num + 2) % x == 0:
                return [x, (num + 2) // x]

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        n = int (math.sqrt(num+2))
        max_ = 0
        check = False
        for i in range(1,n+1):
            if (num + 1) % i == 0:
                max_ = i
                check = False
            elif (num + 2) % i == 0:
                print(i)
                max_ = i
                check = True
        
        if check: return max_, int ((num+2)/max_)
        else: return max_, int ((num+1)/max_)
        


class Solution:
    def closestDivisors(self, num: int) -> List[int]:     
        
        num += 1
        for factor in range(int((num)**0.5), 0, -1):
            if num % factor == 0:
                num_1 = [factor, num//factor]
                break
        
        num += 1
        for factor in range(int((num)**0.5), 0, -1):
            if num % factor == 0:
                num_2 = [factor, num//factor]
                break
                
        return min(num_1, num_2, key=lambda x: abs(x[0]-x[1]))

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        num1, num2 = num + 1, num + 2
        def findDivisors(num):
            start = int(num ** 0.5)
            for i in range(start, 0, -1):
                if num % i == 0:
                    return [i, num // i]
        div1 = findDivisors(num1)
        div2 = findDivisors(num2)
        div_pairs = [div1, div2]
        res = min(div_pairs, key = lambda x : abs(x[0] - x[1]))
        return res

from math import sqrt
from typing import List


class Solution:
    def findDivisor(self, num):
        min_gap = num
        min_gap_saved = []
        # for i in range(int(sqrt(num)), 0, -1):
        for i in range(1, int(sqrt(num)) + 1):
            if num % i == 0:
                gap = abs(i - num // i)
                if gap < min_gap:
                    min_gap = gap
                    min_gap_saved = sorted([i, num // i])
        return min_gap_saved

    def closestDivisors(self, num: int) -> List[int]:
        a, b = self.findDivisor(num + 1)
        c, d = self.findDivisor(num + 2)
        if b - a > d - c:
            return [c, d]
        else:
            return [a, b]


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        def compute(n):
            diff = float(\"inf\")
            res = []
            for i in range(1, 1+int(n**0.5)):
                if n % i == 0:
                    if abs(n//i - i) < diff:
                        diff = abs(n//i - i)
                        res = [n//i, i]
            return [diff, res]
        d1, r1 = compute(num+1)
        d2, r2 = compute(num+2)
        return r1 if d1 < d2 else r2

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        x, y = self.get_factors(num+1)
        z, t = self.get_factors(num+2)
        return [x, y] if abs(x-y) <= abs(z-t) else [z, t]
    
    def get_factors(self, n):
        y = n
        for x in range(1, int(sqrt(n))+1):
            # y = int(n/x) if (n/float(x)).is_integer() else y
            # alternatively, using mod is faster than direct division:
            y = int(n/x) if n % x == 0 else y

        return int(n/y), y
    
# use n % x to check whether x divides n


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        r = int(math.sqrt(num+2))
        d, ans = inf, [1, num+1]
        for x in range(r, 1, -1):
            for y in [num + 1, num + 2]:
                if y % x == 0:
                    diff = abs(x - y // x)
                    if d > diff:
                        d = diff
                        ans = [x, y // x]
        return ans


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        x = int((num+2)**0.5)
        best = [float('inf'), -float('inf')]
        for y in range(x, 0, -1):
            for z in ((num+1, num+2)):
                if z % y == 0:
                    if abs(y - z//y) < abs(best[0] - best[1]):
                        best = [y, z//y]
        return best


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        minimum = float(\"Inf\")
        upper_bound = int((num + 2) ** 0.5) + 1
        a,b = -1,-1
        for i in range(upper_bound+1 , 0,-1):
            if (num+1) % i == 0:
                first = i
                last = (num+1)// first
                if minimum > abs(first-last):
                    a = first
                    b = last
                    minimum = abs(a-b)
            if (num+2) % i == 0:
                first = i
                last = (num+2) // first
                if minimum > abs(first-last):
                    a = first
                    b = last
                    minimum = abs(a-b)
        return [a,b]

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        
        if not num:
            return []
        
        for i in range(int(sqrt(num+2)), 0, -1):
            
            if not (num+1) % i:
                return([i, (num+1)//i])
            
            if not(num+2) % i:
                return([i, (num+2)//i])

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        sqrt = int(num ** (0.5))+1
        for i in range(sqrt, 0, -1):
            j1 = (num+1) // i
            j2 = (num+2) // i
            d1 = d2 = sys.maxsize
            if j1 * i == num+1:
                d1 = abs(j1-i)
            if j2 * i == num+2:
                d2 = abs(j2-i)
            if d1 != sys.maxsize or d2 != sys.maxsize:
                return [j1, i] if d1 < d2 else [j2, i]
        return []            


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        # for num
        a = floor((num+2)**0.5)
        while a > 0:
            n = 0
            a2 = a**2
            if mod(num+1-a2,a)==0:
                return [a, a + int((num+1-a2)/a)]
            if mod(num+2-a2,a)==0:
                return [a, a + int((num+2-a2)/a)]
            #print(a,n1)
            a -= 1
            
        


import math
class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        d=num
        s = math.ceil(math.sqrt(num))
        while s>0:
            if s*(num//s)==num+1 or s*(num//s)==num+2:
                return [s,num//s]
            elif s*(num//s +1)==num+1 or s*(num//s +1)==num+2:
                return [s,num//s+1]
            s-=1
        return [1,num]

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        # for num
        a = floor((num+2)**0.5)
        n1 = None
        while a > 0:
            n = 0
            a2 = a**2
            if mod(num+1-a2,a)==0:
                return [a, a + int((num+1-a2)/a)]
            if mod(num+2-a2,a)==0:
                return [a, a + int((num+2-a2)/a)]
            #print(a,n1)
            a -= 1
            
        


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        
        def getDiv(n):
            d1s = 1
            d2s = n
            s = n - 1
            
            d1 = 1
            d2 = n
            
            while d1 <= d2:
                d1 += 1
                if n % d1 == 0:
                    d1s = d1
                    d2s = n // d1
                d2 = n / d1
            
            return (d1s,d2s)
        
        v1,v2 = getDiv(num+1)
        z1,z2 = getDiv(num+2)
        
        vdif = v2 - v1
        zdif = z2 - z1
        
        print((v1,v2,z1,z2))
        print((vdif,zdif))
        
        if vdif > zdif:
            return [z1,z2]
        else:
            return [v1,v2]


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        cd1 = self.closestDivisorWithProduct(num+1)
        cd2 = self.closestDivisorWithProduct(num+2)
        if cd1 == None:
            return cd2
        elif cd2 == None:
            return cd1
        if abs(cd1[0]-cd1[1]) < abs(cd2[0]-cd2[1]):
            return cd1
        else:
            return cd2
        
    def closestDivisorWithProduct(self, num):
        divisors = [(i, num // i) for i in range(1, int(num**0.5)+1) if num % i == 0]
        minPair = None
        minDiff = num
        for a, b in divisors:
            if a * b != num:
                continue
            if abs(a-b) < minDiff:
                minPair = (a,b)
                minDiff = abs(a-b)
        return minPair

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        nums = [num + 1, num + 2]
        pair = (1, num+1)
        seen = collections.defaultdict(bool)

        for i,num in enumerate(nums):
            for j in range(1, int(sqrt(num))+1):
                if seen[j]:
                    continue

                if num % j == 0:
                    seen[num // j] = True
                    if abs(pair[0] - pair[1]) > abs(j - num // j):
                        pair = (j, num // j)
        return pair

class Solution:
\tdef closestDivisors(self, num: int) -> List[int]:
\t\tfrom math import sqrt
\t\tdef factor(n):
\t\t\td = int(sqrt(n))
\t\t\tif d*d == n:
\t\t\t\treturn [d, d]
\t\t\tdefault = [1, n]
\t\t\tfor i in range(2, d+1):
\t\t\t\tx, m = divmod(n, i)
\t\t\t\tif not m:
\t\t\t\t\tdefault = [i, x]
\t\t\treturn default
\t\tx = factor(num+1)
\t\ty = factor(num+2)
\t\tif abs(x[0] - x[1]) < abs(y[0] - y[1]):
\t\t\treturn x
\t\treturn y



class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        def get_best_divisors(num):
            ans = [1, num]

            i = 2
            while i*i <= num:
                if num % i == 0:
                    divisor = num // i
                    if (divisor-i) < ans[1]-ans[0]:
                        ans = [i, divisor]
                i += 1
            return ans

        n_plus1_cand = get_best_divisors(num+1)
        diff1 = n_plus1_cand[1] - n_plus1_cand[0]
        if diff1 == 0:
            return n_plus1_cand

        n_plus2_cand = get_best_divisors(num+2)
        diff2 = n_plus2_cand[1] - n_plus2_cand[0]
        if diff2 < diff1:
            return n_plus2_cand
        return n_plus1_cand

import math
class Solution:
    def get_closest(self, num):
        for val in range(int(math.sqrt(num)), 0, -1):
            if not num % val:
                return [val, num // val]
        return [1, num]
            
    def closestDivisors(self, num: int) -> List[int]:
        temp1, temp2 = self.get_closest(num + 1), self.get_closest(num + 2)
        return temp1 if (abs(temp1[0] - temp1[1]) < abs(temp2[0] - temp2[1])) else temp2

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        
        def find_closest(cur):
            nonlocal mini
            nonlocal ans
            
            y = 1
            while y*y <= (cur+2):
                mod = cur%y
                if(not mod):
                    other = cur//y
                    if((other - y) < mini):
                        mini = other - y
                        ans = [y, other]
                elif((mod + 1) == y):
                    other = (cur+1)//y
                    if((other - y) < mini):
                        mini = other - y
                        ans = [y, other]
                y += 1
        
        mini = float('inf')
        ans = None
        
        find_closest(num+1)

        return ans

from math import sqrt
from typing import List


class Solution:
    def findDivisor(self, num):
        min_gap = num
        min_gap_saved = []
        for i in range(int(sqrt(num)), 0, -1):
            if num % i == 0:
                gap = abs(i - num // i)
                if gap < min_gap:
                    min_gap = gap
                    min_gap_saved = sorted([i, num // i])
        return min_gap_saved

    def closestDivisors(self, num: int) -> List[int]:
        a, b = self.findDivisor(num + 1)
        c, d = self.findDivisor(num + 2)
        if b - a > d - c:
            return [c, d]
        else:
            return [a, b]


s = Solution()
print((s.closestDivisors(8)))
print((s.closestDivisors(123)))
print((s.closestDivisors(999)))
print((s.closestDivisors(170967091)))


class Solution:
    def solve(self,x):
        a = max(1, int(math.sqrt(x)) )
        while (a*(x//a))!=x:
            a = max(1, a-1 )
        return [a,x//a]
    def closestDivisors(self, x):
        a,b = self.solve(x+1)
        if a==b:
            return [a,b]
        c,d = self.solve(x+2)
        return [a,b] if (b-a)<=(d-c) else [c,d]

class Solution:
    def solve(self,x):
        a = max(1, int(math.sqrt(x)) )
        while (a*(x//a))!=x:
            a = max(1, a-1 )
        return [a,x//a]
    def closestDivisors(self, x):
        a,b = self.solve(x+1)
        c,d = self.solve(x+2)
        return [a,b] if (b-a)<=(d-c) else [c,d]

class Solution:
    def solve(self,x):
        a = max(1, int(math.sqrt(x)) )
        b = x//a
        while (a*b)!=x:
            a = max(1, a-1 )
            b = x//a
        return [a,b]
    def closestDivisors(self, x):
        a,b = self.solve(x+1)
        c,d = self.solve(x+2)
        return [a,b] if (b-a)<=(d-c) else [c,d]

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        x, y = self.get_factors(num+1)
        z, t = self.get_factors(num+2)
        return [x, y] if abs(x-y) <= abs(z-t) else [z, t]
    
    def get_factors(self, n):
        y = n
        for x in range(1, int(sqrt(n))+1):
            y = int(n/x) if (n/float(x)).is_integer() else y

        return int(n/y), y

import math
def difun(num):
    ans=num
    n1=0
    n2=0
    for i in range(int(math.sqrt(num)),0,-1):
        abc=abs(i-(num//i))
        if(num%i==0 and abc<ans):
            ans=abc
            n1=i
            n2=num//i
    return ans,n1,n2
class Solution:
    
    def closestDivisors(self, num: int) -> List[int]:
        a,b,c=difun(num+1)
        print(a,b,c)
        d,e,f=difun(num+2)
        print(d,e,f)
        if(a<d):return [b,c]
        return [e,f]

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        closestOne = self.findClosestProduct(num+1)
        closestTwo = self.findClosestProduct(num+2)
        differenceOne = abs(closestOne[0]-closestOne[1])
        differenceTwo = abs(closestTwo[0]-closestTwo[1])
        if differenceOne > differenceTwo:
            return closestTwo
        else:
            return closestOne
    def findClosestProduct(self,num):
        ##we start from floor of sqrt(num) and go down.
        for i in range(int(math.sqrt(num)),0,-1):
            if num%i == 0:
                return [i,num//i]


def findDivisors(n):
    res = []
    i = 1
    while i <= sqrt(n):
        if n % i == 0:
            res.append([i, n//i])
        i = i + 1
    return res

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        A = findDivisors(num + 1)
        B = findDivisors(num + 2)

        return A[-1] if abs(A[-1][0] - A[-1][1]) < abs(B[-1][0] - B[-1][1]) else B[-1]

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        # primes = self.get_prime_numbers_below(num+3)
        x, y = self.get_factors(num+1)
        z, t = self.get_factors(num+2)
        print((x, y), (z, t))
        return [x, y] if abs(x-y) <= abs(z-t) else [z, t]
        
    def get_prime_numbers_below(self, n):
        numbers = set([i for i in range(2, n)])
        for i in range(2, int(sqrt(n))+1):
            j = max(2, i)
            while(i*j < n):
                if i*j in numbers: numbers.remove(i*j)
                j += 1
        return list(numbers)
    
    def get_factors(self, n):
        y = n
        for x in range(1, int(sqrt(n))+1):
            y = int(n/x) if (n/float(x)).is_integer() else y

        return int(n/y), y

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        cd1 = self.closestDivisorWithProduct(num+1)
        cd2 = self.closestDivisorWithProduct(num+2)
        if abs(cd1[0]-cd1[1]) < abs(cd2[0]-cd2[1]):
            return cd1
        else:
            return cd2
        
    def closestDivisorWithProduct(self, num):
        divisors = [(i, num // i) for i in range(1, int(num**0.5)+1) if num % i == 0]
        minPair = None
        minDiff = num
        for a, b in divisors:
            if a * b != num:
                continue
            if abs(a-b) < minDiff:
                minPair = (a,b)
                minDiff = abs(a-b)
        return minPair

import math

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        num1 = num + 1
        num2 = num + 2
        divisor = []
        divisor = self.find_divisors(num1, 1000000001, divisor)
        divisor = self.find_divisors(num2, abs(divisor[0] - divisor[1]), divisor)
        return divisor
        
    def find_divisors(self, num, difference, divisors):
        i = 1
        while i <= math.sqrt(num):
            if num % i == 0:
                second = num // i
                diff = abs(second - i)
                if diff < difference:
                    divisors = [i, second]
            i += 1
        return divisors
        


class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        
        def find_closest(cur):
            nonlocal mini
            nonlocal ans
            
            y = 1
            while y*y <= cur:
                if(not cur%y):
                    other = cur//y
                    if((other - y) < mini):
                        mini = other - y
                        ans = [y, other]
                y += 1
        
        mini = float('inf')
        ans = None
        
        find_closest(num+1)
        find_closest(num+2)

        return ans