Number Of Digit One


  • 0
    A

    Click here to see the full article post


  • 0
    V

    import java.util.Scanner;
    public class Leetcode1 {
    public static void main(String args[])
    {
    Scanner s=new Scanner(System.in);
    int n=s.nextInt();
    String k=String.valueOf(1);
    for(int i=0;i<n;i++)
    {
    String s1=String.valueOf(i);
    if(s1.startsWith(k))
    {
    System.out.print(s1+",");
    }
    }
    }
    }


  • 0
    J

    It seems very easy, the time complexity should be O(1)


  • 0
    This post is deleted!

  • 0
    O

    There is also a dynamic programming solution, with time complexity O(logn).


  • 0
    E

    java:

    class Solution {
        public int countDigitOne(int n) {
            if (n <= 0) {
                return 0;
            }
            int m = n;
            int sum = 0;
            int e = 1;
            while (n > 0) {
                int r = n % 10;
                n /= 10;
                if (r == 0) {
                    sum += n * e;
                } else if (r > 1) {
                    sum += (n + 1) * e;
                } else { // r == 1
                    sum += m - n * 9 * e - e + 1;
                }
                e *= 10;
            }
            return sum;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.