Sum of Digits in a^n till a single digit
Given two numbers a and n, the task is to find the single sum of digits of a^n (pow(a, n)). In single digit sum, we keep doing sum of digit until a single digit is left.
Examples:
Input : a = 5, n = 4 Output : 4 5^4 = 625 = 6+2+5 = 13 Since 13 has two digits, we sum again 1 + 3 = 4. Input : a = 2, n = 8 Output : 4 2^8=256 = 2+5+6 = 13 = 1+3 = 4
A naive approach is to first find a^n, then find sum of digits in a^n using the approach discussed here.
The above approach may cause overflow. A better solution is based on below observation.
int res = 1; for (int i=1; i<=n; i++) { res = res*a; res = digSum(res); } Here digSum() finds single digit sum of res. Please refer this for details of digSum().
Illustration of above pseudo code:
For example, let a = 5, n = 4.
After first iteration,
res = 5
After second iteration,
res = 7 (Note : 2 + 5 = 7)
After third iteration,
res = 8 (Note : 3 + 5 = 8)
After 4th iteration,
res = 4 (Note : 4 + 0 = 4)
We can write a function similar to a fast modular exponentiation to evaluate digSum(a^n) which evaluates this in log(n) steps.
Below is the implementation of above approach:
C++
// CPP program to find single digit // sum of a^n. #include <bits/stdc++.h> using namespace std; // This function finds single digit // sum of n. int digSum( int n) { if (n == 0) return 0; return (n % 9 == 0) ? 9 : (n % 9); } // Returns single digit sum of a^n. // We use modular exponentiation technique. int powerDigitSum( int a, int n) { int res = 1; while (n) { if (n % 2 == 1) { res = res * digSum(a); res = digSum(res); } a = digSum(digSum(a) * digSum(a)); n /= 2; } return res; } // Driver code int main() { int a = 9, n = 4; cout << powerDigitSum(a, n); return 0; } |
Java
// Java program to find single digit // sum of a^n. import java.util.*; import java.lang.*; import java.io.*; class GFG{ // This function finds single digit // sum of n. static int digSum( int n) { if (n == 0 ) return 0 ; return (n % 9 == 0 ) ? 9 : (n % 9 ); } // Returns single digit sum of a^n. // We use modular exponentiation technique. static int powerDigitSum( int a, int n) { int res = 1 ; while (n> 0 ) { if (n % 2 == 1 ) { res = res * digSum(a); res = digSum(res); } a = digSum(digSum(a) * digSum(a)); n /= 2 ; } return res; } // Driver code public static void main(String args[]) { int a = 9 , n = 4 ; System.out.print(powerDigitSum(a, n)); } } |
Python 3
# Python 3 Program to find single digit # sum of a^n. # This function finds single digit # sum of n. def digSum(n) : if n = = 0 : return 0 elif n % 9 = = 0 : return 9 else : return n % 9 # Returns single digit sum of a^n. # We use modular exponentiation technique. def powerDigitSum(a, n) : res = 1 while (n) : if n % 2 = = 1 : res = res * digSum(a) res = digSum(res) a = digSum(digSum(a) * digSum(a)) n / / = 2 return res # Driver Code if __name__ = = "__main__" : a, n = 9 , 4 print (powerDigitSum(a, n)) # This code is contributed by ANKITRAI1 |
C#
// C# program to find single // digit sum of a^n. class GFG { // This function finds single // digit sum of n. static int digSum( int n) { if (n == 0) return 0; return (n % 9 == 0) ? 9 : (n % 9); } // Returns single digit sum of a^n. // We use modular exponentiation // technique. static int powerDigitSum( int a, int n) { int res = 1; while (n > 0) { if (n % 2 == 1) { res = res * digSum(a); res = digSum(res); } a = digSum(digSum(a) * digSum(a)); n /= 2; } return res; } // Driver code static void Main() { int a = 9, n = 4; System.Console.WriteLine(powerDigitSum(a, n)); } } // This Code is contributed by mits |
PHP
<?php // PHP program to find single // digit sum of a^n. // This function finds single // digit sum of n. function digSum( $n ) { if ( $n == 0) return 0; return ( $n % 9 == 0) ? 9 : ( $n % 9); } // Returns single digit sum // of a^n. We use modular // exponentiation technique. function powerDigitSum( $a , $n ) { $res = 1; while ( $n ) { if ( $n % 2 == 1) { $res = $res * digSum( $a ); $res = digSum( $res ); } $a = digSum(digSum( $a ) * digSum( $a )); $n /= 2; } return $res ; } // Driver code $a = 9; $n = 4; echo powerDigitSum( $a , $n ); // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // javascript program to find single digit // sum of a^n. // This function finds single digit // sum of n. function digSum( n) { if (n == 0) return 0; return (n % 9 == 0) ? 9 : (n % 9); } // Returns single digit sum of a^n. // We use modular exponentiation technique. function powerDigitSum( a, n) { let res = 1; while (n) { if (n % 2 == 1) { res = res * digSum(a); res = digSum(res); } a = digSum(digSum(a) * digSum(a)); n /= 2; } return res; } // Driver code let a = 9, n = 4; document.write( powerDigitSum(a, n)); // This code is contributed by todaysgaurav </script> |
9
Time Complexity: O(log2n)// since in the powerDigitSum function in every call the value of n is divided by 2 until it reaches 1 thus the algorithm takes logarithmic time to execute.
Auxiliary Space: O(1) // since no extra array is used so the space taken by the algorithm is constant