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 Xint 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 codeint 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 Xdef 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 codea, b, c = 3, 2, 8print(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> |
Output:
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.
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!
