Geek works at the post office and he writes the following types of letters.
	Corporate Letters: 12 letters of this type can be written in an hour.
	Informal Letters: 10 letters of this type can be written in an hour.
Given N number of letters, find the minimum number of hours he needs to generate a combination of both types without wasting any time.
 
Example 1:
Input: N = 33
Output: -1
Explaination: 33 letters can not be generated
without wasting any time.
 
Example 2:
Input: N = 36
Output: 3
Explaination: 36 corporate letters can 
be written in 3 hours.
 
Your Task:
You do not need to read input or print anything. Your task is to complete the function minHours() which takes the value N as input parameters and returns the minimum hours. Return -1 if N letters cannot be written without wasting any time.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def minHours(self, N):

        # code here

Solutions:
class Solution:

	def minHours(self, N):
		if N % 12 == 0:
			return N // 12
		c = 0
		while N > 0:
			if N % 12 == 0:
				c = c + N // 12
				return c
			N = N - 10
			c = c + 1
		if N == 0:
			return c
		return -1


class Solution:

	def minHours(self, N):
		dp = [10000000000.0] * (N + 1)
		dp[0] = 0
		for i in range(10, N + 1):
			if i - 10 >= 0 and dp[i - 10] != 10000000000.0:
				dp[i] = min(dp[i], dp[i - 10] + 1)
			if i - 12 >= 0 and dp[i - 12] != 10000000000.0:
				dp[i] = min(dp[i], dp[i - 12] + 1)
		if dp[N] == 10000000000.0:
			return -1
		return dp[N]


from collections import defaultdict

class Solution:

	def minHours(self, N):
		d = defaultdict(lambda : float('inf'))
		d[0] = 0
		for i in range(10, N + 1, 2):
			d[i] = min(d[i - 10], d[i - 12]) + 1
		return d[N] if d[N] != float('inf') else -1


class Solution:

	def minHours(self, N):
		ans = 0
		while N > 0:
			if N % 12 == 0:
				ans += N // 12
				return ans
			N -= 10
			ans += 1
		if N == 0:
			return ans
		else:
			return -1


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def minHours(self, N):
		dp = {}

		def mintime(n):
			if n < 0:
				return 999999999
			if n == 0:
				return 0
			if n in dp:
				return dp[n]
			dp[n] = min(mintime(n - 10) + 1, mintime(n - 12) + 1)
			return dp[n]
		b = mintime(N)
		if b >= 999999999:
			return -1
		return b


class Solution:

	def minHours(self, n):
		arr = [-1] * (n + 1)
		arr[0] = 0
		for i in range(n + 1):
			if i - 10 >= 0 and 1 - 12 >= 0:
				if arr[i - 10] != -1 and arr[i - 12] != -1:
					arr[i] = min(arr[i], arr[i - 10] + 1, arr[i - 12] + 1)
			if i - 10 >= 0:
				if arr[i - 10] != -1:
					arr[i] = n
					arr[i] = min(arr[i], arr[i - 10] + 1)
			if i - 12 >= 0:
				if arr[i - 12] != -1:
					arr[i] = n
					arr[i] = min(arr[i], arr[i - 12] + 1)
		return arr[n]


class Solution:

	def minHours(self, N):
		dp = [float('inf')] * (N + 1)
		dp[0] = 0
		if N <= 11:
			if N == 10:
				return 1
			else:
				return -1
		dp[10] = 1
		for i in range(12, N + 1):
			dp[i] = 1 + min(dp[i - 12], dp[i - 10])
		if dp[N] != float('inf'):
			return dp[N]
		else:
			return -1