Se le da un número entero n, encuentre la raíz entera positiva más pequeña de la ecuación x, o imprima -1 si no se encuentran raíces.
Ecuación: x^2 + s(x)*x – n = 0
donde x, n son números enteros positivos, s(x) es la función, igual a la suma de los dígitos del número x en el sistema numérico decimal.
1 <= norte <= 10^18
Ejemplos:
Input: N = 110
Output: 10
Explanation: x = 10 is the minimum root.
As s(10) = 1 + 0 = 1 and
102 + 1*10 - 110=0.
Input: N = 4
Output: -1
Explanation: there are no roots of the
equation possible
Un enfoque ingenuo será iterar a través de todos los valores posibles de X y averiguar si existe alguna raíz de este tipo, pero esto no será posible ya que el valor de n es muy grande.
Un enfoque eficiente sería el siguiente
. En primer lugar, encontremos el intervalo de valores posibles de s(x). Por lo tanto, x ^ 2 <= N y N <= 10 ^ 18, x <= 109. En otras palabras, para cada solución considerable x, la longitud decimal de x no se extiende 10 dígitos. Entonces Smax = s(9999999999) = 10*9 = 90.
Hagamos fuerza bruta en el valor de s(x) (0 <= s(x) <= 90). Ahora tenemos una ecuación cuadrada ordinaria. El trato es resolver la ecuación y comprobar que el valor actual de fuerza bruta de s(x) es igual a la suma de los dígitos de la solución. Si la solución existe y se mantiene la igualdad, debemos obtener la respuesta y almacenar el mínimo posible de raíces.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find smallest value of root
// of an equation under given constraints.
#include <bits/stdc++.h>
using namespace std;
// function to check if the sum of digits is
// equal to the summation assumed
bool check(long long a, long long b)
{
long long int c = 0;
// calculate the sum of digit
while (a != 0) {
c = c + a % 10;
a = a / 10;
}
return (c == b);
}
// function to find the largest root possible.
long long root(long long n)
{
bool found = 0;
long long mx = 1e18;
// iterate for all possible sum of digits.
for (long long i = 0; i <= 90; i++) {
// check if discriminant is a perfect square.
long long s = i * i + 4 * n;
long long sq = sqrt(s);
// check if discriminant is a perfect square and
// if it as perfect root of the equation
if (sq * sq == s && check((sq - i) / 2, i)) {
found = 1;
mx = min(mx, (sq - i) / 2);
}
}
// function returns answer
if (found)
return mx;
else
return -1;
}
// driver program to check the above function
int main()
{
long long n = 110;
cout << root(n);
}
Java
// Java program to find smallest value of root
// of an equation under given constraints.
class GFG{
// function to check if the sum of digits is
// equal to the summation assumed
static boolean check(long a, long b)
{
long c = 0;
// calculate the sum of digit
while (a != 0) {
c = c + a % 10;
a = a / 10;
}
return (c == b);
}
// function to find the largest root possible.
static long root(long n)
{
boolean found = false;
long mx = (long)1E18;
// iterate for all possible sum of digits.
for (long i = 0; i <= 90; i++) {
// check if discriminant is a perfect square.
long s = i * i + 4 * n;
long sq = (long)Math.sqrt(s);
// check if discriminant is a perfect square and
// if it as perfect root of the equation
if (sq * sq == s && check((sq - i) / 2, i)) {
found = true;
mx = Math.min(mx, (sq - i) / 2);
}
}
// function returns answer
if (found)
return mx;
else
return -1;
}
// driver program to check the above function
public static void main(String[] args)
{
long n = 110;
System.out.println(root(n));
}
}
// This code is contributed by mits
Python3
# Python3 program to find smallest # value of root of an equation # under given constraints. import math # function to check if the sum # of digits is equal to the # summation assumed def check(a, b): c = 0; # calculate the # sum of digit while (a != 0): c = c + a % 10; a = int(a / 10); return True if(c == b) else False; # function to find the # largest root possible. def root(n): found = False; # float(1E+18) mx = 1000000000000000001; # iterate for all # possible sum of digits. for i in range(91): # check if discriminant # is a perfect square. s = i * i + 4 * n; sq = int(math.sqrt(s)); # check if discriminant is # a perfect square and # if it as perfect root # of the equation if (sq * sq == s and check(int((sq - i) / 2), i)): found = True; mx = min(mx, int((sq-i) / 2)); # function returns answer if (found): return mx; else: return -1; # Driver Code n = 110; print(root(n)); # This code is contributed by mits
C#
//C# program to find smallest value of root
// of an equation under given constraints.
using System;
public class GFG{
// function to check if the sum of digits is
// equal to the summation assumed
static bool check(long a, long b)
{
long c = 0;
// calculate the sum of digit
while (a != 0) {
c = c + a % 10;
a = a / 10;
}
return (c == b);
}
// function to find the largest root possible.
static long root(long n)
{
bool found = false;
long mx = (long)1E18;
// iterate for all possible sum of digits.
for (long i = 0; i <= 90; i++) {
// check if discriminant is a perfect square.
long s = i * i + 4 * n;
long sq = (long)Math.Sqrt(s);
// check if discriminant is a perfect square and
// if it as perfect root of the equation
if (sq * sq == s && check((sq - i) / 2, i)) {
found = true;
mx = Math.Min(mx, (sq - i) / 2);
}
}
// function returns answer
if (found)
return mx;
else
return -1;
}
// driver program to check the above function
public static void Main()
{
long n = 110;
Console.Write(root(n));
}
}
// This code is contributed by Raput-Ji
PHP
<?php
// PHP program to find
// smallest value of root
// of an equation under
// given constraints.
// function to check if
// the sum of digits is
// equal to the summation
// assumed
function check($a, $b)
{
$c = 0;
// calculate the
// sum of digit
while ($a != 0)
{
$c = $c + $a % 10;
$a = (int)($a / 10);
}
return ($c == $b) ? true : false;
}
// function to find the
// largest root possible.
function root($n)
{
$found = false;
// float(1E+18)
$mx = 1000000000000000001;
// iterate for all
// possible sum of digits.
for ($i = 0; $i <= 90; $i++)
{
// check if discriminant
// is a perfect square.
$s = $i * $i + 4 * $n;
$sq = (int)(sqrt($s));
// check if discriminant is
// a perfect square and
// if it as perfect root
// of the equation
if ($sq * $sq == $s &&
check((int)(($sq - $i) / 2), $i))
{
$found = true;
$mx = min($mx, (int)(($sq -
$i) / 2));
}
}
// function returns answer
if ($found)
return $mx;
else
return -1;
}
// Driver Code
$n = 110;
echo root($n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find smallest
// value of root of an equation under
// given constraints.
// Function to check if the sum of digits is
// equal to the summation assumed
function check(a, b)
{
var c = 0;
// Calculate the sum of digit
while (a != 0)
{
c = c + a % 10;
a = parseInt(a / 10);
}
return (c == b);
}
// Function to find the largest root possible.
function root(n)
{
var found = false;
var mx = 1E18;
// Iterate for all possible
// sum of digits.
for(i = 0; i <= 90; i++)
{
// Check if discriminant is a
// perfect square.
var s = i * i + 4 * n;
var sq = Math.sqrt(s);
// Check if discriminant is a
// perfect square and if it as
// perfect root of the equation
if (sq * sq == s && check((sq - i) / 2, i))
{
found = true;
mx = Math.min(mx, (sq - i) / 2);
}
}
// Function returns answer
if (found)
return mx;
else
return -1;
}
// Driver code
var n = 110;
document.write(root(n));
// This code is contributed by todaysgaurav
</script>
Producción:
10
Complejidad de tiempo : O (90 * log (sqrt (N))), ya que estamos usando bucles anidados para recorrer 90 * log (sqrt (N)) veces.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.