Find the number of solutions to the given equation

0 0 5 minutes read

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 < 10⁹.
Examples:

Input: A = 3, B = 2, C = 8
Output: 3
For X = 10, 2 * (1)³ + 8 = 10
For X = 2008, 2 * (10)³ + 8 = 2008
For X = 13726, 2 * (19)³ + 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>

Output:

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 zambiatek!