Geek wants to buy chocolates. The shop only has two types of chocolates. One costs 3 rupees and the other cost 7 rupees. Geek has 100 rupees. Is it possible for him to save exactly N rupees after visiting the shop?
Example 1:
Input: N = 99
Output: 0
Explanation: Geek needs to save 99 rupees. 
That means he can only spend 1 rupee. But 
no chocolate is available for 1 rupee. Therefore 
there is no way for him to save N rupees. 
Example 2:
Input: N = 97
Output: 1
Explanation: Geek can buy one chocolate 
for 3 rupees and save 97 rupees.
Your Task:
You do not need to read input or print anything. Your task is to complete the function isPossible() which takes N as input parameter and returns 1 if Geek can save N rupees else returns 0.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints:
0 ≤ N ≤ 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def isPossible(self, N):

        # code here

Solutions:
class Solution:

	def isPossible(self, N):
		for i in range(100):
			for j in range(100):
				if i * 3 + j * 7 == 100 - N:
					return 1
		return 0


class Solution:

	def isPossible(self, n):

		def f(a):
			if a < 0:
				return 0
			if a == 0:
				return 1
			return f(a - 7) or f(a - 3)
		return f(100 - n)


class Solution:

	def isPossible(self, N):
		m = 100
		p = m - N
		o = p
		if p == 0:
			return 1
		while p >= 3:
			if p % 3 == 0:
				return 1
			p -= 7
		while o >= 7:
			if o % 7 == 0:
				return 1
			o -= 3
		return 0


class Solution:

	def a(self, N):
		if N == 0:
			return True
		if N < 3:
			return False
		return self.a(N - 7) or self.a(N - 3)

	def isPossible(self, N):
		if self.a(100 - N):
			return 1
		return 0


class Solution:

	def isPossible(self, N):
		for i in range(0, 34):
			for j in range(0, 15):
				if i * 3 + j * 7 == 100 - N:
					return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.isPossible(N))


class Solution:

	def isPossible(self, N):
		x = 100 - N
		if x == 1 or x == 2 or x == 4 or (x == 5) or (x == 8) or (x == 11):
			return 0
		else:
			return 1