Given a number N, find the total sum of digits of all the numbers from 1 to N.
 
Example 1:
Input:
N = 5
Output:
15
Explanation:
Sum of digits of number from 1 to 5:
1 + 2 + 3 + 4 + 5 = 15
Example 2:
Input:
N = 12
Output
51
Explanation:
Sum of all digits from 1 to 12 is:
1+2+3+4+5+6+7+8+9+(1+0)+(1+1)+(1+2) = 51
Your Task:
You don't need to read input or print anything. Your task is to complete the function sumOfDigits() which takes an integer N as input parameter and returns the total sum of digits of all the numbers from 1 to N. 
 
Expected Time Complexity: O(D^{2}) (D is the number of digits in N)
Expected Space Complexity: O(D) (D is the number of digits in N)
 
Constraints:
1<= N <=1000000

Difficulty: EASY
Tags: Dynamic programming
Skill types: Dynamic programming
Expected Time Complexity: O(D^{2}) (D is the number of digits in N)
Expected Auxiliary Space: O(D) (D is the number of digits in N)

Starter code:
#User function Template for python3
class Solution:
    def sumOfDigits (self,N):
        # code here

Solutions:
class Solution:

	def sumOfDigits(self, N):
		sum = 0
		for i in range(1, N + 1):
			if i <= 9:
				sum = sum + i
			else:
				x = 0
				while i > 0:
					last = i % 10
					x = x + last
					i = i // 10
				sum = sum + x
		return sum


class Solution:

	def sum(self, n):
		s = 0
		while n > 0:
			r = n % 10
			s = s + r
			n = n // 10
		return s

	def sumOfDigits(self, N):
		s = 0
		for i in range(1, N + 1):
			p = self.sum(i)
			s = s + p
		return s


class Solution:

	def sumOfDigits(self, n):
		total = 0

		def value(num):
			nonlocal total
			while num:
				total += num % 10
				num = num // 10
		for i in range(1, n + 1):
			value(i)
		return total


class Solution:

	def sumOfDigits(self, N):
		summ = 0
		for i in range(1, N + 1):
			while i != 0:
				summ += i % 10
				i = i // 10
		return summ


class Solution:

	def sumOfDigits(self, N):

		def count(val):
			sums = 0
			while val != 0:
				rem = val % 10
				sums += rem
				val = val // 10
			return sums
		sums = 0
		for i in range(1, N + 1):
			sums += count(i)
		return sums


class Solution:

	def sumOfDigits(self, n):
		ans = 0
		for i in range(1, n + 1):
			while i:
				ans += i % 10
				i //= 10
		return ans


class Solution:

	def sumOfDigits(self, N):
		s = 0
		for i in range(1, N + 1):
			j = i
			while j >= 1:
				s += j % 10
				j = j // 10
		return s
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.sumOfDigits(N))


class Solution:

	def sumOfDigits(self, N):

		def digitSum(n):
			s = 0
			while n > 0:
				s = s + n % 10
				n = n // 10
			return s
		count = 0
		i = 0
		while i <= N:
			count += digitSum(i)
			i += 1
		return count


def digsum(x):
	res = 0
	temp = x
	while temp:
		res += temp % 10
		temp //= 10
	return res

class Solution:

	def sumOfDigits(self, N):
		res = 0
		for i in range(1, N + 1):
			res += digsum(i)
		return res


class Solution:

	def sumOfDigits(self, N):
		data = [0 for i in range(N + 1)]
		for i in range(N + 1):
			if i < 10:
				data[i] = i
			else:
				data[i] = data[i // 10] + data[i % 10]
		return sum(data)


class Solution:

	def sumOfDigits(self, N):
		result = 0
		for x in range(1, N + 1):
			result += self.sum_of_element(x)
		return result

	def sum_of_element(self, n):
		sum = 0
		while n != 0:
			r = n % 10
			sum += r
			n = n // 10
		return sum


class Solution:

	def sumOfDigits(self, n):
		dp = [0] * (n + 1)
		ans = 0
		for i in range(1, n + 1):
			if i < 10:
				dp[i] = i
			else:
				dp[i] = dp[i // 10] + int(str(i)[-1])
			ans += dp[i]
		return ans


class Solution:

	def sumOfDigits(self, N):
		s1 = 0
		for i in range(1, N + 1):
			j = i
			while j >= 1:
				s1 += j % 10
				j = j // 10
		return s1


class Solution:

	def sumOfDigits(self, n):
		import math
		if n < 10:
			return n * (n + 1) // 2
		d = int(math.log10(n))
		a = [0] * (d + 1)
		a[0] = 0
		a[1] = 45
		for i in range(2, d + 1):
			a[i] = a[i - 1] * 10 + 45 * int(math.ceil(math.pow(10, i - 1)))
		p = int(math.ceil(math.pow(10, d)))
		msd = n // p
		ans = int(msd * a[d] + msd * (msd - 1) // 2 * p // 1 + msd * (1 + n % p) // 1 + self.sumOfDigits(n % p) // 1)
		return ans


def getDigits(x, digit):
	while x:
		digit.append(x % 10)
		x //= 10

def digitSum(index, sumof, tight, digit, dp):
	if index == -1:
		return sumof
	if dp[index][sumof][tight] != -1 and tight != 1:
		return dp[index][sumof][tight]
	ret = 0
	k = digit[index] if tight else 9
	for i in range(0, k + 1):
		newTight = tight if digit[index] == i else 0
		ret += digitSum(index - 1, sumof + i, newTight, digit, dp)
	dp[index][sumof][tight] = ret
	return ret

def rangeDigitSum(a, b):
	digitA = []
	getDigits(a - 1, digitA)
	ans1 = digitSum(len(digitA) - 1, 0, 1, digitA)
	digitB = []
	getDigits(b, digitB)
	ans2 = digitSum(len(digitB) - 1, 0, 1, digitB)
	return ans2 - ans1

class Solution:

	def sumOfDigits(self, N):
		dp = [[[-1 for i in range(2)] for j in range(180)] for k in range(20)]
		digitB = []
		getDigits(N, digitB)
		ans2 = digitSum(len(digitB) - 1, 0, 1, digitB, dp)
		return ans2


class Solution:

	def sumOfDigits(self, N):
		cache = {}
		NArray = []
		while N:
			(N, m) = divmod(N, 10)
			NArray.append(m)
		NArray = list(reversed(NArray))
		L = len(NArray)

		def DFS(idx, sumSoFar, isRestricted):
			if not isRestricted and (idx, sumSoFar) in cache:
				return cache[idx, sumSoFar]
			if idx == L:
				return sumSoFar
			maxConsideredVal = 9 if not isRestricted else NArray[idx]
			ret = 0
			for i in range(maxConsideredVal + 1):
				ret += DFS(idx + 1, sumSoFar + i, isRestricted and i == NArray[idx])
			if not isRestricted:
				cache[idx, sumSoFar] = ret
			return ret
		return DFS(0, 0, True)


class Solution:

	def sumOfDigits(self, N):
		s = 0
		for i in range(1, N + 1):
			if i < 10:
				s += i
			else:
				while i != 0:
					a = i % 10
					s += a
					i = i // 10
		return s


import math

class Solution:

	def sumOfDigits(self, N):

		def S(n):
			if n < 10:
				return n * (n + 1) // 2
			r = n % 10
			k = n // 10
			return 45 * k + 10 * S(n // 10 - 1) + (1 + n % 10) * D(n // 10) + n % 10 * (1 + n % 10) // 2

		def D(n):
			ans = 0
			while n:
				ans += n % 10
				n //= 10
			return ans
		return S(N)


import math

class Solution:

	def sumOfDigits(self, N):

		def sumOfDigitsFrom1ToN(n):
			if n < 10:
				return n * (n + 1) // 2
			d = int(math.log(n, 10))
			a = [0] * (d + 1)
			a[0] = 0
			a[1] = 45
			for i in range(2, d + 1):
				a[i] = a[i - 1] * 10 + 45 * int(math.ceil(pow(10, i - 1)))
			return sumOfDigitsFrom1ToNUtil(n, a)

		def sumOfDigitsFrom1ToNUtil(n, a):
			if n < 10:
				return n * (n + 1) // 2
			d = int(math.log(n, 10))
			p = int(math.ceil(pow(10, d)))
			msd = n // p
			return msd * a[d] + msd * (msd - 1) // 2 * p + msd * (1 + n % p) + sumOfDigitsFrom1ToNUtil(n % p, a)
		return sumOfDigitsFrom1ToN(N)


class Solution:

	def sumOfDigits(self, N):
		tot = 0
		for i in range(1, N + 1):
			x = i
			while x > 0:
				tot += x % 10
				x = x // 10
		return tot