Given N students sitting in a circle, distribute M candies to these students. The i_{th} student can take only i candies. If i_{th} student does not get the required amount of candies he will not take it. Distribute the candies starting from the 1st student and moving along the circle of students till you reach a student you can not give candies to. You need to find the amount of candies left.
Example 1:
Input:
N = 4, M = 11
Output: 0
Explanation: You first give 1 candy to 1st student, 
2 to 2nd , 3 to 3rd , 4 to 4th then again 1 to first. 
All candies are finished with none left out.
Example 2:
Input:
N = 4, M = 12
Output: 1
Explanation: You are left with only one candy.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function leftCandies() which takes two integers n and m as input parameters and returns an integer denoting the amount of candies left.
 
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ N ≤ 10^{9}
1 ≤ M ≤ 10^{18}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



def leftCandies(n, m):

    # code here

Solutions:
def leftCandies(n, m):
	candy_left = m % (n * (n + 1) // 2)
	start = 0
	end = n
	while start <= end:
		mid = (start + end) // 2
		curr = mid * (mid + 1) // 2
		if curr == candy_left:
			return 0
		elif curr > candy_left:
			end = mid - 1
		else:
			start = mid + 1
	return candy_left - end * (end + 1) // 2


def leftCandies(n, m):
	round = n * (n + 1) // 2
	m = m % round
	low = 0
	high = n
	while low < high:
		mid = (low + high) // 2
		if mid * (mid + 1) // 2 <= m:
			low = mid + 1
		else:
			high = mid
	return m - low * (low - 1) // 2


def leftCandies(n, m):
	l = m % (n * (n + 1) // 2)
	a = 0
	b = n
	while a <= b:
		mid = (a + b) // 2
		c = mid * (mid + 1) // 2
		if c == l:
			return 0
		elif c > l:
			b = mid - 1
		else:
			a = mid + 1
	return l - b * (b + 1) // 2


import math

def leftCandies(n, m):
	sum1 = n * (n + 1) / 2
	count1 = m // sum1
	total = int(count1) * int(sum1)
	m = m - total
	k = (-1 + math.sqrt(1 + 8 * m)) / 2
	if int(k) == k:
		return 0
	return int(m - int(k) * (int(k) + 1) / 2)


def leftCandies(n, m):
	summ = (n + 1) * n // 2
	m = m % summ
	l = 1
	r = n
	mid = 0
	while l <= r:
		mid = (l + r) // 2
		summ = (mid + 1) * mid // 2
		if summ < m:
			l = mid + 1
		elif summ > m:
			r = mid - 1
		else:
			return 0
	if summ > m:
		return m - (l - 1) * l // 2
	else:
		return m - (r + 1) * r // 2


import math

def leftCandies(n, m):
	actualM = m % sumToN(n)
	lastStudent = math.floor((math.sqrt(1 + 8 * actualM) - 1) / 2)
	return actualM - sumToN(lastStudent)

def sumToN(n):
	return int(n * (n + 1) / 2)


def leftCandies(n, m):
	candies = m
	if n * (n + 1) // 2 <= m:
		candies = m % (n * (n + 1) // 2)
	if candies == 0 or candies == 1:
		return 0
	low = 1
	high = n
	while low <= high:
		mid = (low + high) // 2
		if mid * (mid + 1) // 2 <= candies:
			low = mid + 1
			ans = mid
		else:
			high = mid - 1
	return candies - ans * (ans + 1) // 2


def leftCandies(n, m):
	distributed = n * (n + 1) // 2
	m = m % distributed
	left = 1
	right = n
	mid = 0
	while left <= right:
		mid = (left + right) // 2
		distributed = mid * (mid + 1) // 2
		if distributed < m:
			left = mid + 1
		elif distributed > m:
			right = mid - 1
		else:
			return 0
	if distributed > m:
		return m - left * (left - 1) // 2
	else:
		return m - right * (right + 1) // 2


def leftCandies(n, m):
	s = n * (n + 1) // 2
	if m % s == 0:
		return 0
	else:
		re = m % s
		l = 0
		r = n
		while l <= r:
			m = (l + r) // 2
			curr = m * (m + 1) // 2
			if curr == re:
				return 0
			elif re < curr:
				r = m - 1
			else:
				l = m + 1
		return re - r * (r + 1) // 2


def leftCandies(n, m):
	l = m % (n * (n + 1) // 2)
	s = 0
	e = n
	while s <= e:
		m = (s + e) // 2
		c = m * (m + 1) // 2
		if c == l:
			return 0
		elif c > l:
			e = m - 1
		else:
			s = m + 1
	return l - e * (e + 1) // 2


from math import *

def leftCandies(n, m):
	x = m % (n * (n + 1) // 2)
	a = (sqrt(8 * x + 1) - 1) // 2
	b = a * (a + 1) // 2
	return int(x - b)


def leftCandies(n, m):
	total = n * (n + 1) // 2
	left = m % total
	start = 0
	end = n
	while start <= end:
		mid = (start + end) // 2
		curr = mid * (mid + 1) // 2
		if curr == left:
			return 0
		elif curr > left:
			end = mid - 1
		else:
			start = mid + 1
	return left - end * (end + 1) // 2


def leftCandies(n, m):
	import math
	rc = int(n * (n + 1) / 2)
	rem = m % rc
	nmax = int((math.sqrt(8 * rem + 1) - 1) / 2)
	dc = int(nmax * (nmax + 1) / 2)
	return rem - dc