题解

题目难度：简单

知识点：数学问题，二分算法

分析：

针对本题，有两种方法，一种利用数学思想，较为直接粗暴的搜索；另一种方法可以利用二分法来解决

方法1:

针对本题，第一想法是通过暴力的方法利用数学思路解答，给出sum的值求原值x（如果存在则为x,否则x=-1）,那么sum = x+(1/10)x+(1/100)x+…。以例子sum= 564为例计算，x≈508，与真实结果509相差很少，可以通过从508开始往后展开n个元素的搜索，这样也可以在一定程度上减少搜索范围。因为sum的范围在[1, 10^18]，所以要适当扩大搜索范围，在这个数据范围中n取100。

import java.util.Scanner;

public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            long sum = sc.nextLong();
            // 1. 暴力数学搜索法
            System.out.println(mathSolve(sum));

        }

        private static long mathSolve(long sum) {
            // 统计位数
            int count = 0;
            long tmp = sum;
            while(tmp>0){
                count++;
                tmp/=10;
            }

            //统计除数
            double chu = 0;
            for(int i=0;i<count;i++){
                chu += 1 / Math.pow(10, i);  // 1+0.1+0.01+...
            }

            //获取第一个搜索数
            long begin = (long) (sum/chu);

            //开始搜索
            long res = search(sum,begin);
        return res;
        }

        private static long search(long sum, long begin) {
            for(long i = begin; i<begin+100;i++){

                long tmp = i;

                    long sum2 = 0;
                    while (tmp > 0) {
                        sum2 += tmp;
                        tmp /= 10;
                    }

                    if (sum2 - sum ==0) {
                        return i ;
                    }

            }
            return -1;
        }

}

方法2：

利用二分思想解决问题：设置左右两个指针left和right，sum值一定大于要求的真实值，所以这两个指针可以分别指向1和输入的sum，找到中间mid值，求mid值对应的总和’sum’进行比较。

import java.util.Scanner;

public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            long sum = sc.nextLong();
                // 2. 利用二分查找的方法
            System.out.println(BineraySearchSolve(sum));
        }

        private static long BineraySearchSolve(long sum) {

            long tmp = sum;
            long left = 0 ;
            long right = sum;

            while(left<=right){
                long mid = (left+right)/2;
                // 二分找到mid,求其sum值，与输入的sum值比较是否相等。
                long theSum = getSum(mid);
                if(theSum == sum){
                    return mid;
                }else if(theSum > sum){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
            return -1;
        }



        private static long getSum(long mid) {
            long res = 0;
            while(mid>0){
                res+=mid;
                mid/=10;
            }
            return res;
        }
}