java - 计算从 1 到 n 的个数的替代解决方案

Question

我有一个问题:

Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n (inclusive), For example,f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?

为了找到这个答案，我编写了如下程序:

/**
 * @author Rakesh KR
 *
 */
public class CountOne {

    public static int countOne(int n){
        int          count;
        StringBuffer strBff = new StringBuffer();
        for(int i=0;i<=n;i++){
            strBff = strBff.append(i);
        }
        count  = strBff.length() - strBff.toString().replace("1", "").length();
        strBff = null;
        return count;
    }

    public static void main(String[] args) {
        int count = 0;
        for(int i=1;i>0;i++){
            if(countOne(i)==i){
                System.out.println("Got it At :: "+ i);
                count++;
            }
            if(count==2)
                break;
        }
    }
}

程序运行良好。等了大约 1 小时后，我得到的答案是 199981

我正在为这个问题寻找替代的 IDEA(不需要代码)。我们如何才能在更短的时间内解决这个问题？

Answer 1

算术运算比转换为字符串和比较字符更高效。此代码在不到 10 毫秒的时间内找到了解决方案:

public class CountOne {

    public static int countOne(int n) {
        int count = 0;
        int mod;
        while (n > 0) {
            mod = n % 10;
            n /= 10;
            if (mod == 1) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int sum = 1;
        for (int i = 2;; i++) {
            sum += countOne(i);
            if (sum == i) {
                System.out.println(i);
                break;
            }
        }
    }
}