Given a, b and c which are part of the equation x = b * ( sumdigits(x) ^ a ) + c.
Where sumdigits(x) determines the sum of all digits of the number x. The task is to find out all integer solutions for x that satisfy the equation and print them in increasing order.
Given that, 1<=x<=109
Examples:
Input: a = 3, b = 2, c = 8
Output: 10 2008 13726
Values of x are: 10 2008 13726. For 10, s(x) is 1; Putting value of s(x) in equation b*(s(x)^a)+c we get 10, and as 10 lies in range 0<x<1e+9, therefore 10 is a possible answer, similar for 2008 and 13726. No other value of x satisfies the equation for the given value of a, b and c
Input: a = 2, b = 2, c = -1
Output: 1 31 337 967
Values of x that satisfy the equation are: 1 31 337 967
Approach: sumdigits(x) can be in the range of 1<=s(X)<=81 for the given range of x i.e 0<x<1e+9. This is because the value of x can be minimum 0 where sumdigits(x)=0 and maximum 999999999 where sumdigits(x) is 81. So first iterate through 1 to 81 to find x from the given equation, then cross-check if the sum of digits of the number found, is the same as the value of sum sumdigits(x). If both are the same then increase the counter and store the result in an array.
Below is the implementation of the above approach:
C++
// C++ program to find the numbers of// values that satisfy the equation#include <bits/stdc++.h>using namespace std;// This function returns the sum of// the digits of a numberint getsum(int a){ int r = 0, sum = 0; while (a > 0) { r = a % 10; sum = sum + r; a = a / 10; } return sum;}// This function creates// the array of valid numbersvoid value(int a, int b, int c){ int co = 0, p = 0; int no, r = 0, x = 0, q = 0, w = 0; vector<int> v; for (int i = 1; i < 82; i++) { // this computes s(x)^a no = pow((double)i, double(a)); // this gives the result of equation no = b * no + c; if (no > 0 && no < 1000000000) { x = getsum(no); // checking if the sum same as i if (x == i) { // counter to keep track of numbers q++; // resultant array v.push_back(no); w++; } } } // prints the number for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; }}// Driver Codeint main(){ int a = 2, b = 2, c = -1; // calculate which value // of x are possible value(a, b, c); return 0;} |
Java
// Java program to find the numbers of// values that satisfy the equationimport java.util.Vector;class GFG{// This function returns the sum of// the digits of a numberstatic int getsum(int a){ int r = 0, sum = 0; while (a > 0) { r = a % 10; sum = sum + r; a = a / 10; } return sum;}// This function creates// the array of valid numbersstatic void value(int a, int b, int c){ int co = 0, p = 0; int no, r = 0, x = 0, q = 0, w = 0; Vector<Integer> v = new Vector<Integer>(); for (int i = 1; i < 82; i++) { // this computes s(x)^a no = (int) Math.pow(i, a); // this gives the result of equation no = b * no + c; if (no > 0 && no < 1000000000) { x = getsum(no); // checking if the sum same as i if (x == i) { // counter to keep track of numbers q++; // resultant array v.add(no); w++; } } } // prints the number for (int i = 0; i < v.size(); i++) { System.out.print(v.get(i)+" "); }}// Driver Codepublic static void main(String[] args){ int a = 2, b = 2, c = -1; // calculate which value // of x are possible value(a, b, c); }} // This code is contributed by // PrinciRaj1992 |
Python 3
# Python 3 program to find the numbers # of values that satisfy the equation# This function returns the sum # of the digits of a numberdef getsum(a): r = 0 sum = 0 while (a > 0) : r = a % 10 sum = sum + r a = a // 10 return sum# This function creates# the array of valid numbersdef value(a, b, c): x = 0 q = 0 w = 0 v = [] for i in range(1, 82) : # this computes s(x)^a no = pow(i, a) # this gives the result # of equation no = b * no + c if (no > 0 and no < 1000000000) : x = getsum(no) # checking if the sum same as i if (x == i) : # counter to keep track # of numbers q += 1 # resultant array v.append(no) w += 1 # prints the number for i in range(len(v)) : print(v[i], end = " ")# Driver Codeif __name__ == "__main__": a = 2 b = 2 c = -1 # calculate which value # of x are possible value(a, b, c)# This code is contributed # by ChitraNayal |
C#
// C# program to find the numbers of // values that satisfy the equation using System;using System.Collections.Generic;class GFG { // This function returns the sum of // the digits of a number static int getsum(int a) { int r = 0, sum = 0; while (a > 0) { r = a % 10; sum = sum + r; a = a / 10; } return sum; } // This function creates // the array of valid numbers static void value(int a, int b, int c) { int no, x = 0, q = 0, w = 0; List<int> v = new List<int>(); for (int i = 1; i < 82; i++) { // this computes s(x)^a no = (int) Math.Pow(i, a); // this gives the result of equation no = b * no + c; if (no > 0 && no < 1000000000) { x = getsum(no); // checking if the sum same as i if (x == i) { // counter to keep track of numbers q++; // resultant array v.Add(no); w++; } } } // prints the number for (int i = 0; i < v.Count; i++) { Console.Write(v[i]+" "); } } // Driver Code public static void Main(String[] args) { int a = 2, b = 2, c = -1; // calculate which value // of x are possible value(a, b, c); } }// This code has been contributed by Rajput-Ji |
PHP
<?php// PHP program to find the numbers of// values that satisfy the equation// This function returns the sum of// the digits of a numberfunction getsum($a){ $r = 0; $sum = 0; while ($a > 0) { $r = $a % 10; $sum = $sum + $r; $a = (int)($a / 10); } return $sum;}// This function creates// the array of valid numbersfunction value($a, $b, $c){ $co = 0; $p = 0; $no; $r = 0; $x = 0; $q = 0; $w = 0; $v = array(); $u = 0; for ($i = 1; $i < 82; $i++) { // this computes s(x)^a $no = pow($i, $a); // this gives the result // of equation $no = $b * $no + $c; if ($no > 0 && $no < 1000000000) { $x = getsum($no); // checking if the // sum same as i if ($x == $i) { // counter to keep // track of numbers $q++; // resultant array $v[$u++] = $no; $w++; } } } // prints the number for ($i = 0; $i < $u; $i++) { echo $v[$i] . " "; }}// Driver Code$a = 2;$b = 2;$c = -1;// calculate which value// of x are possiblevalue($a, $b, $c);// This code is contributed // by mits?> |
Javascript
<script>// Javascript program to find the numbers of// values that satisfy the equation // This function returns the sum of// the digits of a number function getsum(a) { let r = 0, sum = 0; while (a > 0) { r = a % 10; sum = sum + r; a = Math.floor(a / 10); } return sum; } // This function creates // the array of valid numbers function value(a,b,c) { let co = 0, p = 0; let no, r = 0, x = 0, q = 0, w = 0; let v = []; for (let i = 1; i < 82; i++) { // this computes s(x)^a no = Math.pow(i, a); // this gives the result of equation no = b * no + c; if (no > 0 && no < 1000000000) { x = getsum(no); // checking if the sum same as i if (x == i) { // counter to keep track of numbers q++; // resultant array v.push(no); w++; } } } // prints the number for (let i = 0; i < v.length; i++) { document.write(v[i]+" "); } } // Driver Code let a = 2, b = 2, c = -1; // calculate which value // of x are possible value(a, b, c); // This code is contributed by avanitrachhadiya2155</script> |
Output:
1 31 337 967
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
