leetcode Question: Excel Sheet Column Number

Excel Sheet Column Number

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

Analysis:

This problem is pretty straightforward. Simply apply maltiplication and power of 26 (the number of chars from A-Z) will work well.

For each string, e.g. BCD:

• char D represents number  D - A + 1 ===> 4
• char C represents number  (26 ** 1) * (C - A + 1) ===> 78
• char B represents number  (26 ** 2) * (B - A + 1) ===> 1352

Therefore, the string BCD represents number 1352 + 78 + 4 = 1434

 

Code (C++):

class Solution {

public:

int titleToNumber(string s) {

int res = 0;

for (int i=s.size()-1;i>=0;--i){

res += (s[i]-'A' + 1) * pow(26, s.size() - i -1);

}

return res;

}

};

Code (Python):

class Solution(object):

def titleToNumber(self, s):

"""

:type s: str

:rtype: int

"""

res = 0

for i in range(len(s)):

res += 26**(len(s)-i-1) * (ord(s[i])-ord('A') + 1)

return res

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: Rectangle Area

Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

Analysis:

There are two step for solving this problem:
1. Check if the two rectangles are overlap or not.
2. Compute the overlap area. The overall area is \(area_1 + area_2 - area_{overlap}\).

To check the overlap of two rectangles, consider the non-overlap conditions:
1. A is on the left of B.  (A's right edge is on the left of B's left edge)
2. A is on the right of B.  (A's left edge is on the right of B's right edge)
3. A is on top of B.  (A's bottom edge is on top of B's top edge)
4. A is on the bottom of B.  (A's top edge is on the bottom of B's bottom edge)
In this problem:
Conditions A>G, C<E, D<F, B>H are corresponding to the above 4 conditions to check if the two rectangles are overlap.

To compute the overlap area, according to the figure in the question, it is not hard to derive the area is: \((\min(D, H) - \max(B,F)) \times (\min(C,G)-\max(A,E))\).

Code(C++):

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int area = (C-A)*(D-B) + (G-E)*(H-F);
        if (A>G || C < E || D < F || B > H){
            return area;
        } else{
            return area - (min(D, H)- max(B, F))*(min(C,G)- max(A,E));
        }
    }
};

Code(Python):

class Solution(object):
    def computeArea(self, A, B, C, D, E, F, G, H):
        """
        :type A: int
        :type B: int
        :type C: int
        :type D: int
        :type E: int
        :type F: int
        :type G: int
        :type H: int
        :rtype: int
        """
        area = (C-A)*(D-B) + (G-E)*(H-F)
        if A > G or C < E or D < F or B > H: 
            return area
        else:
            return area - (min(D, H)- max(B, F))*(min(C,G)- max(A,E))

leetcode Question: Factorial Trailing Zeroes

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Analysis:

Zeros can only generated on prime factors of 5s and 2s.
Lets' say 5s = {5*1, 5*2 ... 5*n}, 2s = {2*1, 2*2 ... 2*n}

So in this problem we need to count how many 5s and 2s.
Note that in n!, the 2s are always more than 5s, so we simplify the problem into counting the 5s.
There are several cases on 5s.  They are 5, 5^2, 5^3 ...
First let's see how to count 5s,  all we need is to compute floor (n/5) .
Then let's deal with 5^n.
E.g., n = 28,  it has 5s =  [5, 10, 15, 20, 25]
When we count 5s using floor(n/5), we have the length 5, but 25 = 5*5, there should be another 5 and the length is 6.  To count this, we can continue counting 5s using n divide by 5, 5^2, 5^3 ... In this way, all the 5s can be found.

Code(C++):

class Solution {
public:
    int trailingZeroes(int n) {
        long p = 5;
        int res = 0;
        while (p <= n){
            res += n/p;
            p = p*5;
        }
        return res;
    }
};

Code(Python):

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        p = 5
        res = 0
        while p <= n :
            res += n/p
            p = p *5
        return res
            

leetcode Question: Count Primes

Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

Analysis:

This is a classic algorithm question.  Here I'd like to introduce one of the famous algorithm called "Sieve of Eratosthenes." The general idea is to use a "sieve", to filter the numbers form 2 to n, each time, we get the next prime number in the array, and remove the multiples of this prime number. Iterating this process until the square of next prime number is greater than the last number n.  The numbers now left in the array are all primes.

In this problem, just be careful that the last number is not included.

According to the literature, the time complexity of this algorithm is nloglogn. Details of the analysis can be found in the wikipedia page here.

Code(C++):

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> num(n,true);
        int i = 2;
        while (i * i < n){
            for (int j = 2; j*i < n; j++){
                num[j*i] = false;
            }
            
            i++;
            
            while (num[i] == false && i*i < n){
                i++;
            }
        }
        int res=0;
        for (int i=2;i<n;i++){
            if (num[i] == true){
                res ++;
            }
        }
        return res;
    }
};

Code(Python):

class Solution:
    # @param {integer} n
    # @return {integer}
    def countPrimes(self, n):
        num=[1 for x in range(n)] 
        i = 2
        while i * i < n:
            j = 2
            while j*i < n:
                num[j*i] = 0
                j += 1
            i += 1
            while num[i] == 0 and i * i < n:
                i += 1
                
        return sum(num[2::])

leetcode Question: Excel Sheet Column Title

Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

Analysis:

This problem is not difficult but needs more attention on the format.
General cases are straightforward:
27 -> AA                 27/26 = 1,  27%26 = 1,     1->A, 1->A   thus AA
3  ->  C                    3/26 = 0,    3%26 = C        0->   , 3->C   thus C
53 -> BA                 53/26 = 2,   53%26 = 1      2->B, 1->A   thus BA

Some special cases we need to handle:
26 -> Z                    26/26 = 0,  26%26 = 0
52 -> AZ                 26/26 = 2,   26%26 = 0

When n%26 == 0, the last digit must be filled with a 'Z', therefore n in the next step must subtract this 'Z' (which is 26) and continue.

Code(C++):

class Solution {
public:
    string convertToTitle(int n) {
        string res = "";
        while (n>0){
            if (n%26==0){
                res = 'Z' + res;
                n = n/26 -1;
            }else{
                res = char(n%26 -1 + 'A') + res;
                n = n/26;
            }
        }
        return res;
    }
};

Code(Python):

class Solution:
    # @param {integer} n
    # @return {string}
    def convertToTitle(self, n):
        res = ''
        while n > 0:
            if n%26 == 0:
                res = 'Z' + res
                n = n/26 -1
            else:
                res = chr(ord('A') + n%26 - 1) + res
                n = n/26
        return res;