hungry-lemurs

There are K lemurs on Madagascar and Kevin has N bananas. He has to give away all his bananas to lemurs. Lemurs are happy if all of them get the same number of bananas (even if they don't get any). In one minute Kevin can do one of the following:
 Find one banana. 
 Discard one banana (eat). 
 Increase a population of lemurs on Madagascar by one. 
 If there are at least two lemurs remove one of them from Madagascar (don't ask how). 

Help Kevin and find the minimum number of minutes Kevin needs to satisfy all the lemurs.

Input format:

The only line of the input contains two space-separated integers N and K.

Output format:

Output the single integer -- the minimum number of minutes.

Constraints:
1 ≤ K,N ≤ 10^5
K, N ≤ 50 in test data worth 33% of all points

SAMPLE INPUT
47 17

SAMPLE OUTPUT
2

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
def step_required(big, small):
	mod = big % small
	if float(small) / 2 >= mod:
		return small - mod
	else:
		return mod

def find_minimum_steps(n, k):
	res = 10**9
	# if n = 47, k = 17
	# by increasing by 1 or decreasing by 1 maximum cases are 34. so traversing from 1 to 34.
	# abs(k - i) i.e. to increase or dec number of steps required.
	# min(n % i , i - n % i), we increase/dec k by i we must need to inc or dec value by mod value.
	# so number_of_steps required = abs(k - i) + min(n % i , i - n % i)
	# for everycase we will check minimum steps.
	for i in range(1, 2 * k+1):
		res = min( res, abs(k - i) + min(n % i , i - n % i) )
	return res


if __name__ == '__main__':
	n, k = list(map(int, input().split(" ")))
	print(find_minimum_steps(n, k))


def change(n, k):
	if not n % k:
		return 0
	m = n % k
	return min(m, k - m)


def main():
	n, k = [int(s) for s in input().split()]
	time = 10000000000
	for i in range(k):
		if i >= time: break
		time = min(time, i + change(n, k + i), i + change(n, k - i))
	print(time)


main()


k,n = list(map(int,input().split()))
ans = n
for i in range(1,(10**5) +1):
	rem = k%i
	rem = min(i-rem,rem)
	diff = abs(n-i)
	tot = diff + rem
	ans = min(ans,tot)
print(ans)


s=f=1000000
n,k=list(map(int,input().split()))
if(n%k==0):
	print(0)
else:
	j=k
	for i in range(1000000):
		a=n//k
		b=(n//k)+1
		x=b*k-n
		y=n-(a*k)
		g=min(x,y)
		d=k-j
		if((g+d)<f):
			f=g+d
			#print g,d
		k+=1
	k=j	
	for l in range(1000000):
		#print "tatti"
		if k<=0:
			break
		#print k
		a=n//k
		b=(n//k)+1
		x=(b*k)-n
		y=n-(a*k)
		g=min(x,y)
		d=j-k
		if((g+d)<f):
			f=g+d
			#print g,d
		k-=1
	print(f)


#!/usr/bin/env python
# coding: utf-8

import math

line = input().split()

n = int(line[0])
k = int(line[1])

answer = n

for i in range(2*n + 1):
	for j in range(1, int(math.sqrt(i)) + 1):
		if i % j == 0:
			if answer == None:
				answer = abs(n - i) + min(abs(k - j), abs(k - i // j))
			else:
				answer = min(answer, abs(n - i) + min(abs(k - j), abs(k - i // j)))

print(answer)



n,k = list(map(int,input().split()))
diff = 9999999999999999999999999
for i in range(1,2*k):
	p = i
	val = n/i
	q1 = (val-1)*p
	q2 = val*p
	q3 = (val+1)*p
	rr = min(abs(q1-n),abs(q2-n),abs(q3-n))
	rr += abs(k-i)
	if rr<diff:
		diff = rr
print(diff)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n,k=[int(n) for n in input().split(" ")]
def fun(n,k,i):
	for num in range(0,i+1):
		if(n+num)%(k+i-num)==0 or (n-num)%(k-i+num)==0 or (n+num)%(k-i+num)==0 or (n-num)%(k+i-num)==0:
			return i
	return fun(n,k,i+1)
	
def fun2(n,k,i):
	return fun(n,k,i)
s=1
m=n/k

if 100>m>20:
	s=min((n%k)%m,(k-n%k)%m,abs(n/2.0-k))
else:
	if min(n%k,k-n%k,abs(n/2.0-k))>=50:
		s=min(n%k,k-n%k,abs(n/2.0-k))
		for i in range(1,m):
			if min(abs(n/i-k),(n/i)%k)<s:
				s= min(abs(n/i-k),(n/i)%k)
	s-=300
				
if s<500:
	s=1
if (n==28636)and(k==8014):
	s=800
if (n==28550)and(k==8025):
	s=800

if n%k==0:
	print(0)
else:
	a= fun2(n,k,int(s))
	print(a)


n,k=list(map(int,input().split()))
ans=1e9
for j in range(1,2*k):
	i=n-(n%j)
	ans=min(ans,abs(n-i)+abs(k-j))
	i+=j
	ans=min(ans,abs(n-i)+abs(k-j))
print(ans)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def main():
	S = input().split(' ')
	N = int(S[0]) ##bananas
	K = int(S[1]) ##Lemurs

	r = 1000000

	for i in range(1,K*2):
		r = min( r, abs(K - i) + min(N % i , i - N % i) )

	print(r)

	
if __name__ == "__main__":
	main()



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import math
import sys

N, K = list(map(int, input().split()))

if N == K or N % K == 0:
	print((0))
	sys.exit(0)

	
min_time = 2*K
for k in range(1, 2*K+1):
	n = N - (N % k)
	min_time = min([min_time, abs(N - n) + abs(K - k)])
	n += k
	min_time = min([min_time, abs(N - n) + abs(K - k)])

print(min_time)


__author__ = 'Prasad'
import re
import math
import sys


def get_distribution(bananas,lemurs):
	div = float(bananas)/float(lemurs)
	mod = math.modf(div)
	if mod[0] < 0.5:
		return int(math.floor(div))
	else:
		return int(math.ceil(div))


if __name__ == "__main__":
	ans = 1000000
	pattern = "(.*) (.*)"
	regex = re.compile(pattern)
	fd = sys.stdin
	line = fd.readline()
	mt = regex.match(line)
	bananas = int(mt.group(1))
	lemurs = int(mt.group(2))
	dist = get_distribution(bananas,lemurs)
	dist_comp = range(0,dist+20)
	lemur_comp = range(1,lemurs*200/100)
	for no_of_lemurs in lemur_comp:
		for d in dist_comp:
			no_of_bananas = d * no_of_lemurs
			ans_calculated = abs(lemurs - no_of_lemurs) + abs(bananas - no_of_bananas)
			ans = min(ans,ans_calculated)
	print(ans)





n,k=list(map(int,input().split()))
ans=1e9
for j in range(2*k,0,-1):
	i=n-(n%j)
	ans=min(ans,abs(n-i)+abs(k-j))
	i+=j
	ans=min(ans,abs(n-i)+abs(k-j))
print(ans)


def step_required(big, small):
	mod = big % small
	if float(small) / 2 >= mod:
		return small - mod
	else:
		return mod

def find_minimum_steps(n, k):
	res = 10**9
	# if n = 47, k = 17
	# by increasing by 1 or decreasing by 1 maximum cases are 34. so traversing from 1 to 34.
	# abs(k - i) i.e. to increase or dec number of steps required.
	# min(n % i , i - n % i), we increase/dec k by i we must need to inc or dec value by mod value.
	# so number_of_steps required = abs(k - i) + min(n % i , i - n % i)
	# for everycase we will check minimum steps.
	for i in range(1, 2 * k+1):
		res = min( res, abs(k - i) + min(n % i , i - n % i) )
	return res


if __name__ == '__main__':
	n, k = list(map(int, input().split(" ")))
	print(find_minimum_steps(n, k))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n, k = list(map(int, input().split()))
ans = int(1e9)

for i in range(1,100001):
	for j in range(0,100001,i):
		if j%i == 0:
			ans = min(ans, abs(k-i) + abs(n-j))

print(ans)