Recuento de números en el rango [L, R] que tienen la suma de los dígitos de su cuadrado igual al cuadrado de la suma de los dígitos

Dados dos enteros L y R, la tarea es encontrar el conteo de números en el rango [L, R] tal que la suma de los dígitos de su cuadrado sea igual al cuadrado de la suma de sus dígitos , 

Ejemplo :

Entrada: L = 22, R = 22
Salida: 1
Explicación: 22 es solo un número válido en este rango como 
suma de dígitos de su cuadrado = S(22*22) = S(484) = 16 y 
cuadrado de la suma de sus dígitos = S(22)*S(22) = 16

Entrada: L = 1, R = 58
Salida: 12
Explicación : los números totales válidos son {1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 30, 31}

Enfoque ingenuo:  Ejecute un ciclo de L a R y para cada número calcule la suma de los dígitos y verifique si el número actual cumple con la condición dada o no. 

Siga los pasos a continuación para resolver el problema:

• Iterar de L a R y para cada número calcular su suma de dígitos.
• Eleva al cuadrado el número actual y encuentra su suma de dígitos.
• Si son iguales, incremente la respuesta; de lo contrario, continúe con el siguiente elemento.

Complejidad de tiempo: O((RL)*log(R))

Enfoque eficiente: del ejemplo 2, podemos observar que todos los números válidos tienen dígitos del 0 al 3 únicamente . Por lo tanto, solo hay 4 opciones para cada dígito presente en un número. Use la recursividad para calcular todos los números válidos hasta R y compruebe si cumple o no la condición dada.

Siga los pasos a continuación para resolver el problema:

• Observe que todos los números válidos tienen dígitos desde [0,3].
• Los números entre [4,9] cuando se elevan al cuadrado llevan un arrastre sobre ellos.
  • S(4)*S(4) = 16 y S(16) = 7, 16 != 7.
  • S(5)*S(5) = 25 y S(25) = 7, 25 != 7.
• Entonces, genera todos los números posibles hasta la R .
• Para cada número generado hay un total de 4 opciones posibles entre [0,3].
• Calcula cada elección posible y comprueba la condición de cada una de ellas.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the number is valid
bool check(int num)
{
    // Sum of digits of num
    int sm = 0;
 
    // Squared number
    int num2 = num * num;
 
    while (num) {
        sm += num % 10;
        num /= 10;
    }
 
    // Sum of digits of (num * num)
    int sm2 = 0;
    while (num2) {
        sm2 += num2 % 10;
        num2 /= 10;
    }
    return ((sm * sm) == sm2);
}
 
// Function to convert a string to an integer
int convert(string s)
{
    int val = 0;
    reverse(s.begin(), s.end());
    int cur = 1;
    for (int i = 0; i < s.size(); i++) {
        val += (s[i] - '0') * cur;
        cur *= 10;
    }
    return val;
}
 
// Function to generate all possible
// strings of length len
void generate(string s, int len, set<int>& uniq)
{
    // Desired string
    if (s.size() == len) {
 
        // Take only valid numbers
        if (check(convert(s))) {
            uniq.insert(convert(s));
        }
        return;
    }
 
    // Recurse for all possible digits
    for (int i = 0; i <= 3; i++) {
        generate(s + char(i + '0'), len, uniq);
    }
}
 
// Function to calculate unique numbers
// in range [L, R]
int totalNumbers(int L, int R)
{
    // Initialize a variable
    // to store the answer
    int ans = 0;
 
    // Calculate the maximum
    // possible length
    int max_len = log10(R) + 1;
 
    // Set to store distinct
    // valid numbers
    set<int> uniq;
 
    for (int i = 1; i <= max_len; i++) {
        // Generate all possible strings
        // of length i
        generate("", i, uniq);
    }
 
    // Iterate the set to get the count
    // of valid numbers in the range [L,R]
    for (auto x : uniq) {
        if (x >= L && x <= R) {
            ans++;
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    int L = 22, R = 22;
    cout << totalNumbers(L, R);
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to check if the number is valid
static boolean check(int num)
{
   
    // Sum of digits of num
    int sm = 0;
 
    // Squared number
    int num2 = num * num;
 
    while (num > 0) {
        sm += num % 10;
        num /= 10;
    }
 
    // Sum of digits of (num * num)
    int sm2 = 0;
    while (num2>0) {
        sm2 += num2 % 10;
        num2 /= 10;
    }
    return ((sm * sm) == sm2);
}
 
// Function to convert a String to an integer
static int convert(String s)
{
    int val = 0;
    s = reverse(s);
    int cur = 1;
    for (int i = 0; i < s.length(); i++) {
        val += (s.charAt(i) - '0') * cur;
        cur *= 10;
    }
    return val;
}
 
// Function to generate all possible
// Strings of length len
static void generate(String s, int len, HashSet<Integer> uniq)
{
    // Desired String
    if (s.length() == len) {
 
        // Take only valid numbers
        if (check(convert(s))) {
            uniq.add(convert(s));
        }
        return;
    }
 
    // Recurse for all possible digits
    for (int i = 0; i <= 3; i++) {
        generate(s + (char)(i + '0'), len, uniq);
    }
}
static String reverse(String input) {
    char[] a = input.toCharArray();
    int l, r = a.length - 1;
    for (l = 0; l < r; l++, r--) {
        char temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return String.valueOf(a);
}
   
// Function to calculate unique numbers
// in range [L, R]
static int totalNumbers(int L, int R)
{
   
    // Initialize a variable
    // to store the answer
    int ans = 0;
 
    // Calculate the maximum
    // possible length
    int max_len = (int) (Math.log10(R) + 1);
 
    // Set to store distinct
    // valid numbers
    HashSet<Integer> uniq = new HashSet<Integer>();
 
    for (int i = 1; i <= max_len; i++) {
        // Generate all possible Strings
        // of length i
        generate("", i, uniq);
    }
 
    // Iterate the set to get the count
    // of valid numbers in the range [L,R]
    for (int x : uniq) {
        if (x >= L && x <= R) {
            ans++;
        }
    }
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int L = 22, R = 22;
    System.out.print(totalNumbers(L, R));
}
}
 
// This code is contributed by Princi Singh

# python 3 program for the above approach
 
from math import log10
# Function to check if the number is valid
def check(num):
    # Sum of digits of num
    sm = 0
 
    # Squared number
    num2 = num * num
 
    while (num):
        sm += num % 10
        num //= 10
 
    # Sum of digits of (num * num)
    sm2 = 0
    while (num2):
        sm2 += num2 % 10
        num2 //= 10
    return ((sm * sm) == sm2)
 
# Function to convert a string to an integer
def convert(s):
    val = 0
    s = s[::-1]
    cur = 1
    for i in range(len(s)):
        val += (ord(s[i]) - ord('0')) * cur
        cur *= 10
    return val
 
# Function to generate all possible
# strings of length len
def generate(s, len1, uniq):
    # Desired string
    if (len(s) == len1):
 
        # Take only valid numbers
        if(check(convert(s))):
            uniq.add(convert(s))
        return
 
    # Recurse for all possible digits
    for i in range(4):
        generate(s + chr(i + ord('0')), len1, uniq)
 
# Function to calculate unique numbers
# in range [L, R]
def totalNumbers(L, R):
    # Initialize a variable
    # to store the answer
    ans = 0
 
    # Calculate the maximum
    # possible length
    max_len = int(log10(R)) + 1
 
    # Set to store distinct
    # valid numbers
    uniq = set()
 
    for i in range(1,max_len+1,1):
        # Generate all possible strings
        # of length i
        generate("", i, uniq)
 
    # Iterate the set to get the count
    # of valid numbers in the range [L,R]
    for x in uniq:
        if (x >= L and x <= R):
            ans += 1
    return ans
 
# Driver Code
if __name__ == '__main__':
    L = 22
    R = 22
    print(totalNumbers(L, R))
     
    # This code is contributed by ipg2016107.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to check if the number is valid
static bool check(int num)
{
    // Sum of digits of num
    int sm = 0;
 
    // Squared number
    int num2 = num * num;
 
    while (num>0) {
        sm += num % 10;
        num /= 10;
    }
 
    // Sum of digits of (num * num)
    int sm2 = 0;
    while (num2>0) {
        sm2 += num2 % 10;
        num2 /= 10;
    }
    return ((sm * sm) == sm2);
}
 
// Function to convert a string to an integer
static int convert(string s)
{
    int val = 0;
    char[] charArray = s.ToCharArray();
    Array.Reverse( charArray );
    s = new string( charArray );
    int cur = 1;
    for (int i = 0; i < s.Length; i++) {
        val += ((int)s[i] - (int)'0') * cur;
        cur *= 10;
    }
    return val;
}
 
// Function to generate all possible
// strings of length len
static void generate(string s, int len, HashSet<int> uniq)
{
    // Desired string
    if (s.Length == len) {
 
        // Take only valid numbers
        if (check(convert(s))) {
            uniq.Add(convert(s));
        }
        return;
    }
 
    // Recurse for all possible digits
    for (int i = 0; i <= 3; i++) {
        generate(s + Convert.ToChar(i + (int)'0'), len, uniq);
    }
}
 
// Function to calculate unique numbers
// in range [L, R]
static int totalNumbers(int L, int R)
{
    // Initialize a variable
    // to store the answer
    int ans = 0;
 
    // Calculate the maximum
    // possible length
    int max_len = (int)Math.Log10(R) + 1;
 
    // Set to store distinct
    // valid numbers
    HashSet<int> uniq = new HashSet<int>();
 
    for (int i = 1; i <= max_len; i++) {
        // Generate all possible strings
        // of length i
        generate("", i, uniq);
    }
 
    // Iterate the set to get the count
    // of valid numbers in the range [L,R]
    foreach (int x in uniq) {
        if (x >= L && x <= R) {
            ans++;
        }
    }
    return ans;
}
 
// Driver Code
public static void Main()
{
    int L = 22, R = 22;
    Console.Write(totalNumbers(L, R));
}
 
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
// Javascript program for the above approach
 
// Function to check if the number is valid
function check(num)
{
 
  // Sum of digits of num
  let sm = 0;
 
  // Squared number
  let num2 = num * num;
 
  while (num) {
    sm += num % 10;
    num = Math.floor(num / 10);
  }
 
  // Sum of digits of (num * num)
  let sm2 = 0;
  while (num2) {
    sm2 += num2 % 10;
    num2 = Math.floor(num2 / 10);
  }
  return sm * sm == sm2;
}
 
// Function to convert a string to an integer
function convert(s) {
  let val = 0;
  s = s.split("").reverse().join("");
  let cur = 1;
 
  for (let i = 0; i < s.length; i++) {
    val += (s[i].charCodeAt(0) - "0".charCodeAt(0)) * cur;
    cur *= 10;
  }
  return val;
}
 
// Function to generate all possible
// strings of length len
function generate(s, len, uniq) {
  // Desired string
  if (s.length == len) {
    // Take only valid numbers
    if (check(convert(s))) {
      uniq.add(convert(s));
    }
    return;
  }
 
  // Recurse for all possible digits
  for (let i = 0; i <= 3; i++) {
    generate(s + String.fromCharCode(i + "0".charCodeAt(0)), len, uniq);
  }
}
 
// Function to calculate unique numbers
// in range [L, R]
function totalNumbers(L, R) {
  // Initialize a variable
  // to store the answer
  let ans = 0;
 
  // Calculate the maximum
  // possible length
  let max_len = Math.log10(R) + 1;
 
  // Set to store distinct
  // valid numbers
  let uniq = new Set();
 
  for (let i = 1; i <= max_len; i++) {
    // Generate all possible strings
    // of length i
    generate("", i, uniq);
  }
 
  // Iterate the set to get the count
  // of valid numbers in the range [L,R]
  for (let x of uniq) {
    if (x >= L && x <= R) {
      ans++;
    }
  }
  return ans;
}
 
// Driver Code
let L = 22,
  R = 22;
document.write(totalNumbers(L, R));
 
// This code is contributed by _saurabh_jaiswal.
</script>

Producción:

1

Complejidad de tiempo: ( , dado que hay 4 opciones para cada uno de los dígitos hasta la longitud de R , es decir, log10 (R) + 1, por lo tanto, la complejidad de tiempo sería exponencial.

Espacio auxiliar:    (espacio de pila recursivo)