Given N candies and K people. In the first turn, the first person gets 1 candy, the second gets 2 candies, and so on till K people. In the next turn, the first person gets K+1 candies, the second person gets K+2 candies and so on. If the number of candies is less than the required number of candies at every turn, then the person receives the remaining number of candies. Find the total number of candies every person has at the end.
 
Example 1:
Input:
N = 7, K = 4
Output:
1 2 3 1
Explanation:
At the first turn, the fourth person
has to be given 4 candies, but there is
only 1 left, hence he takes only one. 
Example 2:
Input:
N = 10, K = 3
Output :
5 2 3
Explanation:
At the second turn first one receives
4 and then we have no more candies left. 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function distributeCandies() which takes 2 integers N and K as input and returns a list, where the ith integer denotes the number of candies the ith person gets.
Expected Time Complexity: O(logN+K)
Expected Auxiliary Space: O(K)
Constraints:
1 ≤ N ≤ 10^{8}
1 ≤ K ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Mathematics

Starter code: #User function Template for python3

class Solution:
    def distributeCandies(self, N, K):
        # code here 

Solutions:
class Solution:

	def distributeCandies(self, N, K):
		ans = [0] * K
		x = 0
		while N > 0:
			ans[x % K] += min(x + 1, N)
			x += 1
			N -= x
		return ans


class Solution:

	def distributeCandies(self, N, K):
		ans = [0] * K
		i = 1
		p = 0
		while N > 0:
			if p == K:
				p = 0
			ans[p] += min(i, N)
			p += 1
			N -= i
			i += 1
		return ans


class Solution:

	def distributeCandies(self, target, num):
		value = 1
		a = [0] * num
		x = 0
		while int(target) >= int(value):
			if x == num:
				x = 0
			a[x] = a[x] + value
			x = x + 1
			target = target - value
			value = value + 1
			if target < value:
				if x == num:
					a[0] = a[0] + target
				else:
					a[x] += target
		return a


class Solution:

	def distributeCandies(self, N, K):
		n = N
		ans = [0 for _ in range(K)]
		give = 1
		while n > 0:
			for i in range(K):
				if give <= n:
					ans[i] += give
				else:
					ans[i] += n
					n = 0
					break
				n -= give
				give += 1
		return ans


class Solution:

	def distributeCandies(self, N, K):
		no_of_candies = [0 for _ in range(K)]
		n_times = ((1 + 8 * N) ** 0.5 - 1) / 2
		r = int(n_times) % K
		q = int(n_times) // K
		for i in range(K):
			c = K * q * (q - 1) // 2 + q * (i + 1)
			no_of_candies[i] = c
			N -= c
		for i in range(r):
			c = q * K + i + 1
			no_of_candies[i] += c
			N -= c
		if n_times > int(n_times):
			no_of_candies[r] += N
		return no_of_candies


class Solution:

	def distributeCandies(self, N, K):
		arr = [0] * K
		i = 0
		candies = 1
		while N > 0:
			arr[i] += min(N, candies)
			N -= candies
			candies += 1
			if i == K - 1:
				i = 0
			else:
				i += 1
		return arr


class Solution:

	def distributeCandies(self, N, K):
		output = [0] * K
		i = 0
		while N > i:
			output[i % K] += i + 1
			i += 1
			N -= i
		output[i % K] += N
		return output


class Solution:

	def distributeCandies(self, n, k):
		ans = [0] * k
		t = k
		i = 0
		cycle = False
		temp = 0
		while n > 0:
			ans[temp % k] += min(temp + 1, n)
			temp += 1
			n -= temp
		return ans


class Solution:

	def distributeCandies(self, N, K):
		arr = [0] * K
		i = 0
		j = 1
		while N > 0:
			if i == K:
				i = 0
			if N >= j:
				arr[i] += j
				N -= j
			else:
				arr[i] += N
				N = 0
			i += 1
			j += 1
		return arr


class Solution:

	def distributeCandies(self, N, k):
		l = [0] * k
		c = 1
		i = 0
		p = k
		if k == 1:
			return [N]
		while True:
			if k <= 0:
				i = 0
				k = p
			l[i] += c
			N -= c
			c += 1
			i += 1
			k -= 1
			if N <= 0:
				return l
			if c > N:
				c = N


class Solution:

	def distributeCandies(self, N, K):
		ans = [0 for i in range(K)]
		count = 1
		index = 0
		incrMul = 1
		while N >= 0:
			if index == K:
				index = 0
				count = incrMul * K + 1
				incrMul += 1
				continue
			if count > N:
				ans[index] += N
				break
			else:
				ans[index] += count
				N -= count
			index += 1
			count += 1
		return ans


class Solution:

	def distributeCandies(self, N, K):
		v = [0] * K
		r = N
		i = 0
		while r > 0:
			d = i % K
			if i >= r:
				v[d] += r
			else:
				v[d] += i + 1
			r -= i + 1
			i += 1
		return v


class Solution:

	def distributeCandies(self, N, k):
		ans = [0] * k
		t = 1
		rem = N
		ind = 0
		rep = 1
		while t < N:
			ans[ind] += t
			N -= t
			t += 1
			ind = ind + 1
			if ind == k:
				ind = 0
				t = k * rep + 1
				rep += 1
		ans[ind] += N
		return ans


class Solution:

	def distributeCandies(self, N, K):
		k = K
		n = N
		count = 0
		ind = 1
		l = []
		arr = [0 for i in range(k)]
		while n > 0:
			f1 = (ind - 1) * k
			f2 = ind * k
			sum1 = f1 * (f1 + 1) // 2
			sum2 = f2 * (f2 + 1) // 2
			res = sum2 - sum1
			if res <= n:
				count += 1
				n -= res
				ind += 1
			else:
				i = 0
				term = (ind - 1) * k + 1
				while n > 0:
					if term <= n:
						arr[i] = term
						i += 1
						n -= term
						term += 1
					else:
						arr[i] = n
						i += 1
						n = 0
		for i in range(k):
			arr[i] += count * (i + 1) + k * (count * (count - 1)) // 2
		for i in range(k):
			l.append(arr[i])
		return l


class Solution:

	def binarysearch(self, l, r, k):
		if l <= r:
			mid = (l + r) // 2
			if mid * (mid + 1) // 2 <= k:
				return self.binarysearch(mid + 1, r, k)
			else:
				return self.binarysearch(l, mid - 1, k)
		return r // k

	def distributeCandies(self, n, k):
		count = 0
		ind = 1
		arr = [0] * k
		low = 0
		high = n
		while low <= high:
			mid = low + high >> 1
			sum = mid * (mid + 1) >> 1
			if sum <= n:
				count = int(mid / k)
				low = mid + 1
			else:
				high = mid - 1
		last = count * k
		n -= int(last * (last + 1) / 2)
		i = 0
		term = count * k + 1
		while n:
			if term <= n:
				arr[i] = term
				i += 1
				n -= term
				term += 1
			else:
				arr[i] += n
				n = 0
		for i in range(k):
			arr[i] += count * (i + 1) + int(k * (count * (count - 1)) / 2)
		return arr


class Solution:

	def distributeCandies(self, N, K):
		counter = 0
		res = [0] * K
		candies = 1
		x = 0
		while N > 0:
			val = min(candies, N)
			res[x % K] += min(candies, N)
			candies += 1
			N -= val
			x += 1
		return res


class Solution:

	def distributeCandies(self, N, K):
		arr = [0] * K
		i = 0
		noc = N
		turn = 0
		while noc > 0:
			can = turn * K + i + 1
			if noc >= can:
				arr[i] += can
			else:
				arr[i] += noc
				break
			noc -= can
			i += 1
			if i == K:
				i = 0
				turn += 1
		return arr


class Solution:

	def distributeCandies(self, N, K):
		n = 1
		output = [0] * K
		last = 0
		while N > 0:
			if n < N:
				last = n % K
				output[last - 1] += n
				N -= n
				n += 1
			else:
				if last == K:
					output[0] += N
				else:
					output[last] += N
				return output


class Solution:

	def distributeCandies(self, N, K):
		res = [0] * K
		j = 0
		for i in range(1, N + 1):
			x = i - 1
			s = x * (x + 1) // 2
			if i >= N - s:
				res[j] += N - s
				break
			res[j] += i
			j = (j + 1) % K
		return res


class Solution:

	def distributeCandies(self, N, K):
		arr = [0] * K
		count = 1
		turn = 0
		person = 1
		while N > 0:
			person = count % K
			if person == 0:
				person = K
				turn = count // K - 1
			else:
				turn = count // K
			if turn * K + person <= N:
				arr[person - 1] += turn * K + person
				N -= turn * K + person
				count += 1
			else:
				arr[person - 1] += N
				N = 0
		return arr


class Solution:

	def distributeCandies(self, N, K):
		list_new = []
		for i in range(K):
			list_new.append(0)
		x = 0
		while N > 0:
			list_new[x % K] += min(x + 1, N)
			x += 1
			N -= x
		return list_new


class Solution:

	def distributeCandies(self, N, K):
		result = [0] * K
		(idx, candies_count) = (0, 1)
		while N > 0:
			result[idx] += candies_count
			N -= candies_count
			(idx, candies_count) = (idx + 1, candies_count + 1)
			if idx == K:
				idx = 0
			if candies_count > N:
				candies_count = N
		return result


class Solution:

	def distributeCandies(self, N, K):
		i = 0
		s = 1
		arr = [0] * K
		while 1:
			if i == K:
				i = 0
			arr[i] = arr[i] + s
			N = N - s
			s = s + 1
			if s > N:
				if i + 1 != K:
					arr[i + 1] = arr[i + 1] + N
				else:
					arr[0] = arr[0] + N
				break
			i = i + 1
		return arr


class Solution:

	def distributeCandies(self, N, K):
		arr = [0] * K
		c = 0
		p = 1
		while N > 0:
			c %= K
			if N >= p:
				arr[c] += p
			else:
				arr[c] += N
			N -= p
			p += 1
			c += 1
		return arr


class Solution:

	def distributeCandies(self, N, K):
		l = 0
		r = N
		turns = 0
		ans = [0] * K
		while l <= r:
			mid = l + r >> 1
			s = mid * (mid + 1) >> 1
			if s <= N:
				turns = mid // K
				l = mid + 1
			else:
				r = mid - 1
		last = turns * K
		N -= last * (last + 1) >> 1
		nxt = last + 1
		i = 0
		while N:
			if nxt <= N:
				ans[i] += nxt
				i += 1
				N -= nxt
				nxt += 1
			else:
				ans[i] = N
				N = 0
		for i in range(K):
			c = i + 1
			c += c + (turns - 1) * K
			c = c * turns >> 1
			ans[i] += c
		return ans


class Solution:

	def distributeCandies(self, N, K):
		li = [0] * K
		i = 0
		while N > 0:
			li[i % K] += min(i + 1, N)
			i += 1
			N = N - i
		return li


class Solution:

	def distributeCandies(self, N, K):
		li = [0] * K
		n = N
		M = K
		j = 0
		for i in range(1, N + 1):
			if i <= n:
				if j < M:
					li[j] = li[j] + i
					j = j + 1
				else:
					j = 0
					li[j] = li[j] + i
					j = j + 1
				n = n - i
			else:
				li[j % M] += n
				break
		return li


class Solution:

	def distributeCandies(self, N, K):
		i = 0
		c = 0
		l = [0 for i in range(K)]
		while N > 0:
			i = i % K
			if N <= c:
				l[i] += N
				break
			c += 1
			l[i] += c
			i += 1
			N = N - c
		return l


class Solution:

	def distributeCandies(self, n, k):
		arr = [0] * k
		cnt = 1
		while n > 0:
			n -= cnt
			if n < 0:
				arr[cnt % k - 1] += n + cnt
				break
			arr[cnt % k - 1] += cnt
			cnt += 1
		return arr


class Solution:

	def distributeCandies(self, N, K):
		candies = N
		num_people = K
		a = []
		for i in range(num_people):
			a.append(0)
		sum1 = 1
		while candies > 0:
			for i in range(num_people):
				if candies - sum1 >= 0:
					a[i] = a[i] + sum1
					candies = candies - sum1
				else:
					a[i] = a[i] + candies
					candies = 0
				sum1 = sum1 + 1
		return a
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		res = ob.distributeCandies(N, K)
		for i in res:
			print(i, end=' ')
		print()


class Solution:

	def distributeCandies(self, k, n):
		a = [0] * n
		i = 0
		curk = k
		while i < k:
			tmp = min(curk, i + 1)
			a[i % n] += tmp
			curk -= tmp
			if curk == 0:
				break
			i += 1
		return a
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		res = ob.distributeCandies(N, K)
		for i in res:
			print(i, end=' ')
		print()


class Solution:

	def distributeCandies(self, N, K):
		i = 0
		res = [0] * K
		while N > 0:
			res[i % K] = res[i % K] + min(N, i + 1)
			N = N - (i + 1)
			i = i + 1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		res = ob.distributeCandies(N, K)
		for i in res:
			print(i, end=' ')
		print()


class Solution:

	def distributeCandies(self, N, K):
		res = []
		i = 1
		while N > 0:
			if N >= i:
				res.append(i)
				N -= i
				i += 1
			else:
				res.append(N)
				N = 0
		result = [0] * K
		for i in range(len(res)):
			result[i % K] += res[i]
		return result
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		res = ob.distributeCandies(N, K)
		for i in res:
			print(i, end=' ')
		print()


class Solution:

	def distributeCandies(self, input1, input2):
		low = 0
		high = input1
		temp = [0] * input2
		counter = 0
		while low <= high:
			mid = low + high >> 1
			tempsum = mid * (mid + 1) >> 1
			if tempsum <= input1:
				counter = mid // input2
				low = mid + 1
			else:
				high = mid - 1
		last = counter * input2
		input1 -= last * (last + 1) >> 1
		x = counter * input2 + 1
		i = 0
		while input1:
			if x <= input1:
				temp[i] = x
				i += 1
				input1 -= x
				x += 1
			else:
				temp[i] += input1
				input1 = 0
		for i in range(input2):
			temp[i] = temp[i] + ((input2 * (counter * (counter - 1)) >> 1) + counter * (i + 1))
		return temp
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		res = ob.distributeCandies(N, K)
		for i in res:
			print(i, end=' ')
		print()


class Solution:

	def distributeCandies(self, n, k):
		count = 0
		ind = 1
		arr = [0] * k
		low = 0
		high = n
		while low <= high:
			mid = low + high >> 1
			sum = mid * (mid + 1) >> 1
			if sum <= n:
				count = int(mid / k)
				low = mid + 1
			else:
				high = mid - 1
		last = count * k
		n -= int(last * (last + 1) / 2)
		i = 0
		term = count * k + 1
		while n:
			if term <= n:
				arr[i] = term
				i += 1
				n -= term
				term += 1
			else:
				arr[i] += n
				n = 0
		for i in range(k):
			arr[i] += count * (i + 1) + int(k * (count * (count - 1)) / 2)
		return arr
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		res = ob.distributeCandies(N, K)
		for i in res:
			print(i, end=' ')
		print()


class Solution:

	def distributeCandies(self, k, n):
		a = [0] * n
		i = 0
		curk = k
		while i < k:
			tmp = min(curk, i + 1)
			a[i % n] += tmp
			curk -= tmp
			if curk == 0:
				break
			i += 1
		return a


class Solution:

	def distributeCandies(self, N, K):
		count = 0
		ind = 1
		arr = [0] * K
		low = 0
		high = N
		while low <= high:
			mid = low + high >> 1
			sum = mid * (mid + 1) >> 1
			if sum <= N:
				count = int(mid / K)
				low = mid + 1
			else:
				high = mid - 1
		last = count * K
		N -= int(last * (last + 1) / 2)
		i = 0
		term = count * K + 1
		while N:
			if term <= N:
				arr[i] = term
				i += 1
				N -= term
				term += 1
			else:
				arr[i] += N
				N = 0
		for i in range(K):
			arr[i] += count * (i + 1) + int(K * (count * (count - 1)) / 2)
		ans = []
		for i in range(K):
			ans.append(arr[i])
		return ans


class Solution:

	def distributeCandies(self, N, K):
		ans = [0] * K
		round = 0
		while True:
			for i in range(K):
				req = round * K + i + 1
				if req > N:
					ans[i] += N
					return ans
				ans[i] += req
				N -= req
			round += 1


class Solution:

	def distributeCandies(self, N, K):
		l = [0] * K
		val = 1
		i = 1
		count = 1
		while val <= N:
			l[i - 1] += count
			if i % K == 0:
				i = 0
			i += 1
			count += 1
			val += count
		l[i - 1] += count - (val - N)
		return l


class Solution:

	def distributeCandies(self, N, K):
		l = [0] * K
		i = 0
		n = 1
		while N > 0:
			if i == K:
				i = 0
			if N < n:
				l[i] += N
				N -= N
			else:
				l[i] += n
				N -= n
				n += 1
			i += 1
		return l


class Solution:

	def distributeCandies(self, N, K):
		lst = []
		for i in range(K):
			lst.append(0)
		candies = N
		turn = 1
		flag = True
		while flag:
			for i in range(K):
				amount = (turn - 1) * K + (i + 1)
				if amount <= candies:
					lst[i] = lst[i] + amount
					candies = candies - amount
				else:
					lst[i] = lst[i] + candies
					flag = False
					break
			turn = turn + 1
		return lst


class Solution:

	def distributeCandies(self, n, k):
		val = 1
		idx = 0
		res = [0 for i in range(k)]
		while n > 0:
			res[idx] += val
			idx += 1
			n -= val
			val += 1
			if idx == k:
				idx = 0
			if val > n:
				val = n
		return res


class Solution:

	def distributeCandies(self, N, K):
		out = [0 for i in range(K)]
		i = 0
		while N > 0:
			out[i % K] += min(N, i + 1)
			N -= i + 1
			i += 1
		return out


class Solution:

	def distributeCandies(self, N, K):
		turn = 0
		left = N
		out = [0 for i in range(K)]
		while left > 0:
			for i in range(K):
				if left <= 0:
					break
				req = turn * K + i + 1
				if req >= left:
					out[i] += left
				else:
					out[i] += req
				left -= req
			turn += 1
		return out


class Solution:

	def distributeCandies(self, N, K):
		a = [0] * K
		i = 0
		p = 1
		c = 0
		while N > 0:
			if p == 1:
				if N >= i + 1:
					a[i] = a[i] + i + 1
					N -= i + 1
				else:
					a[i] = a[i] + N
					break
			elif p == 0:
				if N >= i + 1 + K * c:
					a[i] = a[i] + (i + 1 + K * c)
					N -= i + 1 + K * c
				else:
					a[i] = a[i] + N
					break
			i = i + 1
			if i == K:
				i = 0
				p = 0
				c = c + 1
		return a


class Solution:

	def distributeCandies(self, N, K):
		arr = [0] * K
		t = 0
		while N > 0:
			for i in range(K):
				val = t * K + (i + 1)
				if N <= val:
					arr[i] += N
					N -= val
					break
				else:
					arr[i] += val
					N -= val
			t += 1
		return arr


class Solution:

	def distributeCandies(self, n, k):
		l = 0
		h = n
		x = 0
		while l <= h:
			mid = l + (h - l) // 2
			cnt = mid * (mid + 1) // 2
			if cnt > n:
				h = mid - 1
			elif cnt <= n:
				x = mid // k
				l = mid + 1
		last = k * x
		rem = n - last * (last + 1) // 2
		res = [0] * k
		i = 0
		while rem > 0:
			cnt = last + i + 1
			if cnt <= rem:
				res[i] = cnt
				rem = rem - cnt
				i += 1
			else:
				res[i] = res[i] + rem
				break
		i = 0
		while i < k:
			res[i] = res[i] + ((i + 1) * x + k * x * (x - 1) // 2)
			i += 1
		return res


class Solution:

	def distributeCandies(self, N, K):
		candy_list = [0] * K
		low = 0
		high = N
		while low <= high:
			mid = (low + high) // 2
			sum1 = mid * (mid + 1) // 2
			if sum1 <= N:
				count = int(mid / K)
				low = mid + 1
			else:
				high = mid - 1
		last = count * K
		N -= int(last * (last + 1) / 2)
		term = count * K + 1
		i = 0
		while N:
			if term <= N:
				candy_list[i] = term
				i += 1
				N -= term
				term += 1
			else:
				candy_list[i] = N
				N = 0
		for i in range(K):
			candy_list[i] += count * (i + 1) + int(K * (count * (count - 1)) / 2)
		return candy_list


class Solution:

	def distributeCandies(self, N, K):
		vect = [0 for _ in range(K)]
		cnt = 1
		idx = 0
		while N > 0:
			if N >= cnt:
				vect[idx % K] += cnt
			else:
				vect[idx % K] += N
			N -= cnt
			cnt += 1
			idx += 1
		return vect


class Solution:

	def distributeCandies(self, n, k):
		ans = [0] * k
		res = 1
		i = 0
		while n > 0:
			if n >= res:
				ans[i % k] += res
			else:
				ans[i % k] += n
			n -= res
			res += 1
			i += 1
		return ans


class Solution:

	def distributeCandies(self, N, K):
		ans = [0 for i in range(K)]
		j = 0
		while N > 0:
			for i in range(K):
				j += 1
				N -= j
				if N <= 0:
					ans[i] += N + j
					break
				else:
					ans[i] += j
		return ans


class Solution:

	def distributeCandies(self, N, K):
		t = N
		c = 1
		l = [0 for i in range(K)]
		flag = True
		while flag:
			for i in range(K):
				if t < c:
					l[i] += t
					flag = False
					break
				l[i] += c
				t -= c
				c += 1
		return l


class Solution:

	def distributeCandies(self, N, K):
		out = [0] * K
		i = 0
		loop = 0
		while N > 0:
			if i == K:
				i = 0
				loop += 1
			curcandy = loop * K + (i + 1)
			if N - curcandy < 0:
				out[i] += N
			else:
				out[i] += curcandy
			i += 1
			N -= curcandy
		return out


class Solution:

	def distributeCandies(self, N, K):
		i = 0
		prev = 0
		res = [0] * K
		while N > 0:
			curr = prev + 1
			if curr >= N:
				res[i] += N
				break
			res[i] += curr
			N = N - curr
			prev = curr
			i = (i + 1) % K
		return res


class Solution:

	def distributeCandies(self, N, K):
		arr = [0 for i in range(K + 1)]
		i = 0
		empty = False
		while not empty and N > 0:
			for j in range(1, K + 1):
				if N > i * K + j:
					arr[j] += i * K + j
					N -= i * K + j
				else:
					arr[j] += N
					N -= N
					empty = True
			i += 1
		return arr[1:]


class Solution:

	def is_valid(self, c_t, N, K):
		val = c_t * K * (K + 1 + (c_t - 1) * K) // 2
		return val >= N

	def distributeCandies(self, N, K):
		left = 1
		right = N
		while left < right:
			mid = left + (right - left) // 2
			if self.is_valid(mid, N, K):
				right = mid
			else:
				left = mid + 1
		t = left
		prev_t = t - 1
		candies = [0] * K
		for i in range(K):
			candies[i] = (i + 1) * prev_t + prev_t * (prev_t - 1) // 2 * K
		rem_n = N - sum(candies)
		for i in range(K):
			if rem_n <= 0:
				break
			curr_cand = min(rem_n, i + 1 + (t - 1) * K)
			candies[i] += curr_cand
			rem_n -= curr_cand
		return candies


class Solution:

	def distributeCandies(self, N, K):
		lst = []
		for i in range(K):
			lst.append(0)
		i = 0
		j = 1
		while N >= 0:
			if N >= j:
				lst[i % K] += j
			else:
				lst[i % K] += N
			N -= j
			i += 1
			j += 1
		return lst