233. Number of Digit One

233. Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example:

Input: 13
Output: 6 
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

-----------------------
以百位上1的个数举例，3种情况：
55023 -> 55 * 100
55123 -> 55 * 100 + 23  + 1
55523 -> (55 + 1) * 100

class Solution {
    public int countDigitOne(int n) {
        long rt = 0;
        for (long i = 1; i <= n; i *= 10) {
            long first = n / i, second = n % i;
            long mid = first % 10;
            if (mid == 0) {
                rt += first / 10 * i;
            }else if (mid == 1) {
                rt += first / 10 * i + second + 1;
            }else {
                rt += (first / 10 + 1) * i;
            }
        }
        
        return (int)rt;
    }
}

479. Largest Palindrome Product

479. Largest Palindrome Product

Find the largest palindrome made from the product of two n-digit numbers.

Since the result could be very large, you should return the largest palindrome mod 1337.

Example:

Input: 2

Output: 987

Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Note:

The range of n is [1,8].

-----------------------
又恶心！
Solution#1, 找出上下边界，做遍历。超时
Solution#2 在上下边界内遍历所有的palindrome，找出符合的

class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) return 9;
        
        long upper = (long)Math.pow(10, n) - 1;
        long lower = (long)Math.pow(10, n - 1);
        long max = (long)upper * (long)upper;        
        long firstHalf = max / (long)Math.pow(10, n);
        
        boolean found = false;
        long pal = 0;
        while (!found) {
            pal = createPal(firstHalf);
            for (long i = upper; i >= lower; i--) {
                if (pal > i * i) break;
                if (pal % i == 0) {
                    found = true;
                    break;        
                }
            }
            firstHalf--;
        }
        
        return (int)(pal % 1337);
    }
    
    private long createPal(long firstHalf) {
        String s = firstHalf + new StringBuilder().append(firstHalf).reverse().toString();
        return Long.parseLong(s);
    }
}