Given very large numbers n and x, we need to find the sum of digits of n^x such that :
If n^x < 10
digSum(n^x) = n^x
Else
digSum(n^x) = Sum(digSum(n^x))
Examples:
Input : 5 4 Output : 4 We know 54 = 625 Sum of digits in 625 = 6 + 2 + 5 = 13 Sum of digits in 13 = 1 + 3 = 4 Input : 546878 56422 Output : 7
Prerequisite : Recursive sum of digits.
The idea is:
Sum of digits repeats after every 6th exponents.
Let SoD(n) = a
Let b = x % 6
then
SoD(n^x) = SoD(a^b) except for b = 1 when a = 3 & 6
SoD(n^x) = 9 forall x > 1, when a = 3 & 6
C++
// CPP Code for Sum of// digit of n^x where// n and x are very large#include <bits/stdc++.h>using namespace std; // function to get sum// of digits of a number long digSum(long n) { if (n == 0) return 0; return (n % 9 == 0) ? 9 : (n % 9); } // function to return sum long PowDigSum(long n, long x) { // Find sum of digits in n long sum = digSum(n); // Find remainder of exponent long rem = x % 6; if ((sum == 3 || sum == 6) && x > 1) return 9; else if (x == 1) return sum; else if (x == 0) return 1; else if (rem == 0) return digSum((long)pow(sum, 6)); else return digSum((long)pow(sum, rem)); } // Driver codeint main(){ int n = 33333; int x = 332654; cout << PowDigSum(n, x); return 0;}// This code is contributed by Gitanjali. |
Java
// Java Code for // Sum of digit of // n^x where n and// x are very largeimport java.util.*;class GFG { // function to get sum // of digits of a number static long digSum(long n) { if (n == 0) return 0; return (n % 9 == 0) ? 9 : (n % 9); } // function to return sum static long PowDigSum(long n, long x) { // Find sum of digits in n long sum = digSum(n); // Find remainder of exponent long rem = x % 6; if ((sum == 3 || sum == 6) && x > 1) return 9; else if (x == 1) return sum; else if (x == 0) return 1; else if (rem == 0) return digSum((long)Math.pow(sum, 6)); else return digSum((long)Math.pow(sum, rem)); } /* Driver program to test above function */ public static void main(String[] args) { int n = 33333; int x = 332654; System.out.println(PowDigSum(n, x)); }}// This code is contributed by Arnav Kr. Mandal. |
Python3
# Python3 Code for Sum# of digit of n^x import math # function to get # sum of digits of# a numberdef digSum(n): if (n == 0): return 0 if n % 9==0 : return 9 else: return (n % 9) # function to return sumdef PowDigSum(n, x): # Find sum of # digits in n sum = digSum(n) # Find remainder # of exponent rem = x % 6 if ((sum == 3 or sum == 6) and x > 1): return 9 elif (x == 1): return sum elif (x == 0): return 1 elif (rem == 0): return digSum(math.pow(sum, 6)) else: return digSum(math.pow(sum, rem)) # Driver methodn = 33333x = 332654print (PowDigSum(n, x))# This code is contributed by Gitanjali |
C#
// C# Code for Sum of digit of // n^x where n and x are very largeusing System;class GFG { // Function to get sum // of digits of a number static long digSum(long n) { if (n == 0) return 0; return (n % 9 == 0) ? 9 : (n % 9); } // Function to return sum static long PowDigSum(long n, long x) { // Find sum of digits in n long sum = digSum(n); // Find remainder of exponent long rem = x % 6; if ((sum == 3 || sum == 6) && x > 1) return 9; else if (x == 1) return sum; else if (x == 0) return 1; else if (rem == 0) return digSum((long)Math.Pow(sum, 6)); else return digSum((long)Math.Pow(sum, rem)); } // Driver Code public static void Main() { int n = 33333; int x = 332654; Console.WriteLine(PowDigSum(n, x)); }}// This code is contributed by vt_m. |
PHP
<?php// PHP Code for Sum of// digit of n^x where// function to get sum// of digits of a numberfunction digSum($n) { if ($n == 0) return 0; return ($n % 9 == 0) ? 9 : ($n % 9); } // function to return sum function PowDigSum($n, $x) { // Find sum of digits in n $sum = digSum($n); // Find remainder of exponent $rem = $x % 6; if (($sum == 3 || $sum == 6) && $x > 1) return 9; else if ($x == 1) return $sum; else if ($x == 0) return 1; else if ($rem == 0) return digSum(pow($sum, 6)); else return digSum(pow($sum, $rem)); } // Driver code $n = 33333; $x = 332654; echo PowDigSum($n, $x);// This code is contributed by aj_36.?> |
Javascript
<script>// JavaScript Code for Sum of// digit of n^x where// n and x are very large // function to get sum// of digits of a number function digSum(n) { if (n == 0) return 0; return (n % 9 == 0) ? 9 : (n % 9); } // function to return sum function PowDigSum(n, x) { // Find sum of digits in n let sum = digSum(n); // Find remainder of exponent let rem = x % 6; if ((sum == 3 || sum == 6) && x > 1) return 9; else if (x == 1) return sum; else if (x == 0) return 1; else if (rem == 0) return digSum(Math.pow(sum, 6)); else return digSum(Math.pow(sum, rem)); } // Driver codelet n = 33333;let x = 332654;document.write(PowDigSum(n, x));</script> |
Output:
9
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!