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 codeint 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 codepublic 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 Codeif __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 codestatic 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
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
