leetcode Question: Number of Digit One

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.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Analysis:


It takes me a couple of hours to figure out a easy way to solve this problem. Basically once you get the idea, it would take you less than 10 mins to implement the code, and before that, all you need is a piece of paper and a pencil.

At the first glance, what usually comes up to our mind is different O(n) solutions, however this won't pass the OJ. We must think from another way: from digit to digit.

Lets' first take a look at an easier problem:  how many digits 1 appearing in all non-negative integers less than or equal to n-digits length integer?  In other words, how many "1"s in  0-9 (1-digit), how many "1"s in 0-99, how many "1"s in 0-999...

From 0-9, it is not hard to find out there is only 1 "1" (here "1" indicates the digit 1 in integer), it occurred in integer 1.

From 0-99, counting number of "1" is a procedure as follows:
1. Consider two blank slots which we fill number in them: [ ][ ]

2. Both digits are ranging from 0-9, e.g., [0][2] = 2, [1][3] = 13, denote as [0-9][0-9].

3. There are two cases:  [0,2-9][ 0-9] and [1][0-9]

4. Case 1: [0,2-9][0-9]. There is no "1" in the highest digit. "1" only appears in the rest of digits, here is one digit [0-9]. For each number in [0, 2-9], we have the number of "1" from its lower digit(s) [0-9], which is 1. Now we have 10 different possible highest digits, i.e., 0,2,3,4,5,6,7,8,9, for every one of them, the lower digit(s) can generate 1 "1", in total there are 10 *1 = 10  "1"s in this case.

5. Case 2: [1][0-9]. "1" is in highest digit, which means every possible number in  its lower digits (now is [0-9]) contains one "1".  So there are 1*10  = 10 "1"s in this case.

6. Sum Case 1 and Case 2 up, we have 20 "1"s from 0-99.



Next, let's see how to count "1" from 0-999, similar to previous steps:
1. We have three blank slots [ ][ ][ ].

2. There are two cases: [1][0-9][0-9] , and [0, 2-9][0-9][0-9].

3. Case 1:  [0, 2-9][0-9][0-9]. # of "1" is in this case equal to:  # of "1" in [0-9][0-9]  times 10 =  20*10 = 200.

4. Case 2: [1][0-9][0-9], we have more "1"s since all numbers in form [1][0][0] to [1][9][9] have an additional "1" in their highest digit. Thus, we need to add 100, which is # of integers from 100-199.

5. The total number of "1" from 0-999 is 300.




Getting clear the above procedures, now we are targeting arbitrary number. Let's take an example,
say n = 5746. Denote function C(m,n) as the number of digit "1" appearing from integer m to integer n. We can write down the procedure:

$$
\small\begin{array}{ccccccccccccc}
C(0,5746) & = & C(0,999) & + & C(1000,5746)\\
& = & C(0,999) & + & 4*C(0,999) & + & 1000 & + & C(5000,5746)\\
& = & 5*C(0,999) & + & 1000 & + & C(0,746)\\
& = & 5*C(0,999) & + & 1000 & + & C(0,99) & + & C(100,746)\\
& = & 5*C(0,999) & + & 1000 & + & 7*C(0,99) & + & C(700,746)\\
& = & 5*C(0,999) & + & 1000 & + & 7*C(0,99) & + & 100 & + & C(0,46)\\
& = & 5*C(0,999) & + & 1000 & + & 7*C(0,99) & + & 100 & + & 5*C(0,9) & + & 10\\
& = & 5*300 & + & 1000 & + & 7*20 & + & 100 & + & 5 & + & 10\\
& = & 2755

\end{array}
$$


Although it looks complicated, from the programming view, it is much easier. There are two cases you have to pay attention to, (1). When current digit is 0, there no additional "1" to be added. (1000, and 100 and 10 in the above expression.) (2) When current digit is 1, the additional "1" is not 10,100,or 1000 any more, but the actual number in its lower digits.

In my implementation, I choose to use lower to higher order rather than the higher to lower order when scanning each digit. To get i-th digit, we can use \((n\%10^{i})/(i/10)\). I use bool type to check the current digit to simplify my code.  "m" indicates the number of "1"s  in 0-9, 0-99, 0-999 and so on.


Code(C++):


class Solution {
public:
    int countDigitOne(int n) {
        int res = 0;
        int m = 0;
        for (long i=1;i<=n;i=i*10){
            int d = n%(i*10)/i;
            res += d*m + (d == 1)*(n%i + 1) + (d>1)*(i);
            m = m*10 +i;
        }
        return res;
    }
};


Code(Python):


class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        m = 0
        i = 1
        while i <= n:
            d = n%(i*10)/i;
            res += d*m + (d == 1)*(n%i + 1) + (d>1)*i
            m = m*10 +i
            i = i*10
        return res

leetcode Question: Implement Queue using Stacks

Implement Queue using Stacks

Implement the following operations of a queue using stacks.
  • push(x) -- Push element x to the back of queue.
  • pop() -- Removes the element from in front of queue.
  • peek() -- Get the front element.
  • empty() -- Return whether the queue is empty.
Notes:

  • You must use only standard operations of a stack -- which means only push to toppeek/pop from topsize, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Analysis:


This kind of problem usually requires more than one data structure to implement the other data structure. In this problem, two stacks are enough to implement a queue.

The idea is keep push element into stack 1, then "pop" is called, put all the elements from stack 1 to stack 2. Then pop the top element in stack 2.  If "pop" is called again, not stack 2 is not empty, just pop the top element is enough. If stack 2 is empty, put all the elements in stack 1 to stack 2.  In short, stack 1 is used for "push", stack 2 is used for "pop" and "peek". We do the "move element from stack1 to stack 2" only when stack 2 is empty and "pop" or "peek" is called.


e.g., We call push(1), push(2), push(3), push(4), and push(5), stack 1 is filled all the five elements, then do pop(), since stack 2 is empty, move elements from stack 1 to stack 2, then pop the top element (now is 1) in stack2:
 Then we call push(6), push(7), push(8), push(9), and pop(), pop(), pop(), stack 1 is used for pushing, and stack 2 is used for popping :
Again, we call pop() (now 5 is popped out and no element in stack 2), and a peek() operation is called, stack 2 is empty, so push elements from stack 1 to stack 2, and return the top element as the peek:




Code(C++):

class Queue {

stack<int> st1;
stack<int> st2;

public:
    // Push element x to the back of queue.
    void push(int x) {
        st1.push(x);
    }

    // Removes the element from in front of queue.
    void pop(void) {
        if (!st2.empty()){
            st2.pop();
        }else{
            while (!st1.empty()){
                st2.push(st1.top());
                st1.pop();
            }
            st2.pop();
        }
    }

    // Get the front element.
    int peek(void) {
        if (!st2.empty()){
            return st2.top();
        }else{
            while (!st1.empty()){
                st2.push(st1.top());
                st1.pop();
            }
            return st2.top();
        }
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return (st1.empty() && st2.empty());
    }
};

Code(Python):

class Queue(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.st1 = []
        self.st2 = []
        

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.st1.append(x)
        

    def pop(self):
        """
        :rtype: nothing
        """
        if len(self.st2) == 0:
            while len(self.st1) != 0:
                self.st2.append(self.st1.pop())
        self.st2.pop()
                

    def peek(self):
        """
        :rtype: int
        """    
        if len(self.st2) == 0:
            while len(self.st1) != 0:
                self.st2.append(self.st1.pop())
        return self.st2[-1]
        

    def empty(self):
        """
        :rtype: bool
        """
        return not self.st1 and not self.st2


leetcode Question: Power of Two

Power of Two

Given an integer, write a function to determine if it is a power of two.

Analysis:

An straightforward way is to keep doing "divide by 2" for the number and check if current number "mod 2" is zero. However this is pretty slow (it still can pass the OJ).

More efficient way is to use bit manipulation.

If one number is a power of 2, then its binary must starts with 1 and all the lower bits are 0. e.g.,
2 10
4 100
8 1000
16 10000
...

Also, we have to find a "mask" to check this format, what "mask" should we use?
Let's see some examples:
1 01
3 011
7 0111
15 01111
...

Well, it is not hard to see that,  if one number "n" is a power of 2, then "n-1" must have all 1s in its binary format. Therefore, "n & n-1" must be 0.  


Code(C++):

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return ( (n>0) && (n & (n-1))==0 ) || (n==1);
    }
};

Code(Python):

aclass Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n>0 and  n & (n-1)==0 or n==1