Given two numbers A and B, the task is to find f(A^{B}). f(n) which takes a positive integer n as input and does the following:
f(n):
if n < 10  
    return n
else return f( sum_of_digits(n) )
 
Example 1:
Input: A = 6, B = 6
Output: 9
Explanation: 
f(6^{6}) = f(46656) = f(27) = f(9) = 9
Example 2:
Input: A = 7, B = 3
Output: 1
Explanation: 
f(7^{3}) = f(343) = f(10) = f(1) = 1
 
Your Task:
You don't need to read or print anything. Your task is to complete the function SumofDigits() which takes A and B as input parameters and returns f(A^{B}).
 
Expected Time Complexity: O(Log(B))
Expected Space Complexity: O(1)
 
Constraints:
1 <= A, B <= 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

	def SumofDigits(self, A, B):

		# Code here

Solutions:
class Solution:

	def SumofDigits(self, a, b):
		k = 1
		while b:
			if b & 1:
				k = k * a % 9
			a = a * a % 9
			b = b >> 1
		if k == 0:
			return 9
		return k


class Solution:

	def SumofDigits(self, A, B):
		res = 1
		while B:
			if B & 1:
				res = res * A % 9
			A = A * A % 9
			B = B >> 1
		if res == 0:
			return 9
		return res


class Solution:

	def SumofDigits(self, A, B):
		if A == 0:
			return 0
		s = A % 9
		if s == 0:
			s = 9
		if (s == 3 or s == 6) and B > 1:
			return 9
		if B == 1:
			return s
		if B == 0:
			return 1
		B = B % 6
		if B == 0:
			s = A ** 6 % 9
			if s == 0:
				return 9
			return s
		s = A ** B % 9
		if s == 0:
			return 9
		return s


class Solution:

	def power(self, x, y):
		res = 1
		x = x % 9
		while y > 0:
			if y & 1:
				res = res * x % 9
			y = y >> 1
			x = x * x % 9
		return res

	def SumofDigits(self, A, B):
		x = self.power(A, B)
		if x == 0:
			return 9
		return x


import math

class Solution:

	def SumofDigits(self, A, B):
		s = pow(A, B, 9)
		if s % 9 == 0:
			return 9
		else:
			return s % 9


import math

class Solution:

	def fun(self, num):
		if num == 0:
			return 0
		elif num % 9 == 0:
			return 9
		else:
			return num % 9

	def SumofDigits(self, A, B):
		sum = self.fun(A)
		rem = B % 6
		if (sum == 3 or sum == 6) and B > 1:
			return 9
		elif B == 1:
			return sum
		elif B == 0:
			return 1
		elif rem == 0:
			return int(self.fun(math.pow(sum, 6)))
		else:
			return int(self.fun(math.pow(sum, rem)))