Encontrar el número más pequeño cuyos dígitos suman n -- java campo con beginner campo con performance campo con algorithm camp codereview Relacionados El problema

Finding the smallest number whose digits sum to N


9
vote

problema

Español

Probé mi mano en un programa de examen de placa de grado XII:

Dado dos números positivos M y N, de modo que M está entre 100 y 10000 y N es menor que 100, encuentre el entero más pequeño que sea mayor que M y cuyos dígitos se suman a N. por ejemplo, si M = 100 y n = 11, el número mínimo es 119 cuyos dígitos se suman a N. Escriba un programa para aceptar los números M y N del usuario e imprimir el número más pequeño requerido cuya suma de todos sus dígitos es igual a N. también, imprimir El número total de dígitos presentes en el número requerido. El programa debe verificar la validez de las entradas y mostrar un mensaje apropiado para una entrada no válida.

Resolví el programa, pero como una persona curiosa, me encantaría saber cómo aumentar su eficiencia, los retrasos en el tiempo del compilador y si el programa podría ser aún más corto. Entonces, la pregunta principal es, ¿qué modificaciones deben hacerse en mi código para que se vuelva más compilador y eficiente?

  A overlaps with C. B overlaps with D. D overlaps with E. 6  
Original en ingles

I tried my hand at a grade XII Board exam program:

Given two positive numbers M and N, such that M is between 100 and 10000 and N is less than 100, find the smallest integer that is greater than M and whose digits add up to N. For example, if M = 100 and N = 11, the minimum number is 119 whose digits add up to N. Write a program to accept the numbers M and N from the user and print the smallest required number whose sum of all its digits is equal to N. Also, print the total number of digits present in the required number. The program should check for the validity of the inputs and display an appropriate message for an invalid input.

I solved the program, but as a curious person, I would love to know how to increase it's efficiency, compiler time delays, and if the program could be even shorter in length. So the primary question is, what modifications need be made in my code so that it becomes more compiler-friendly and efficient?

import java.util.Scanner; public class ISC { static Scanner sc =new Scanner(System.in); static int m,n; static int ndigit; void input(){ System.out.println("Enter the value of M: "); m = sc.nextInt(); if (m>=100&&m<=10000) { } else {     System.out.println("INVALID, Enter again: ");     while (!(m>=100&&m<=10000)){         m = sc.nextInt();     } }  System.out.println("Enter the value of N: "); n = sc.nextInt(); if (n>=1&&n<=100){     //do nothing } else {     System.out.println("INVALID INPUT, Enter again");     while (!(n>=1&&n<=100)){         n = sc.nextInt();     }  } }  static int sumOfDigits(int n){ int sum = 0; String a = Integer.toString(n); int digit; for (int i = 0; i<a.length();i++){     digit = Integer.parseInt(Character.toString(a.charAt(i)));     sum += digit;   } return sum; }  static int getNo(){ ndigit = 0; for (int i = m; i<=10000;i++){     if (sumOfDigits(i)==n){         ndigit = (Integer.toString(i)).length();         return i;     }  } return 0; }  public static void main(String[] args){ ISC a = new ISC(); a.input(); if (getNo()==0) System.out.println("NO NUMBER FOUND"); else {   System.out.println("Minimum number is: " + getNo());   System.out.println("Total number of digits: " + ndigit); } } } 
           
   
   

Lista de respuestas

11
 
vote
vote
La mejor respuesta
 

El programa debe parecer más así:

  public static void main(String[] args) {     int m = askInt("Enter the value of M: ", 100, 10000),         n = askInt("Enter the value of N: ", 1, 100);     long solution = findSolution(m, n);     System.out.println("Minimum number is: " + solution);     System.out.println("Total number of digits: " + numberOfDigits(solution)); }   

Diferencias notables:

  • Su programa no está orientado a objetos de todos modos, por lo que no hay un punto en la creación de instancias a y llamando 9988777665544332 como método de instancia. (Además, es raro que input()3 , que es un método de instancia, almacena sus resultados en 9988777665544334 variables en lugar de las variables de ejemplo).
  • Hay mucha repetición dentro de input() . Una rutina de impulsión de enteros de propósito general, utilizada para m y n , sería mejor.
  • m , n , y ndigit no debe ser variables estáticas, ya que eso las hace esencialmente variables globales. Cualquier función en la clase puede alterar sus valores como un efecto secundario, lo que hace que su código sea más difícil de analizar, debe leer todo el código para comprender cualquiera de ello.
  • La solución debe ser un long , en caso n es grande. Como se señaló @oletange, si N es 99, entonces la solución debe ser al menos 99999999999, que no cabe en un 99887766555443310 . Tenga en cuenta que la enumeración de la fuerza bruta es una estrategia muy pobre para números tan grandes.

Aquí es cómo escribiría a1 :

  a2  

Tenga en cuenta que devuelve un valor a la persona que llama, en lugar de establecer una variable como un efecto secundario.


Suponiendo que nos pegamos con su algoritmo de fuerza bruta (y de hecho hay una manera mucho más rápida), estas funciones podrían mejorarse:

  a3  

La aritmética es preferible para convertir los números a las cuerdas y la espalda. Tenga en cuenta que el proceso de enchufe en sí mismo implica operaciones aritméticas similares, y por lo tanto debe ser más lento que la aritmética. Tratar con cadenas también incurre en un costo para asignar la memoria para ellos.

He elegido a4 a medida que los nombres de los parámetros para evitar confusiones con el n en la declaración del problema.


En cuanto a la búsqueda de la solución, hay dos errores:

  • El problema requiere que la solución sea estrictamente mayor que m .
  • .
  • El problema no afirma que la solución debe limitarse a 10000. (por ejemplo, dado m = 10000 y n = 2, la solución debe ser 10001. )
  a5  
 

The program should look more like this:

public static void main(String[] args) {     int m = askInt("Enter the value of M: ", 100, 10000),         n = askInt("Enter the value of N: ", 1, 100);     long solution = findSolution(m, n);     System.out.println("Minimum number is: " + solution);     System.out.println("Total number of digits: " + numberOfDigits(solution)); } 

Notable differences:

  • Your program isn't object-oriented anyway, so there's no point in instantiating a and calling input() as an instance method. (Furthermore, it's weird that input(), which is an instance method, stores its results in static variables instead of instance variables.)
  • There is a lot of repetition within input(). A general-purpose integer-prompting routine, used for both M and N, would be better.
  • m, n, and ndigit should not be static variables, as that makes them essentially global variables. Any function in the class can alter their values as a side-effect, making your code harder to analyze xe2x80x94 you have to read all of the code to understand any of it.
  • The solution needs to be a long, in case N is large. As @OleTange pointed out, if N is 99, then the solution must be at least 99999999999, which won't fit in an int. Note that brute-force enumeration is a very poor strategy for such large numbers.

Here's how I would write askInt():

static int askInt(String prompt, int min, int max) {     int result;     System.out.println(prompt);     while ((result = sc.nextInt()) < min || result > max) {         System.out.println("Invalid input, enter again: ");     }     return result; } 

Note that it returns a value to the caller, rather than setting some variable as a side-effect.


Assuming that we stick with your brute-force algorithm (and indeed there is a much faster way), these functions could be improved:

static int sumOfDigits(long num) {     int sum = 0;     while (num > 0) {         sum += num % 10;         num /= 10;     }     return sum; }  static int numberOfDigits(long num) {     return (int)Math.log10(num) + 1; } 

Arithmetic is preferable to converting numbers to strings and back. Keep in mind that the stringification process itself involves similar arithmetic operations, and therefore must be slower than arithmetic. Dealing with strings also incurs a cost for allocating memory for them.

I've chosen num as the parameter names to avoid confusion with the N in the problem statement.


As for the solution search itself, there are two bugs:

  • The problem calls for the solution to be strictly greater than M.
  • The problem does not state that the solution should be capped at 10000. (For example, given Mxc2xa0= 10000 and Nxc2xa0= 2, the solution should be 10001.)
public static long findSolution(int m, int n) {     for (long i = m + 1; ; i++) {         if (sumOfDigits(i) == n) {             return i;         }     } } 
 
 
   
   
10
 
vote

Su código es casi incomprensible debido a un formato deficiente. Para el beneficio de usted y otros revisores, aquí está su programa, sin otros cambios que no sean espacios en blanco y llaves:

  a6  

en particular,

  • Usa la sangría consistente.
  • Ponga un espacio antes y después de cada operador binario (excepto comas). a7 es difícil de leer.
  • Deja al menos una línea en blanco entre las funciones.
  • Siempre use tirantes para ambos a8 y a9 .
  • .
 

Your code is nearly incomprehensible due to poor formatting. For the benefit of you and other reviewers, here is your program, with no changes other than whitespace and braces:

import java.util.Scanner;  public class ISC {     static Scanner sc = new Scanner(System.in);     static int m, n;     static int ndigit;      void input() {         System.out.println("Enter the value of M: ");         m = sc.nextInt();         if (m >= 100 && m <= 10000) {         } else {             System.out.println("INVALID, Enter again: ");             while (!(m >= 100 && m <= 10000)) {                 m = sc.nextInt();             }         }          System.out.println("Enter the value of N: ");         n = sc.nextInt();         if (n >= 1 && n <= 100) {             //do nothing         } else {             System.out.println("INVALID INPUT, Enter again");             while (!(n >= 1 && n <= 100)) {                 n = sc.nextInt();             }          }     }      static int sumOfDigits(int n) {         int sum = 0;         String a = Integer.toString(n);         int digit;         for (int i = 0; i < a.length(); i++) {             digit = Integer.parseInt(Character.toString(a.charAt(i)));             sum += digit;         }         return sum;     }      static int getNo() {         ndigit = 0;         for (int i = m; i <= 10000; i++) {             if (sumOfDigits(i) == n) {                 ndigit = (Integer.toString(i)).length();                 return i;             }         }         return 0;     }      public static void main(String[] args) {         ISC a = new ISC();         a.input();         if (getNo()==0) {             System.out.println("NO NUMBER FOUND");         } else {             System.out.println("Minimum number is: " + getNo());             System.out.println("Total number of digits: " + ndigit);         }     } } 

In particular,

  • Use consistent indentation.
  • Put a space before and after every binary operator (except commas). (!(m>=100&&m<=10000)) is hard to read.
  • Leave at least one blank line between functions.
  • Always use braces for both if and else.
 
 
6
 
vote

Cuidado con que la solución pueda exceder la capacidad de un INT de 32 bits (en el peor de los casos, el caso, N = 99, la solución es 99999999999).

Su bucle de entrada está mejor escrito con un while (true) if ... break en lugar de if () ... else while () ... , menos legible y con la duplicación de algún código.

Está utilizando un enfoque de "fuerza bruta", al intentar todos los enteros en el rango permitido y la recompensación de la suma de los dígitos desde cero. Suponiendo que la solución es el entero S TIENDO 9988777665544333 Dígitos, se realizará sobre 9988777665544334 ADORTAS.

De todos modos, suponiendo que la suma de los dígitos de M es más pequeño que N , la solución se logra rápidamente configurando los dígitos a 9, comenzando desde la derecha. Hasta que se alcanza la suma N , si tengo razón. Esto toma O(N) Solo adiciones, un ahorro importante en la mayoría de los casos. ( 100 (1) > 109 (10) > 119 (11) ).

Ahora si la suma de los dígitos del if () ... else while () ...0 excede if () ... else while () ...1 , la solución requiere un análisis más profundo. Deberá modificar if () ... else while () ...2 de tal manera que su valor aumenta mientras que la suma disminuye sus dígitos. No lo he intentado, pero no me sorprendería de que una solución rápida siguiera siendo posible.


Actualización:

En el segundo caso, aumentará los dígitos distintos de la derecha de la derecha para que saturen y generen un transporte. ( if () ... else while () ...3 ) Cuando la suma cae por debajo de if () ... else while () ...4 , está de vuelta en el primer caso.

 

Beware that the solution can exceed the capacity of a 32 bits int (in the worst,case, N=99, the solution is 99999999999).

Your input loop is better written with a while (true) if ... break rather than if () ... else while () ..., less readable and with duplication of some code.

You are using a "brute force" approach, by trying all integers in the allowed range and recomputing the sum of digits from scratch. Assuming that the solution is the integer S having d digits, you will be performing about (S-M)d additions.

Anyway, assuming that the sum of the digits of M is smaller than N, the solution is quickly achieved by setting the digits to 9, starting from the right, until the sum N is reached, if I am right. This takes O(N) additions only, an important saving in most cases. (100 (1) > 109 (10) > 119 (11)).

Now if the sum of the digits of M exceeds N, the solution requires deeper analysis. You will need to modify M in such a way that its value increases while the sum its digits decreases. I have not tried that, but I wouldn't be surprised that a fast solution remained possible.


Update:

In the second case, you will increase the nonzero digits from the right so that they saturate and generate a carry. (14503 (13) > 14510 (11) > 14600 (11) > 15000 (6) > 60000 (6)) When the sum falls below M, you are back in the first case.

 
 
     
     
1
 
vote

Escribí este programa ... funciona realmente rápido ... debe encontrar el número en O (log n) si no me equivoco:

  if () ... else while () ...5  

El algoritmo es el siguiente:
Al principio supongo que M es mi candidato.
Luego, sumeo los dígitos de M. Suma de los dígitos de M mayor que N significa que tenemos un caso como M = 342 y N = 2. Así que tengo que aumentar M y también hacer que las decenas y cientos se encuentran como cero. En este ejemplo, cambiaré de 342 a 350, a continuación, verifique la suma y luego verifique la suma y luego revise la suma 400 a 1000, marque la suma ...

Ahora que la suma de los dígitos de M es menor o igual a n, tengo que aumentar M hasta que la suma se vuelva igual a N. así que primero cambiaré las unidades de lugar y luego cientos de lugares ... en el ejemplo, 1000 se cambiará a 10001 y esa es la respuesta ...

algunos más ejemplos:

  if () ... else while () ...6  

Espero que estos ejemplos ayuden ...

 

I wrote this program... it works really fast... It should find out the number in O(log n) if I am not mistaken :

import java.util.*; class ISC {     public static void main()     {         Scanner sc=new Scanner(System.in);         System.out.print("\fEnter the value of M: ");         long m,n,x;         m = sc.nextLong();         if (!(m >= 100 && m <= 10000))         {             System.out.print("INVALID, Enter again: ");             while (!(m >= 100 && m <= 10000)) {                 m = sc.nextLong();             }         }         System.out.print("Enter the value of N: ");         n = sc.nextLong();         if (!(n >= 1 && n <= 100))         {             System.out.print("INVALID INPUT, Enter again");             while (!(n >= 1 && n <= 100)) {                 n = sc.nextLong();             }         }//input         x=m;//we assume x is the answer         while(sum(x)>n)//the case if Sum of digits is greater than N         {             long i=1;             while(x%(Math.pow(10,i))==0)i++;             x+=Math.pow(10,i)-(x%(Math.pow(10,i)));         }         while(sum(x)<n)//Now Sum of digits less than or equal to N. We have to make it strictly equal         {             long k=n-sum(x),i=0;             while(((long)(x%Math.pow(10,i+1)))/((long)(Math.pow(10,i)))==9)i++;             long l=((long)(((x%Math.pow(10,i+1))/(Math.pow(10,i)))))*((long)Math.pow(10,i));             x+=Math.min(k,9-l)*Math.pow(10,i);         }         System.out.println("Number is : "+x);     }     public static long sum(long a)//to calculate sum of digits     {         long b=0;         while(a!=0)         {             b+=a%10;             a/=10;         }         return b;     } } 

The algorithm is as follows :
At first I assume that M is my candidate.
Then I sum the digits of M. Sum of digits of M greater than N means that we have a case like M=342 and N=2. So I have to increase M and also make the tens and hundreds places as zero. In this example, I will change 342 to 350 then check the sum then 350 to 400 then check the sum then 400 to 1000 then check the sum...

Now that Sum of digits of M is less than or equal to N, I have to increase M until the sum becomes equal to N. So first I will change the units place then hundreds place then...In the example, 1000 will be changed to 10001 and that is the answer...

Some more examples :

N=999999999,M=500  X=500 X=509 X=599 X=999 X=9999 X=99999 X=999999 X=9999999 X=99999999 X=999999999 X=9999999999 X=99999999999 

Hope these examples help...

 
 
         
         
0
 
vote

Esto debería encontrar el número en O (log (i) * log (i)). Esto es más rápido que O (i) que la OP utiliza y, por lo tanto, mejora el tiempo de ejecución (como se le solicita "Me encantaría saber cómo aumentar su eficiencia").

Se usa mucho tiempo en lugar de INT se convierte en cadena.

Solo se cambian 2 métodos y alrededor de 10 líneas de código. El resto del código sigue siendo el mismo y, por lo tanto, no se incluye aquí.

  if () ... else while () ...7  
 

This should find the number in O(log(i)*log(i)). This is faster than O(i) which the OP uses and thus improves run time (as asked for "I would love to know how to increase it's efficiency").

It uses long instead of int converted to string.

Only 2 methods and around 10 lines of code are changed. The rest of the code remains the same and it therefore not included here.

static int sumOfDigits(long num) {     int sum;     // compute the sum as modulo 10 for each digit in num     // T = O(log(num))     for (sum = 0; num != 0; sum += num%10, num = num/10) { }     return sum; }  static int getNo() {     long s = 9;     while(sumOfDigits(s) <= n && s < m) {       // O(log(n)) rounds each taking O(log(s)) => T = O(log(m)*log(m))       s = s*10+9;     }     // s      = 99999... sumdigits(s) >= n     // factor = 10000... same length as s     // s is bigger than the wanted number      // and has a bigger sum than the wanted number has.     // So now we just have to walk down towards the number.     // We do that one decimal position at a time     long factor = (s+1) / 10;      while(factor != 0) {       while(s - factor >= m && sumOfDigits(s - factor) >= n) {         // we can subtract 1 from this decimal position         // Max 10 rounds = O(1)*O(log(s))         s -= factor;       }       // next decimal position       // O(log(factor)) rounds => total: T = O(log(s)*log(factor))       factor /= 10;     }      int i = s;     // Below same as original code.     if (sumOfDigits(i) == n) {       ndigit = (Integer.toString(i)).length();       return i;     }     return 0; } 
 
 
         
         

Relacionados problema

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...

1  Compruebe si dos cadenas son permutación entre sí  ( Check if two strings are permutation of each other ) 
private String sort(String word) { char[] content = word.toCharArray(); Arrays.sort(content); return new String(content); } private boolea...

56  Proyecto Euler Problema 1 en Python - Múltiples de 3 y 5  ( Project euler problem 1 in python multiples of 3 and 5 ) 
Me gustaría sugerencias para optimizar esta solución de fuerza bruta a problema 1 . El algoritmo actualmente comprueba cada entero entre 3 y 1000. Me gustarí...

5  Proyecto EULER NO. 17: contando letras para escribir los números de 1 a 1000  ( Project euler no 17 counting letters to write the numbers from 1 to 1000 ) 
Soy muy nuevo en la programación y, cierto, estoy avergonzado de compartir mi código para la crítica. Este código funciona y produce la respuesta correcta a l...

8  Simple GCD Utility en Java  ( Simple gcd utility in java ) 
i anteriormente discutido El rendimiento se refiere a diferentes algoritmos GCD. Escribí una simple clase de Java que implementa el algoritmo binario GCD. E...

35  Demasiados bucles en la aplicación de dibujo  ( Too many loops in drawing app ) 
Tengo un método que tiene muchos bucles: #ifndef __RUNES_STRUCTURES_H #define __RUNES_STRUCTURES_H /* Runes structures. */ struct Game { char board[2...

5  Orden de número más grande en cadena  ( Largest number order in string ) 
Dada una cadena, suponiendo que la cadena sea solo números, reorganice la cadena a la que sea el mayor número posible. a continuación es mi solución al pr...

1  Retire todos los nodos que no se encuentren en ningún camino con suma> = k  ( Remove all nodes which dont lie in any path with sum k ) 
Dado un árbol binario, una ruta completa se define como un camino desde la raíz a una hoja. La suma de todos los nodos en ese camino se define como la suma d...

25  Algoritmo para transformar una palabra a otra a través de palabras válidas  ( Algorithm to transform one word to another through valid words ) 
He estado practicando retroceso y quería saber cómo puedo mejorar mi código. Por ejemplo, no quiero usarlo global. Además, no estoy seguro de si mi código fun...

2  Dos formas de aleatorias aleatoriamente las tarjetas  ( Two ways to randomly shuffle cards ) 
Aquí hay dos implementaciones que escribí para aleatorizar las tarjetas. El primer método ( dt5 ) Selecciona una tarjeta aleatoria, luego lo quita al frent...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos