【两次过】【二分搜索】【2018爱奇艺】最后一位

题目描述

牛牛选择了一个正整数X,然后把它写在黑板上。然后每一天他会擦掉当前数字的最后一位,直到他擦掉所有数位。 在整个过程中,牛牛会把所有在黑板上出现过的数字记录下来,然后求出他们的总和sum. 例如X = 509, 在黑板上出现过的数字依次是509, 50, 5, 他们的和就是564. 牛牛现在给出一个sum,牛牛想让你求出一个正整数X经过上述过程的结果是sum.

输入描述:

输入包括正整数sum(1 ≤ sum ≤ 10^18)

输出描述:

输出一个正整数,即满足条件的X,如果没有这样的X,输出-1。

示例1

输入

564

输出

509

---

解题思路：

暴力肯定不行，可采用二分搜索，时间复杂度为O(logn)，由于满足条件的数一定小于输入的数，所以可以以[0, num]为边界进行二分搜索，搜索条件需要变为当前数各个数位相加的和是否等于num，若小于则向右搜，若大于则向左搜

另外注意输入条件是10^18次，所以全程需要用long

import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); long num = sc.nextLong(); long res = binarySearch(num); System.out.println(res); } private static long binarySearch(long num){ long l=0, r=num; while(l <= r){ long mid = l + ((r-l)>>>1); long midRes = getNiuSum(mid); if(midRes == num) return mid; else if(midRes < num) l = mid+1; else r = mid-1; } return -1; } private static long getNiuSum(long num) { long ans = 0; while (num != 0) { ans += num; num /= 10; } return ans; } }