Given three integers A, B and C, the task is to find the count of values of X such that the following condition is satisfied,
X = B * Sm(X)A + C where Sm(X) denotes the sum of digits of X and 1 < X < 109.
Examples:
Input: A = 3, B = 2, C = 8
Output: 3
For X = 10, 2 * (1)3 + 8 = 10
For X = 2008, 2 * (10)3 + 8 = 2008
For X = 13726, 2 * (19)3 + 8 = 13726
Input: A = 2, B = 3, C = 10
Output: 1
Approach: An important observation can be made here that the sum of digits can be atmost 81 (i.e. X = 999999999) and corresponding to each sum of digits, we get a single value of X. So we can iterate through each sum of digit and check if the resulting value of X is valid or not.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count of // valid values of X int getCount( int a, int b, int c) { int count = 0; // Iterate through all possible // sum of digits of X for ( int i = 1; i <= 81; i++) { // Get current value of X for sum of digits i int cr = b * pow (i, a) + c; int tmp = cr; int sm = 0; // Find sum of digits of cr while (tmp) { sm += tmp % 10; tmp /= 10; } // If cr is a valid choice for X if (sm == i && cr < 1e9) count++; } // Return the count return count; } // Driver code int main() { int a = 3, b = 2, c = 8; cout << getCount(a, b, c); return 0; } |
Java
// Java implementation of the approach import java.io.*; class GfG { // Function to return the count of // valid values of X static int getCount( int a, int b, int c) { int count = 0 ; // Iterate through all possible // sum of digits of X for ( int i = 1 ; i <= 81 ; i++) { // Get current value of X for sum of digits i int cr = b * ( int )Math.pow(i, a) + c; int tmp = cr; int sm = 0 ; // Find sum of digits of cr while (tmp != 0 ) { sm += tmp % 10 ; tmp /= 10 ; } // If cr is a valid choice for X if (sm == i && cr < 1e9) count++; } // Return the count return count; } // Driver code public static void main(String[] args) { int a = 3 , b = 2 , c = 8 ; System.out.println(getCount(a, b, c)); } } // This code is contributed by Prerna Saini. |
Python3
# Python3 implementation of the approach # Function to return the count of # valid values of X def getCount(a, b, c): count = 0 # Iterate through all possible # sum of digits of X for i in range ( 1 , 82 ): # Get current value of X for # sum of digits i cr = b * pow (i, a) + c tmp = cr sm = 0 # Find sum of digits of cr while (tmp): sm + = tmp % 10 tmp / / = 10 # If cr is a valid choice for X if (sm = = i and cr < 10 * * 9 ): count + = 1 # Return the count return count # Driver code a, b, c = 3 , 2 , 8 print (getCount(a, b, c)) # This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System; class GFG { // Function to return the count of // valid values of X static int getCount( int a, int b, int c) { int count = 0; // Iterate through all possible // sum of digits of X for ( int i = 1; i <= 81; i++) { // Get current value of X for sum // of digits i int cr = b * ( int )Math.Pow(i, a) + c; int tmp = cr; int sm = 0; // Find sum of digits of cr while (tmp != 0) { sm += tmp % 10; tmp /= 10; } // If cr is a valid choice for X if (sm == i && cr < 1e9) count++; } // Return the count return count; } // Driver code public static void Main() { int a = 3, b = 2, c = 8; Console.Write(getCount(a, b, c)); } } // This code is contributed // by Akanksha Rai |
PHP
<?php // PHP implementation of the approach // Function to return the count of // valid values of X function getCount( $a , $b , $c ) { $count = 0; // Iterate through all possible // sum of digits of X for ( $i = 1; $i <= 81; $i ++) { // Get current value of X for sum of digits i $cr = $b * (int)pow( $i , $a ) + $c ; $tmp = $cr ; $sm = 0; // Find sum of digits of cr while ( $tmp != 0) { $sm += $tmp % 10; $tmp /= 10; } // If cr is a valid choice for X if ( $sm == $i && $cr < 1e9) $count ++; } // Return the count return $count ; } // Driver code { $a = 3; $b = 2; $c = 8; echo (getCount( $a , $b , $c )); } // This code is contributed by Code_Mech. |
Javascript
<script> // Javascript implementation of the above approach // Function to return the count of // valid values of X function getCount(a, b, c) { let count = 0; // Iterate through all possible // sum of digits of X for (let i = 1; i <= 81; i++) { // Get current value of X for sum of digits i let cr = b * Math.pow(i, a) + c; let tmp = cr; let sm = 0; // Find sum of digits of cr while (tmp != 0) { sm += tmp % 10; tmp = Math.floor(tmp / 10); } // If cr is a valid choice for X if (sm == i && cr < 1e9) count++; } // Return the count return count; } // driver program let a = 3, b = 2, c = 8; document.write(getCount(a, b, c)); </script> |
3
Time Complexity: O(k*d) where k = 81 and d is the number of digits of X for each corresponding value of k.
Auxiliary Space: O(1), since no extra space has been taken.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!