Given a positive integer N, find the last digit of the N^{th} term from the Fibonacci series.
Note: For N=0 you have to return 0.
 
Example 1:
Input:
N = 5
Output:
5
Explanation:
5th Fibonacci number is 5
Example 2:
Input:
N = 14
Output:
7
Explanation:
14th Fibonacci number is 377
It's last digit is 7
Your Task:
You don't need to read input or print anything. Your task is to complete the function fib() which takes an integer N as input parameter and returns the last digit of Nth Fibonacci number.
Expected Time Complexity: O(N)
Expected Space Complexity: O(1)
 
Constraints:
0 <= N <= 1000

Difficulty: EASY
Tags: Divide and conquer

Mathematics
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:

    def fib (self,N):

        #code here

Solutions:
class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		else:
			a = 0
			b = 1
			c = a + b
			for i in range(1, N):
				c = a + b
				a = b
				b = c
			c = str(c)
		return c[-1]


class Solution:

	def fib(self, N):
		(a, b) = (0, 1)
		for i in range(N):
			(a, b) = (b, a + b)
		return str(a)[-1]


class Solution:

	def fib(self, N):
		(n1, n2) = (1, 0)
		for x in range(N):
			(n1, n2) = (n2, n1 + n2)
		return str(n2)[-1]


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		if N == 1:
			return 1
		if N == 2:
			return 1
		a = 1
		b = 1
		for i in range(3, N + 1):
			c = (a + b) % 10
			a = b
			b = c
		return c


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		if N == 1:
			return 1
		dp = [0] * (N + 1)
		dp[0] = 0
		dp[1] = 1
		for i in range(2, N + 1):
			dp[i] = dp[i - 1] + dp[i - 2]
		return dp[N] % 10


class Solution:

	def fib(self, N):
		first = (0, 1)
		if N in first:
			return N
		(second_to_last, last) = (0, 1)
		for n in range(2, N + 1):
			(second_to_last, last) = (last, (second_to_last + last) % 10)
		return last


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		elif N == 1:
			return 1
		a = 0
		b = 1
		for i in range(2, N + 1):
			r = a + b
			a = b
			b = r
		return r % 10


class Solution:

	def fib(self, N):
		first = (0, 1)
		if N in first:
			return N
		(second_latest, latest) = first
		for n in range(2, N + 1):
			(second_latest, latest) = (latest, (latest + second_latest) % 10)
		return latest


class Solution:

	def fib(self, N):
		base_terms = (0, 1)
		if N in base_terms:
			return N
		(previous, current) = base_terms
		for _ in range(N - 1):
			(previous, current) = (current, (previous + current) % 10)
		return current


class Solution:

	def fib(self, n):
		if n <= 1:
			return n
		i = 1
		a = 0
		b = 1
		while True:
			i += 1
			c = a + b
			if i == n:
				return str(c)[-1]
			a = b
			b = c


class Solution:

	def fib(self, N):
		fibi = [1, 1]
		a = 1
		b = 1
		if N == 0:
			return 0
		for i in range(2, N):
			c = a + b
			fibi.append(c)
			a = b
			b = c
		x = fibi[-1]
		y = x % 10
		return y


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		elif N == 1 or N == 2:
			return 1
		else:
			a = 1
			b = 1
			for i in range(2, N):
				c = a + b
				a = b
				b = c
			return c % 10


class Solution:

	def fib(self, N):
		arr = [0, 1]
		for i in range(N):
			arr.append((arr[-1] + arr[-2]) % 10)
		return arr[N]


class Solution:

	def fib(self, n):
		a = 0
		b = 1
		if n <= 1:
			return n
		for i in range(1, n):
			c = a + b
			a = b
			b = c
		return c % 10


class Solution:

	def fib(self, n):
		dp = {0: 0, 1: 1}
		if n in dp:
			return dp[n]
		for i in range(2, n + 1):
			dp[i] = dp[i - 1] + dp[i - 2]
		return str(dp[n])[-1]


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		if N == 1 or N == 2:
			return 1
		first = 1
		sec = 1
		s = 0
		for i in range(3, N + 1):
			s = first + sec
			first = sec
			sec = s
		return int(str(s)[-1])


class Solution:

	def fib(self, N):
		f1 = 0
		f2 = 1
		for i in range(N):
			f3 = f1 + f2
			f1 = f2
			f2 = f3
		s = str(f1)
		return s[-1]


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		(a, b) = (1, 1)
		while N > 1:
			(a, b) = (b, a + b)
			N -= 1
		return a % 10


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		if N == 1:
			return 1
		(n1, n2) = (1, 1)
		i = 2
		while i < N:
			nth = n1 + n2
			n1 = n2
			n2 = nth
			i += 1
		return str(n2)[-1]


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		if N == 1:
			return 1
		x = [0, 1]
		for i in range(N - 1):
			x.append(x[-1] + x[-2])
		c = str(x[-1])
		return c[-1]


class Solution:

	def fib(self, N: int) -> int:
		if not N:
			return N
		else:
			fibonacci_number = self.nthFibonacci(N)
			return fibonacci_number % 10

	@staticmethod
	def nthFibonacci(num: int) -> int:
		(a, b) = (0, 1)
		for _ in range(num):
			(a, b) = (b, a + b)
		return a


class Solution:

	def fib(self, N):
		a = 0
		b = 1
		fibmod = [0]
		if N <= 1:
			return N
		while True:
			fibmod.append(b % 10)
			(a, b) = (b, a + b)
			if a % 10 == 0 and b % 10 == 1:
				break
		return fibmod[N % (len(fibmod) - 1)]


class Solution:

	def fib(self, N):
		first = 0
		second = 1
		if N == 0:
			return first
		if N == 1:
			return second
		for i in range(N - 1):
			fibonacci = first + second
			first = second
			second = fibonacci
		return fibonacci % 10


class Solution:

	def fib(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		if n == 2:
			return 1
		if n > 2:
			a = 1
			b = 1
			for i in range(3, n + 1):
				sum = a + b
				a = b
				b = sum
			x = str(sum)
			return int(x[-1])


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		elif N == 1:
			return 1
		(n1, n2) = (0, 1)
		i = 1
		while i < N:
			n = n1 + n2
			n1 = n2
			n2 = n
			i += 1
		return str(n)[-1]


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		elif N == 1:
			return 1
		else:
			(a, b) = (0, 1)
		for i in range(1, N):
			c = a + b
			a = b
			b = c
		lastdigit = int(repr(c)[-1])
		return lastdigit


class Solution:

	def fib(self, N):
		n1 = 1
		n2 = 1
		if N == 0:
			return 0
		if N == 1 or N == 2:
			return 1
		for i in range(3, N + 1):
			x = n2
			n2 = n2 + n1
			n1 = x
		return n2 % 10


class Solution:

	def fib(self, N):
		lst = []
		if N == 1:
			lst.append(1)
		elif N == 0:
			return 0
		else:
			lst.append(1)
			lst.append(1)
			for i in range(2, N):
				a = lst[i - 1] + lst[i - 2]
				lst.append(a)
		res = lst[N - 1]
		a = str(res)
		return a[-1]


class Solution:

	def fib(self, N):
		(first, second, temp) = (1, 1, 0)
		if N == 0:
			return 0
		if N <= 2:
			return 1
		for i in range(3, N + 1):
			temp = first + second
			first = second % 10
			second = temp % 10
		return second % 10


class Solution:

	def fib(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		i = 0
		j = 1
		for z in range(n - 1):
			ans = i + j
			i = j
			j = ans
		if ans < 9:
			return ans
		if ans > 9:
			return ans % 10


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		num1 = 0
		num2 = 1
		sum = num1 + num2
		for i in range(3, N + 1):
			num1 = num2
			num2 = sum
			sum = num1 + num2
		sum = sum % 10
		return sum


class Solution:

	def fib(self, N):

		def fibi(f, n):
			f[0] = 0
			f[1] = 1
			for i in range(2, n):
				f[i] = (f[i - 1] + f[i - 2]) % 10
			return f
		f = [0] * 61
		f = fibi(f, 60)
		return f[N % 60]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.fib(N))


class Solution:

	def fib(self, n):
		a = 0
		b = 1
		if n == 0 or n == 1:
			return n
		else:
			for i in range(n - 1):
				c = a + b
				a = b
				b = c
		return c % 10
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.fib(N))


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		if N == 1:
			return 1
		dp = [0] * (N + 1)
		dp[1] = 1
		for i in range(2, N + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % 10
		return dp[N]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.fib(N))


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		fib_1 = 1
		fib_2 = 1
		series = 0
		for i in range(N):
			fib_1 = fib_2
			fib_2 = series
			series = fib_1 + fib_2
		series = str(series)
		return series[-1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.fib(N))


class Solution:

	def fib(self, N):
		fib_60 = []
		(first, second, nextNum) = (0, 1, None)
		fib_60.append(first)
		fib_60.append(second)
		for i in range(60):
			nextNum = (first + second) % 10
			fib_60.append(nextNum)
			first = second
			second = nextNum
		return fib_60[N % 60]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.fib(N))


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		(first, second, nextNum) = (0, 1, 1)
		while N - 2 >= 0:
			nextNum = (first + second) % 10
			first = second
			second = nextNum
			N -= 1
		return nextNum % 10
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.fib(N))


class Solution:

	def fib(self, N):
		f = [0] * 60
		f[1] = 1
		for i in range(2, 60):
			f[i] = (f[i - 1] + f[i - 2]) % 10
		return f[N % 60]


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		(a, ans) = (0, 1)
		for i in range(1, N):
			ans += a
			a = ans - a
		return ans % 10


class Solution:

	def fib(self, N):
		if N < 2:
			return N
		f = 0
		s = 1
		for i in range(2, N + 1):
			n = f + s
			f = s
			s = n
		return n % 10


class Solution:

	def fib(self, N):
		if N == 1:
			return 1
		cnt = 2
		a = 0
		b = 1
		c = 0
		while cnt <= N:
			c = a + b
			a = b
			b = c
			cnt += 1
		return c % 10


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		n1 = 0
		n2 = 1
		sum = 0
		if N == 1:
			return 1
		for i in range(2, N + 1):
			sum = 0
			sum = n1 + n2
			n1 = n2
			n2 = sum
		return sum % 10


class Solution:

	def fib(self, N):
		num = self.fibb(N)
		s = str(num)
		return int(s[-1])

	def fibb(self, N):
		a = 0
		b = 1
		if N == 0:
			return a
		if N == 1:
			return b
		for i in range(1, N):
			c = a + b
			a = b
			b = c
		return b


class Solution:

	def fib(self, N):
		arr = [0, 1]
		a = 0
		b = 1
		for i in range(1, N):
			nextTerm = a + b
			arr.append(nextTerm)
			a = b
			b = nextTerm
		return arr[N] % 10


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		if N == 1:
			return 1
		if N == 2:
			return 1
		(a, b, c) = (1, 1, 0)
		i = 3
		while i <= N:
			c = a + b
			a = b
			b = c
			i += 1
		return c % 10


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		arr = list()
		arr.append(1)
		arr.append(1)
		for i in range(2, N):
			arr.append(arr[i - 1] + arr[i - 2])
		return str(arr[-1])[-1]


class Solution:

	def fib(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		a = 0
		b = 1
		t = 2
		while t <= n:
			c = b + a
			a = b
			b = c
			t += 1
		return c % 10


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		previous = 1
		current = 1
		for i in range(N - 2):
			(previous, current) = (current, previous + current)
		return int(str(current)[-1])


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		else:
			a = 1
			b = 1
			for i in range(0, N - 2):
				b1 = a + b
				a = b
				b = b1
			b = str(b)
			k = len(b)
			return b[k - 1]


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		else:
			a = 1
			b = 1
			for i in range(0, N - 2):
				b1 = a + b
				a = b
				b = b1
			return b % 10


class Solution:

	def fib(self, n):
		f = [0, 1]
		for i in range(2, n + 1):
			f.append(f[i - 1] + f[i - 2])
		return f[n] % 10


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		if N == 1:
			return 1
		if N == 2:
			return 1
		fib_n_1 = 1
		fib_n_2 = 0
		res = fib_n_2 + fib_n_1
		for i in range(N - 1):
			res = fib_n_2 + fib_n_1
			fib_n_2 = fib_n_1
			fib_n_1 = res
		return res % 10


class Solution:

	def fib(self, n):
		res = {}
		res[0] = 0
		res[1] = 1
		for i in range(2, n + 1):
			res[i] = res[i - 1] + res[i - 2]
			del res[i - 2]
		return res[n] % 10


class Solution:

	def fib(self, N):
		if N == 0 or N == 1:
			return N
		(p, pp) = (1, 0)
		c = 0
		for i in range(2, N + 1):
			c = (p + pp) % 10
			pp = p
			p = c
		return c


class Solution:

	def fib(self, n):
		d = dict()
		d[0] = 0
		d[1] = 1
		d[2] = 1
		if n <= 2:
			return d[n] % 10
		for i in range(3, n + 1):
			d[i] = d[i - 1] + d[i - 2]
		return d[n] % 10


class Solution:

	def fib(self, N):
		if N < 2:
			return N
		pre = 1
		pre2 = 0
		res = 1
		for _ in range(2, N + 1):
			res = pre + pre2
			pre2 = pre
			pre = res
		return res % 10


class Solution:

	def fib(self, N):
		a = 1
		b = 1
		c = 0
		if N == 0:
			return 0
		elif N == 1 or N == 2:
			return 1
		for i in range(0, N - 2):
			c = a + b
			if a <= b:
				a = c
			else:
				b = c
		d = str(c)
		return d[len(d) - 1]


class Solution:

	def fib(self, N):
		if N <= 1:
			return N
		prev = 0
		current = 1
		for i in range(N - 1):
			new = prev + current
			prev = current
			current = new
		if current < 10:
			return current
		else:
			k = str(current)
			return k[-1]


class Solution:

	def fib(self, N):
		if N == 0 or N == 1:
			return N
		a = 0
		b = 1
		result = 0
		for i in range(2, N + 1):
			result = a + b
			a = b
			b = result
		return result % 10


class Solution:

	def fib(self, N):
		if N == 0:
			return 0
		if N <= 2:
			return 1
		D = [0] * (N + 1)
		D[0] = 0
		D[1] = D[2] = 1
		for i in range(3, N + 1):
			D[i] = D[i - 1] + D[i - 2]
		return D[N] % 10