牛客網 2018校招真題 愛奇藝 最後一位

Description

牛客網 2018校招真題 最後一位

Solving Ideas

二分查找

Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long sum = Long.parseLong(br.readLine());
        System.out.println(binarySearch(0, sum, sum));
    }

    private static long binarySearch(long left, long right, long target) {
        while (left <= right) {
            long mid = (left + right) / 2;
            long sum = getSum(mid);
            if (sum == target) return mid;
            if (sum < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    private static long getSum(long num) {
        long ans = 0;
        while (num != 0) {
            ans += num;
            num /= 10;
        }
        return ans;
    }
}