We want to represent positive integer n as a sum of addends, where each addends is an integer number containing only 1s. For example, we can represent 121 as 121=111+11+–1. Help us to find the least number of digits 1 in such sum. Input: The first line of the input contains integer n (1 ≤ n < 1015). Output: Print expected minimal number of digits 1. (ex. input:121, output:6)
I wrote the following program for this problem and it works, but is too slow on big numbers. How could i make it faster?
Problem:
We want to represent positive integer n as a sum of addends, where each addends is an integer number containing only 1s. For example, we can represent 121 as 121=111+11+–1. Help us to find the least number of digits 1 in such sum.
import java.util.Scanner;
public class Main {
staticlong[] en=newlong[]{1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,
11111111111L,111111111111L,1111111111111L,11111111111111L,111111111111111L,1111111111111111L};
public static void main(String[] args){
Scanner scanner =new Scanner(System.in);
System.out.println(rekisto(scanner.nextLong()));
}
static long rekisto(long s){
if(s==0){
return 0;
}
int dolzina =String.valueOf(s).length();
if(Math.abs((en[dolzina])-s)<s){
long n2 = rekisto(Math.abs((en[dolzina])-s))+(dolzina+1);
return (Math.min((rekisto(Math.abs(s-en[dolzina-1]))+ dolzina),n2));
}
return rekisto(Math.abs(s-en[dolzina-1]))+ dolzina;
}
}
Step by step
Solved in 3 steps with 2 images
