In the game of Restricted Pacman, an infinite linear path is given. Pacman has to start at position 0 and eat as many candies as possible. In one move he can only jump a distance of either M or N.  If M and N are coprime numbers, find how many candies will be left on the board after the game is over.
Note: The result is always finite as after a point X every index in the infinite path can be visited. 
Example 1:
Input: M = 2, N = 5
Output: 2
Explanation: From index 0, the indices that 
can be visited are
0 + 2 = 2
0 + 2 + 2 = 4
0 + 5 = 5
0 + 2 + 2 + 2 = 6
0 + 2 + 5 = 7
0 + 2 + 2 + 2 + 2 = 8
0 + 2 + 2 + 5 = 9
0 + 5 + 5 = 10
and so on.
1 and 3 are the only indices that cannot be 
visited. Therefore the candies at these two 
positions will be left on the board. 
Example 2:
Input: M = 2, N = 7
Output: 3 
Example 3:
Input: M = 25, N = 7
Output: 72
Your Task:  
You don't need to read input or print anything. Complete the function candies() which take M and N as input parameters and return the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 < M, N ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Mathematics

Starter code: #User function Template for python3

class Solution: 
    def candies(self, m,n): 
        # Your code goes here 

Solutions:
import math
from collections import deque

class Solution:

	def candies(self, m, n):
		ma = m * n // math.gcd(n, m)
		marked = [0] * ma
		marked[0] = 1
		q = deque()
		q.append(0)
		while len(q) > 0:
			curr = q.popleft()
			if curr + m < ma and marked[curr + m] == 0:
				marked[curr + m] = 1
				q.append(curr + m)
			if curr + n < ma and marked[curr + n] == 0:
				marked[curr + n] = 1
				q.append(curr + n)
		return marked.count(0)


class Solution:

	def candies(self, m, n):
		maxi = m * n
		setti = set()
		for i in range(m + 1):
			for j in range(n + 1):
				num = i * n + j * m
				if num < maxi:
					setti.add(num)
		return maxi - len(setti)


class Solution:

	def candies(self, m, n):
		return (m - 1) * (n - 1) // 2


class Solution:

	def find(s, a):
		if a not in s:
			return True
		return False

	def candies(self, m, n):
		return (m - 1) * (n - 1) // 2


class Solution:

	def candies(self, m, n):
		mn = m * n - m - n
		lis = [mn]
		setn = {mn}
		while lis:
			num = lis[0]
			lis.remove(lis[0])
			if num - m > 0 and num - m not in setn:
				setn.add(num - m)
				lis.append(num - m)
			if num - n > 0 and num - n not in setn:
				setn.add(num - n)
				lis.append(num - n)
		return len(setn)


import math

class Solution:

	def candies(self, m, n):
		frobenius = m * n - m - n
		count = 0
		for i in range(1, n):
			count += m * (n - i) // n
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = list(map(int, input().strip().split()))
		m = arr[0]
		n = arr[1]
		obj = Solution()
		print(obj.candies(m, n))


import math

class Solution:

	def candies(self, m, n):
		frobenius = m * n - m - n
		count = 0
		for i in range(1, n):
			count += m * (n - i) // n
		return count


class Solution:

	def candies(self, m, n):
		maxval = m * n
		maxnum = max(m, n)
		arr1 = []
		arr2 = []
		i = min(m, n)
		j = maxnum
		res = 1
		z = 1
		while res < maxval:
			res = i * z
			if res < maxval:
				arr1.append(i * z)
			z += 1
		res = 1
		z = 1
		while res < maxval:
			res = j * z
			if res < maxval:
				arr2.append(j * z)
			z += 1
		arr3 = []
		for i in range(len(arr1)):
			for j in range(len(arr2)):
				res = arr1[i] + arr2[j]
				if res < maxval:
					arr3.append(arr1[i] + arr2[j])
				else:
					break
		res = len(arr1) + len(arr2) + len(arr3)
		return maxval - res - 1


from collections import deque

class Solution:

	def candies(self, m, n):
		q = deque()
		q.append(m * n - m - n)
		s = set()
		count = 0
		while q:
			x = q.popleft()
			count += 1
			if x - m > 0 and x - m not in s:
				s.add(x - m)
				q.append(x - m)
			if x - n > 0 and x - n not in s:
				s.add(x - n)
				q.append(x - n)
		return count


class Solution:

	def candies(self, m, n):
		i = 0
		X = m * n - m - n
		queue = []
		queue.append(X)
		set = {X}
		count = 0
		while len(queue) > 0:
			curr = queue[0]
			queue.remove(queue[0])
			count += 1
			key = curr - m
			if key > 0 and key not in set:
				queue.append(key)
				set.add(key)
			key = curr - n
			if key > 0 and key not in set:
				queue.append(key)
				set.add(key)
		return count


class Solution:

	def candies(self, m, n):
		maxn = m * n - (m + n)
		qu = [maxn]
		set_ans = {maxn}
		while qu:
			num = qu[0]
			qu.remove(qu[0])
			if num - n > 0 and num - n not in set_ans:
				set_ans.add(num - n)
				qu.append(num - n)
			if num - m > 0 and num - m not in set_ans:
				set_ans.add(num - m)
				qu.append(num - m)
		return len(set_ans)


class Solution:

	def candies(self, m, n):
		x = m * n - m - n
		queue = []
		queue.append(x)
		set = {x}
		count = 0
		while queue:
			curr = queue.pop(0)
			count += 1
			if curr - m > 0 and curr - m not in set:
				queue.append(curr - m)
				set.add(curr - m)
			if curr - n > 0 and curr - n not in set:
				queue.append(curr - n)
				set.add(curr - n)
		return count