Count the numbers between 1 to N containing 4 as a digit.
 
Example 1:
Input:
N = 9
Output:
1
Explanation:
4 is the only number between 1 to 9
which contains 4 as a digit.
Example 2:
Input:
N = 14
Output:
2
Explanation:
4 and 14 are the only number between 1
to 14 that contains 4 as a digit.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function countNumberswith4() which takes an Integer N as input and returns the answer.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{5}

Difficulty: EASY
Tags: Dynamic programming

Mathematics
Skill types: Dynamic programming
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def countNumberswith4(self, N):
        # code here

Solutions:
class Solution:

	def countNumberswith4(self, N):
		ans = 0
		for i in range(1, N + 1):
			ans += self.check(i)
		return ans

	def check(self, x):
		while x:
			if x % 10 == 4:
				return True
			x //= 10
		return False


class Solution:

	def countNumberswith4(self, N):
		count = 0
		for i in range(1, N + 1):
			if '4' in str(i):
				count += 1
		return count


class Solution:

	def countNumberswith4(self, N):
		ans = []
		for i in range(1, N + 1):
			if '4' in str(i):
				ans.append(i)
		return len(ans)


class Solution:

	def countNumberswith4(self, N):
		dp = [0 for i in range(N + 1)]

		def contains(N):
			if '4' in str(N):
				return 1
			return 0
		dp[0] = 0
		for i in range(1, N + 1):
			dp[i] = contains(i) + dp[i - 1]
		return dp[N]


class Solution:

	def countNumberswith4(self, N):
		dp = [-1 for i in range(N + 1)]

		def isContain(n):
			if str(n).count('4') >= 1:
				return 1
			return 0

		def solve(N, dp):
			dp[0] = 0
			for i in range(1, N + 1):
				dp[i] = isContain(i) + dp[i - 1]
		ans = solve(N, dp)
		return dp[N]


class Solution:

	def countNumberswith4(self, N):
		list1 = [i for i in range(1, N + 1) if '4' in str(i)]
		return len(list1)


class Solution:

	def countNumberswith4(self, N):
		counter = 0
		for i in range(0, N + 1):
			val = str(i)
			if '4' in val:
				counter += 1
		return counter


class Solution:

	def countNumberswith4(self, N):
		c = 0
		for i in range(1, N + 1):
			while i > 0:
				if i % 10 == 4:
					c += 1
					break
				i = int(i / 10)
		return c


class Solution:

	def countNumberswith4(self, N):
		c = 0
		for i in range(1, N + 1):
			s = str(i)
			for j in s:
				if j == '4':
					c += 1
					break
		return c


class Solution:

	def countNumberswith4(self, N):
		a = '4'
		c = 0
		for i in range(1, N + 1):
			k = str(i)
			if a in k:
				c += 1
		return c


class Solution:

	def countNumberswith4(self, N):
		cnt = 0
		for i in range(1, N + 1):
			temp = str(i)
			if '4' in temp:
				cnt += 1
		return cnt


class Solution:

	def countNumberswith4(self, N):
		dp = [0] * (N + 1)
		res = 0
		for i in range(N + 1):
			if i % 10 == 4:
				dp[i] = 1
			else:
				dp[i] = dp[i // 10]
			res += dp[i]
		return res


class Solution:

	def contains(self, i):
		while i > 0:
			if i % 10 == 4:
				return True
			i = i // 10
		return False

	def countNumberswith4(self, N):
		count = 0
		dp = [0 for i in range(N + 1)]
		for i in range(1, N + 1):
			if dp[i]:
				count += 1
				continue
			if self.contains(i):
				count += 1
				dp[i] = True
		return count


class Solution:

	def solvemem(self, N, dp):
		if N == 0:
			return 0
		if N % 10 == 4:
			return 1
		if dp[N] != -1:
			return dp[N]
		dp[N] = self.solvemem(N // 10, dp)
		return dp[N]

	def countNumberswith4(self, N):
		dp = [-1] * (N + 1)
		sum1 = 0
		for i in range(1, N + 1):
			sum1 += self.solvemem(i, dp)
		return sum1


class Solution:

	def countNumberswith4(self, N):
		count = 0
		for x in range(N + 1):
			count += '4' in str(x)
		return count


class Solution:

	def checkDigit(self, n):
		while n > 0:
			if n % 10 == 4:
				return True
			n = n // 10
		return False

	def countNumberswith4(self, N):
		count = 0
		for num in range(1, N + 1):
			if self.checkDigit(num):
				count += 1
		return count


class Solution:

	def countNumberswith4(self, N):
		c = 0
		for i in range(1, N + 1):
			if str.__contains__(str(i), '4') == True:
				c += 1
		return c


class Solution:

	def countNumberswith4(self, N):
		s = 0
		a = ''
		for i in range(N + 1):
			a = str(i)
			b = a.find('4')
			if b >= 0:
				s += 1
			a = ''
		return s


class Solution:

	def countNumberswith4(self, N):
		count = 0
		for i in range(1, N + 1):
			while i > 0:
				a = i % 10
				i //= 10
				if a == 4:
					count += 1
					break
		return count


class Solution:

	def countNumberswith4(self, N):
		arr = [0] * (N + 1)
		if N < 4:
			return 0
		for i in range(4, N + 1):
			if '4' in str(i):
				arr[i] = max(arr[i - 1], arr[i - 1] + 1)
			else:
				arr[i] = arr[i - 1]
		return arr[N]


class Solution:

	def countNumberswith4(self, N):
		if N < 4:
			return 0
		count = 0
		temp = [False for i in range(N + 1)]
		for i in range(4, N + 1):
			if i % 10 == 4 or temp[i // 10]:
				temp[i] = True
				count += 1
		del temp
		return count


class Solution:

	def countNumberswith4(self, N):
		r = 0
		for i in range(N + 1):
			j = i
			while j > 0:
				if j % 10 == 4:
					r += 1
					break
				j //= 10
		return r