It is given to you that on 1st January 2001 it was monday. Let's call a year as Geeky if the 1st January of that year happens to be on Sunday. You will be given two years 'a' and 'b'. The task is to find the no. of Geeky years between those two years (including 'a' and 'b' as well)
 
Example 1:
Input: a = 2001, b = 2013
Output: 2
Example 2:
Input: a = 2020, b = 2024
Output: 1
 
Your Task:
You don't need to read or print anything. Your task is to complete the function Count() which takes a and b as input parameter and returns total no. of Geeky years between a to b(inclusive).
 
Expected Time Complexity: O(n^{2})
Expected Space Complexity: O(1)
 
Constraints:
1000 <= a < = b <= 3000

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
	def Count(self, a, b):
		# Code here

Solutions:
import datetime

class Solution:

	def Count(self, a, b):
		c = 0
		for i in range(a, b + 1):
			x = datetime.datetime(i, 1, 1)
			if x.strftime('%A') == 'Sunday':
				c += 1
		return c


class Solution:

	def Count(self, a, b):
		count = 0
		for i in range(a, b + 1):
			y = i - 1
			ans = (y + y // 4 - y // 100 + y // 400) % 7
			if ans == 6:
				count += 1
		return count


import datetime

class Solution:

	def Count(self, a, b):
		dp = [0 for i in range(3001)]
		dp[2001] = 0
		for i in range(2000, 999, -1):
			if i % 400 == 0 or (i % 4 == 0 and i % 100 != 0):
				x = dp[i + 1] - 2
				if x < 0:
					x = 6 + x + 1
				dp[i] = x
			else:
				x = dp[i + 1] - 1
				if x < 0:
					x = 6
				dp[i] = x
		for i in range(2001, 3000):
			if i % 400 == 0 or (i % 4 == 0 and i % 100 != 0):
				x = dp[i] + 2
				if x > 6:
					x = x - 6 - 1
				dp[i + 1] = x
			else:
				x = dp[i] + 1
				if x > 6:
					x = 0
				dp[i + 1] = x
		ans = 0
		for i in range(a, b + 1):
			if dp[i] == 6:
				ans += 1
		return ans