Our Chef is catering for a big corporate office party and is busy preparing different mouth watering dishes. The host has insisted that he serves his delicious cupcakes for dessert. 

On the day of the party, the Chef was over-seeing all the food arrangements as well, ensuring that every item was in its designated position. The host was satisfied with everything except the cupcakes. He noticed they were arranged neatly in the shape of a rectangle. He asks the Chef to make it as square-like as possible. 

The Chef is in no mood to waste his cupcakes by transforming it into a perfect square arrangement. Instead, to fool the host, he asks you to arrange the N cupcakes as a rectangle so that the difference between the length and the width is minimized. 

------ Input ------ 

The first line of the input file contains an integer T, the number of test cases. Each of the following T lines contains a single integer N denoting the number of cupcakes.

------ Output ------ 

Output T lines, each indicating the minimum possible difference between the length and the width in a rectangular arrangement of the cupcakes.

------ Constraints ------ 

1 ≤ T ≤ 100
1 ≤ N ≤ 10^{8}

----- Sample Input 1 ------ 
4
20
13
8
4
----- Sample Output 1 ------ 
1
12
2
0
----- explanation 1 ------ 
Test case $1$: $20$ cupcakes can be arranged in a rectange in $6$ possible ways -  $1 \times 20, 2 \times 10, 4 \times 5, 5 \times 4, 10 \times 2$ and $20 \times 1$.  
The corresponding differences between the length and the width for each of these rectangles are $ |1-20| = 19, |2-10| = 8, |4-5| = 1, |5-4| = 1, |10-2| = 8$ and $|20-1| = 19$ respectively. Hence, $1$ is the smallest difference between length and width among all possible combinations.

Test case $2$: $13$ cupcakes can be arranged in $2$ ways only. These are $13 \times 1$ and $1 \times 13$. In both cases, the difference between width and length is $12$.

Test case $3$: $8$ cupcakes can be arranged in $4$ ways. These are: $8\times 1, 4\times 2, 2\times 4$ and $1\times 8$. The minimum difference between length and width is $2$ which is in the cases $4\times 2 $ and $2\times 4$.

Test case $4$: $4$ cupcakes can be arranged as $2\times 2$. The difference between the length and the width, in this case, is $0$.

Difficulty: EASY
Tags: Number theory

Mathematics

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	f = False
	d = n - 1
	for j in range(int(n ** 0.5), 0, -1):
		if n % j == 0:
			if d > abs(j - n / j):
				d = abs(j - n / j)
	print(int(d))


import math
T = int(input())
for i in range(T):
	op = int(input())
	sqr_root = int(math.sqrt(op))
	i_don = 10000000000.0
	for i in range(1, sqr_root + 1):
		if op % i == 0:
			i_don = min(i_don, op // i - i)
	print(i_don)


for i in range(int(input(''))):
	x = int(input(''))
	for j in range(int(x ** 0.5), 0, -1):
		if x % j == 0:
			a = x // j
			ans = abs(a - j)
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	for i in range(int(n ** (1 / 2)), 0, -1):
		if not n % i:
			print(n // i - i)
			break


import math
T = int(input())
for _ in range(T):
	n = int(input())
	if n == 1:
		print(0)
	elif n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		min = n - 1
		for i in range(2, int(math.sqrt(n) + 1)):
			if n % i != 0:
				pass
			else:
				alp = abs(i - n // i)
				if alp < min:
					min = alp
				else:
					pass
		print(min)


t = int(input())
for i in range(t):
	n = int(input())
	m = 10000000000
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			a = n // i
			b = abs(i - a)
			m = min(m, b)
	print(m)


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(int(n ** 0.5), 0, -1):
		if n % i == 0:
			l.append([i, int(n / i)])
	a = []
	for i in l:
		b = abs(i[1] - i[0])
		a.append(b)
	print(min(a))


import math
for _ in range(int(input())):
	n = int(input())
	a = []
	t = int(math.sqrt(n))
	for i in range(1, t + 1):
		if n % i == 0:
			b = n // i
			a.append(abs(i - b))
	print(min(a))


import math
T = int(input())
for i in range(T):
	N = int(input())
	L = int(math.sqrt(N))
	F = True
	while F:
		if N % L == 0:
			dif = abs(L - N / L)
			F = False
		L -= 1
	print(int(dif))


t = int(input())
for _ in range(t):
	n = int(input())
	for i in range(int(n ** 0.5), 0, -1):
		if n % i == 0:
			print(n // i - i)
			break


for _ in range(int(input())):
	n = int(input())
	ans = n - 1
	dp = set()
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0 and i not in dp:
			ans = min(ans, abs(i - n // i))
			dp.add(i)
			dp.add(n // i)
	print(ans)


from math import sqrt
t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			l.append(abs(i - int(n / i)))
	print(min(l))


t = int(input())
while t:
	a = int(input())
	for i in range(int(a ** 0.5), 0, -1):
		if a % i == 0:
			print(abs(a // i - i))
			break
	t -= 1


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = int(math.sqrt(n))
	b = True
	while b:
		if n % a == 0:
			dif = abs(a - n / a)
			b = False
		a -= 1
	print(int(dif))


for i in range(int(input())):
	n = int(input())
	sqrt = int(n ** 0.5)
	minimum = 10000000000.0
	for j in range(1, sqrt + 1):
		if n % j == 0:
			minimum = min(minimum, abs(n // j - j))
	print(minimum)


t = int(input())
for i in range(t):
	f = 0
	n = int(input())
	for i in range(int(n ** 0.5), 1, -1):
		if n % i == 0:
			a = n // i
			b = i
			print(abs(a - b))
			f = 1
			break
	if f == 0:
		print(n - 1)


t = input()
for c in range(0, int(t)):
	n = int(input())
	mi = n - 1
	for i in range(int(n ** 0.5), 1, -1):
		if n % i == 0:
			mi = min(mi, abs(n // i - i))
	print(mi)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	m = int(math.sqrt(n))
	min = n - 1
	for i in range(2, m + 1):
		if n % i == 0:
			if min > abs(n // i - i):
				min = abs(n // i - i)
	print(min)


import math
t = int(input())
for q in range(t):
	n = int(input())
	d = n - 1
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			d = min(d, abs(i - n // i))
	print(d)


for tc in range(int(input())):
	n = int(input())
	x = int(n ** 0.5)
	while n % x != 0:
		x -= 1
	if x == 0:
		print(0)
	else:
		print(int(abs(x - n / x)))


import math
for t in range(int(input())):
	n = int(input())
	m = float('inf')
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			x = n // i
			if abs(x - i) < m:
				m = abs(x - i)
	print(m)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	n_sqrt = math.floor(math.sqrt(n))
	k = 1
	for i in range(1, n_sqrt + 1):
		if n % i == 0:
			k = i
	print(int(n // k - k))


import math
tests = int(input())
for i in range(tests):
	num = int(input())
	end = math.floor(num ** 0.5) + 1
	diff = num - 1
	for j in range(1, end):
		other = num / j
		if other == int(other) and diff > abs(other - j):
			diff = int(abs(other - j))
	print(diff)


import math
T = int(input())
for i in range(T):
	x = 0
	l = []
	N = int(input())
	for i in range(1, int(math.sqrt(N)) + 1):
		if N % i == 0:
			x = N / i - i
			l += [x]
	l.sort()
	print(int(l[0]))


for i in range(int(input())):
	a = int(input())
	d = a
	z = []
	for i in range(1, int(a ** 0.5) + 1):
		if a % i == 0:
			z.append(abs(i - a // i))
	print(min(z))


import math
test_case = int(input())
for _ in range(test_case):
	n = int(input())
	minn = 10000000000
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			minn = min(minn, abs(i - n // i))
	print(minn)


try:
	for _ in range(int(input())):
		num = int(input())
		Min = num - 1
		for i in range(1, int(num ** (1 / 2)) + 1):
			if i * i == num:
				Min = 0
			elif num % i == 0 and abs(num // i - i) < Min:
				Min = abs(num // i - i)
		print(Min)
except:
	pass


for i in range(int(input())):
	N = int(input())
	import math
	N_sqrt = math.floor(math.sqrt(N))
	k = 1
	for i in range(1, N_sqrt + 1):
		if N % i == 0:
			k = i
	print(int(N // k - k))


import math
for item in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	elif n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		m = n - 1
		for i in range(2, int(math.sqrt(n) + 1)):
			if n % i != 0:
				pass
			else:
				alp = abs(i - n // i)
				if alp < m:
					m = alp
				else:
					pass
		print(m)


import math
for _ in range(int(input())):
	x = int(input())
	d = []
	for i in range(1, int(math.sqrt(x) + 1)):
		if x % i == 0:
			x2 = x / i
			d.append(int(abs(x2 - i)))
	print(min(d))


import math
t = int(input())
l = []
for i in range(t):
	N = int(input())
	for i in range(int(N ** 0.5), 0, -1):
		if N % i == 0:
			print(N // i - i)
			break


t = int(input())
for test in range(t):
	n = int(input())
	l = int(n ** 0.5)
	arr = []
	for i in range(1, l + 1):
		if n % i == 0:
			s = n // i
			arr.append(s - i)
	print(min(arr))


import math
t = int(input())
for i in range(t):
	n = int(input())
	root_n = math.floor(math.sqrt(n))
	s = 1
	for j in range(1, root_n + 1):
		if n % j == 0:
			s = j
	print(int(n // s - s))


t = int(input(''))
if 1 <= t <= 100:
	for _ in range(t):
		n = int(input(''))
		sq = int(n ** 0.5)
		min = n
		if 1 <= n <= 10 ** 8:
			for i in range(1, sq + 1):
				if n % i == 0:
					d = n // i - i
					if d < min:
						min = d
			print(min)


for t in range(int(input())):
	N = int(input())
	for i in range(int(N ** 0.5), 0, -1):
		if N % i == 0:
			print(N // i - i)
			break


import math
T = int(input())
for i in range(T):
	n = int(input())
	nsq = math.floor(math.sqrt(n))
	x = 1
	for j in range(1, nsq + 1):
		if n % j == 0:
			x = j
	print(int(n // x - x))


import math
t = int(input())
for i in range(t):
	k = int(input())
	r = math.sqrt(k)
	p = math.floor(math.sqrt(k))
	if r == p:
		print(0)
	else:
		l = []
		f = []
		for i in range(1, p + 1):
			if k % i == 0:
				x = k // i
				y = abs(x - i)
				f.append(y)
		print(min(f))


import math
for _ in range(int(input())):
	n = int(input())
	minimum = 1000000000
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			minimum = min(minimum, abs(i - n // i))
	print(minimum)


import math

def is_sqrt(num):
	if (num ** 0.5).is_integer():
		return True
	return False
for _ in range(int(input())):
	n = int(input())
	tmp = []
	mini = 9999999999
	if is_sqrt(n):
		print(0)
	else:
		for i in range(1, int(math.sqrt(n)) + 1):
			if n % i == 0:
				if abs(i - n / i) < mini:
					mini = abs(i - n / i)
		print(int(mini))


import math as m
for _ in range(int(input())):
	n = int(input())
	minimum = 10000000000.0
	n1 = int(m.sqrt(n) + 1)
	for i in range(1, n1):
		if n % i == 0:
			minimum = min(minimum, n // i - i)
	print(minimum)


import math
for _ in range(int(input())):
	n = int(input())
	factors = []
	ss = math.sqrt(n)
	sq = math.ceil(ss)
	for i in range(1, sq + 1):
		if n % i == 0:
			rr = n // i
			tt = (i, rr)
			factors.append(tt)
	diff = []
	for (a, b) in factors:
		diff.append(abs(a - b))
	diff.sort()
	print(diff[0])


for _ in range(int(input())):
	N = int(input())
	besti = 1
	i = 1
	while i * i <= N:
		if N % i == 0:
			besti = i
		i += 1
	print(int(N / besti - besti))


T = int(input())
j = 1
while j <= T:
	N = int(input())
	sqrt = int(N ** 0.5)
	for i in range(sqrt, 0, -1):
		if N % i == 0:
			print(abs(N // i - i))
			break
	j += 1


import math
t = int(input())
for i in range(t):
	n = int(input())
	mini = n
	for j in range(1, int(math.sqrt(n) + 1)):
		if n % j == 0:
			rem = n / j
			diff = abs(rem - j)
			if diff < mini:
				mini = diff
	print(int(mini))


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	for i in range(int(sqrt(n)), 0, -1):
		x = n % i
		if x == 0:
			y = n / i
			print(int(y - i))
			break


import math
t = int(input())
for _ in range(t):
	n = int(input())
	st = math.floor(n ** 0.5)
	for i in range(st, 0, -1):
		if n % i == 0:
			y = n // i
			print(y - i)
			break


import math
for tc in range(int(input())):
	N = int(input())
	m = float('inf')
	for i in range(1, int(math.sqrt(N)) + 1):
		if N % i == 0:
			q = N // i
			m = min(m, abs(q - i))
	print(m)


for i in range(int(input())):
	a = int(input())
	d = a
	for i in range(1, int(a ** 0.5) + 1):
		if a % i == 0:
			if abs(i - a // i) < d:
				d = abs(i - a // i)
	print(d)


import math
for _ in range(int(input())):
	n = int(input())
	li = []
	mn = n
	for i in range(int(math.sqrt(n + 1)), 0, -1):
		if n % i == 0:
			q = abs(n // i - i)
			mn = min(mn, q)
	print(mn)


import math
T = int(input())
for i in range(T):
	N = int(input())
	ans = N
	for j in range(1, int(math.sqrt(N)) + 1):
		if N % j == 0:
			A = N / j
			X = abs(j - A)
			if X < ans:
				ans = int(X)
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	for i in range(int(math.sqrt(n)), 0, -1):
		if n % i == 0:
			a = n // i
			ans = abs(a - i)
			break
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	k = math.floor(n ** 0.5)
	min = n - 1
	for i in range(1, k + 1):
		if n % i == 0:
			m = abs(n // i - i)
			if m < min:
				min = m
	print(min)


import math
for _ in range(int(input())):
	n = int(input())
	diff = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			n2 = n / i
			diff.append(int(abs(n2 - i)))
	print(min(diff))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	l = n
	k = int(n ** 0.5)
	for i in range(1, k + 1):
		if n % i == 0:
			l = min(l, abs(i - n // i))
	print(l)


import math

def Soluiton(n):
	v = int(math.sqrt(n))
	minDiff = 10 ** 9
	b = True
	for i in range(v, 0, -1):
		if n % i == 0:
			div = n // i
			minDiff = min(minDiff, abs(div - i))
			break
	return minDiff
for _ in range(int(input())):
	n = int(input())
	s = int(math.sqrt(n))
	if n == 1:
		print(0)
	elif n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		print(Soluiton(n))


from math import sqrt
for _ in range(int(input())):
	N = int(input())
	length = int(sqrt(N)) + 1
	while N % length:
		length -= 1
		if length == 1:
			break
	print(abs(length - N // length))


testcase = int(input())
for i in range(testcase):
	n = int(input())
	fnd = False
	diff = n - 1
	for j in range(int(n ** 0.5), 0, -1):
		if n % j == 0:
			if diff > abs(j - n / j):
				diff = abs(j - n / j)
	print(int(diff))


import math

def getMinimumFactorDifference(number):
	min_no = number
	for i in range(1, int(math.sqrt(number) + 1)):
		if number % i == 0:
			second_number = number / i
			diff = abs(second_number - i)
			if diff < min_no:
				min_no = diff
	return int(min_no)
testcase = int(input())
for case in range(testcase):
	number = int(input())
	print(getMinimumFactorDifference(number))


for _ in range(int(input())):
	n = int(input())
	mi = n - 1
	for i in range(int(n ** 0.5), 1, -1):
		if n % i == 0:
			mi = min(mi, abs(n // i - i))
	print(mi)


import math
T = int(input())
for tc in range(T):
	N = int(input())
	L = int(math.sqrt(N))
	Flag = True
	while Flag:
		if N % L == 0:
			dif = abs(L - N / L)
			Flag = False
		L -= 1
	print(int(dif))