Dados a, b y c que son parte de la ecuación x = b * ( sumdigits(x) ^ a ) + c .
Donde sumdigits(x) determina la suma de todos los dígitos del número x. La tarea es encontrar todas las soluciones enteras para x que satisfagan la ecuación e imprimirlas en orden creciente.
Dado que, 1<=x<=10 9
Ejemplos:
Entrada: a = 3, b = 2, c = 8
Salida: 10 2008 13726
Los valores de x son: 10 2008 13726. Para 10, s(x) es 1; Poniendo el valor de s(x) en la ecuación b*(s(x)^a)+c obtenemos 10, y como 10 se encuentra en el rango 0<x<1e+9, por lo tanto 10 es una respuesta posible, similar para 2008 y 13726. Ningún otro valor de x satisface la ecuación para el valor dado de a, b y c
Entrada: a = 2, b = 2, c = -1
Salida: 1 31 337 967
Los valores de x que satisfacen la ecuación son: 1 31 337 967
Enfoque: sumdigits(x) puede estar en el rango de 1<=s(X)<=81 para el rango dado de x, es decir, 0<x<1e+9. Esto se debe a que el valor de x puede ser un mínimo de 0 donde sumdigits(x) = 0 y un máximo de 999999999 donde s umdigits(x) es 81. Entonces, primero repita del 1 al 81 para encontrar x a partir de la ecuación dada, luego verifique si la suma de los dígitos del número encontrado es igual al valor de sum sumdigits(x). Si ambos son iguales, aumente el contador y almacene el resultado en una array.
A continuación se muestra la implementación del enfoque anterior:
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 number
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
void 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 Code
int 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 equation
import java.util.Vector;
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 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 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 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 number def 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 numbers def 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 Code if __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 number
function 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 numbers
function 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 possible
value($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>
Producción:
1 31 337 967
Complejidad temporal: O(N)
Espacio auxiliar: O(N)