Count of numbers whose sum of increasing powers of digits is equal to the number itself
Given an integer N, the task is to count all the integers less than or equal to N that follow the property where the sum of their digits raised to the power (starting from 1 and increased by 1 each time) is equal to the integer itself i.e. if D1D2D3…DN is an N digit number then for it to satisfy the given property (D11 + D22 + D33 + … + DNN) must be equal to D1D2D3…DN.
Examples:
Input: N = 100
Output: 11
01 = 0
11 = 1
21 = 2
…
91 = 9
81 + 92 = 8 + 81 = 89
Input: N = 200
Output: 13
Approach: Initialise count = 0 and for every number from 0 to N, find the sum of digits raised to the increasing power and if the resultant sum is equal to the number itself then increment the count. Finally, print the count.
Below is the implementation of the above approach:
CPP
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the // count of digits of n int countDigits( int n) { int cnt = 0; while (n > 0) { cnt++; n /= 10; } return cnt; } // Function to return the sum of // increasing powers of N int digitPowSum( int n) { // To store the required answer int sum = 0; // Count of digits in n which will // be the power of the last digit int pw = countDigits(n); // While there are digits left while (n > 0) { // Get the last digit int d = n % 10; // Add the last digit after raising // it to the required power sum += pow (d, pw); // Decrement the power for // the previous digit pw--; // Remove the last digit n /= 10; } return sum; } // Function to return the count // of integers which satisfy // the given conditions int countNum( int n) { int count = 0; for ( int i = 0; i <= n; i++) { // If current element satisfies // the given condition if (i == digitPowSum(i)) { count++; } } return count; } // Driver code int main() { int n = 200; cout << countNum(n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the // count of digits of n static int countDigits( int n) { int cnt = 0 ; while (n > 0 ) { cnt++; n /= 10 ; } return cnt; } // Function to return the sum of // increasing powers of N static int digitPowSum( int n) { // To store the required answer int sum = 0 ; // Count of digits in n which will // be the power of the last digit int pw = countDigits(n); // While there are digits left while (n > 0 ) { // Get the last digit int d = n % 10 ; // Add the last digit after raising // it to the required power sum += Math.pow(d, pw); // Decrement the power for // the previous digit pw--; // Remove the last digit n /= 10 ; } return sum; } // Function to return the count // of integers which satisfy // the given conditions static int countNum( int n) { int count = 0 ; for ( int i = 0 ; i <= n; i++) { // If current element satisfies // the given condition if (i == digitPowSum(i)) { count++; } } return count; } // Driver code public static void main (String[] args) { int n = 200 ; System.out.println(countNum(n)); } } // This code is contributed by AnkitRai01 |
Python
# Python3 implementation of the approach # Function to return the # count of digits of n def countDigits(n): cnt = 0 while (n > 0 ): cnt + = 1 n / / = 10 return cnt # Function to return the sum of # increasing powers of N def digitPowSum(n): # To store the required answer sum = 0 # Count of digits in n which will # be the power of the last digit pw = countDigits(n) # While there are digits left while (n > 0 ): # Get the last digit d = n % 10 # Add the last digit after raising # it to the required power sum + = pow (d, pw) # Decrement the power for # the previous digit pw - = 1 # Remove the last digit n / / = 10 return sum # Function to return the count # of integers which satisfy # the given conditions def countNum(n): count = 0 for i in range (n + 1 ): # If current element satisfies # the given condition if (i = = digitPowSum(i)): count + = 1 return count # Driver code n = 200 print (countNum(n)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the // count of digits of n static int countDigits( int n) { int cnt = 0; while (n > 0) { cnt++; n /= 10; } return cnt; } // Function to return the sum of // increasing powers of N static int digitPowSum( int n) { // To store the required answer int sum = 0; // Count of digits in n which will // be the power of the last digit int pw = countDigits(n); // While there are digits left while (n > 0) { // Get the last digit int d = n % 10; // Add the last digit after raising // it to the required power sum += ( int ) Math.Pow(d, pw); // Decrement the power for // the previous digit pw--; // Remove the last digit n /= 10; } return sum; } // Function to return the count // of integers which satisfy // the given conditions static int countNum( int n) { int count = 0; for ( int i = 0; i <= n; i++) { // If current element satisfies // the given condition if (i == digitPowSum(i)) count++; } return count; } // Driver code public static void Main (String[] args) { int n = 200; Console.WriteLine(countNum(n)); } } // This code is contributed by // sanjeev2552 |
Javascript
<script> // JavaScript implementation of the approach // Function to return the // count of digits of n function countDigits(n) { let cnt = 0; while (n > 0) { cnt++; n = Math.floor(n / 10); } return cnt; } // Function to return the sum of // increasing powers of N function digitPowSum(n) { // To store the required answer let sum = 0; // Count of digits in n which will // be the power of the last digit let pw = countDigits(n); // While there are digits left while (n > 0) { // Get the last digit let d = n % 10; // Add the last digit after raising // it to the required power sum += Math.pow(d, pw); // Decrement the power for // the previous digit pw--; // Remove the last digit n = Math.floor(n / 10); } return sum; } // Function to return the count // of integers which satisfy // the given conditions function countNum(n) { let count = 0; for (let i = 0; i <= n; i++) { // If current element satisfies // the given condition if (i == digitPowSum(i)) { count++; } } return count; } // Driver code let n = 200; document.write(countNum(n)); // This code is contributed by Surbhi Tyagi. </script> |
13
Time Complexity: O(n * 2log10n)
Auxiliary Space: O(1)
Contact Us