Leetcode: 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.

Hint:

1. Beware of overflow.

Understand the problem:

Leetcode: Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

Understand the problem:
The idea would be very close to the previous problem. So we find all the strobogrammatic numbers between the length of low and high. Note that when the n == low or n == high, we need to compare and make sure the strobogrammatic number we find is within the range.

Code (Java):

public class Solution {
    private int count = 0;
    private Map<Character, Character> map = new HashMap<>();
    
    public int strobogrammaticInRange(String low, String high) {
        if (low == null || low.length() == 0 || high == null || high.length() == 0) {
            return 0;
        }
        
        fillMap();
        
        for (int n = low.length(); n <= high.length(); n++) {
            char[] arr = new char[n];
            getStrobogrammaticNumbers(arr, 0, n - 1, low, high);
        }
        
        return count;
    }
    
    private void getStrobogrammaticNumbers(char[] arr, int start, int end, String low, String high) {
        if (start > end) {
            String s = new String(arr);
            if ((s.length() == 1 || s.charAt(0) != '0') && compare(low, s) && compare(s, high)) {
                count++;
            }
            return;
        }
            
        for (char c : map.keySet()) {
            arr[start] = c;
            arr[end] = map.get(c);
                
            if ((start < end) || (start == end && map.get(c) == c)) {
                getStrobogrammaticNumbers(arr, start + 1, end - 1, low, high);
            }
        }
    }
    
    // Return true if s1 <= s2
    private boolean compare(String s1, String s2) {
        if (s1.length() == s2.length()) {
            if (s1.compareTo(s2) <= 0) {
                return true;
            } else {
                return false;
            }
        }
        
        return true;
    }
    
    private void fillMap() {
        map.put('0', '0');
        map.put('1', '1');
        map.put('8', '8');
        map.put('6', '9');
        map.put('9', '6');
    }
}

Leetcode: Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Hint:

1. Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.
2. Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.
3. There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

Code (Java):

public class Solution {
    public String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
        
        Map<Integer, String> map = new HashMap<>();
        // Step 1: fill the hash map
        fillHashMap(map);
    
        StringBuffer sb = new StringBuffer();
        int groupId = 1;
        
        // Step 2: group the num with 3 digits
        while (num > 0) {
            int group = num % 1000;
            
            if (groupId > 1 && group > 0) {
                String groupStr = getGroupName(groupId);
                sb.insert(0, groupStr);
            }
            
            String str = numberToWordsHelper(group, map);
            sb.insert(0, str);
            
            groupId++;
            num /= 1000;
        }
        
        String result = sb.toString();
        if (result.charAt(result.length() - 1) == ' ') {
            return result.substring(0, result.length() - 1);
        } else {
            return result;
        }
    }
    
    private void fillHashMap(Map<Integer, String> map) {
        map.put(1, "One ");
        map.put(2, "Two ");
        map.put(3, "Three ");
        map.put(4, "Four ");
        map.put(5, "Five ");
        map.put(6, "Six ");
        map.put(7, "Seven ");
        map.put(8, "Eight ");
        map.put(9, "Nine ");
        map.put(10, "Ten ");
        map.put(11, "Eleven ");
        map.put(12, "Twelve ");
        map.put(13, "Thirteen ");
        map.put(14, "Fourteen ");
        map.put(15, "Fifteen ");
        map.put(16, "Sixteen ");
        map.put(17, "Seventeen ");
        map.put(18, "Eighteen ");
        map.put(19, "Nineteen ");
        map.put(20, "Twenty ");
        map.put(30, "Thirty ");
        map.put(40, "Forty ");
        map.put(50, "Fifty ");
        map.put(60, "Sixty ");
        map.put(70, "Seventy ");
        map.put(80, "Eighty ");
        map.put(90, "Ninety ");
        map.put(100, "One Hundred ");
        map.put(1000, "One Thousand ");
    }
    
    private String getGroupName(int groupId) {
        String result = null;
        switch(groupId) {
            case 2: result = "Thousand ";
            break;
            
            case 3: result = "Million ";
            break;
            
            case 4: result = "Billion ";
            break;
        }
        
        return result;
    }
    
    private String numberToWordsHelper(int num, Map<Integer, String> map) {
        int pos = 0;
        StringBuffer sb = new StringBuffer();
        
        if (num <= 0) {
            return "";
        }
        
        int tmp = num;
        while (tmp > 0) {
            pos++;
            tmp /= 10;
        }
        
        while (num > 0) {
            if (num <= 20) {
                sb.append(map.get(num));
                break;
            }
            
            int digit = num / (int) Math.pow(10, pos - 1);
            int curr = digit * (int) Math.pow(10, pos - 1);
            
            if (pos == 3) {
                sb.append(map.get(digit));
                sb.append("Hundred ");
            } else {
                sb.append(map.get(curr));
            }
            
            num = num % (int) Math.pow(10, pos - 1);
            pos--;
        }
        
        return sb.toString();
    }
}

A neat solution without using HashMap. 

public class Solution {
    public String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
        
        String[] group = {"", "Thousand ", "Million ", "Billion "};
        String[] dict1 = {"", "One ", "Two ", "Three ", "Four ", 
                          "Five ", "Six ", "Seven ", "Eight ", "Nine ",
                          "Ten ", "Eleven ", "Twelve ", "Thirteen ",
                          "Fourteen ", "Fifteen ", "Sixteen ", "Seventeen ",
                          "Eighteen ", "Nineteen "};
        String[] dict2 = {"", "", "Twenty ", "Thirty ", "Forty ", "Fifty ",
                          "Sixty ", "Seventy ", "Eighty ", "Ninety "};
        
        StringBuffer sb = new StringBuffer();
        
        for (int i = 0; i < 4; i++) {
            int curr = num % 1000;
            if (curr > 0) {
                if (i > 0) {
                    sb.insert(0, group[i]);
                }
                sb.insert(0, numToWordsHelper(curr, dict1, dict2));
            }
            num /= 1000;
        }
        
        String result = sb.toString();
        if (result.charAt(result.length() - 1) == ' ') {
            return result.substring(0, result.length() - 1);
        } else {
            return result;
        }
    }
    
    private String numToWordsHelper(int num, String[] dict1, String[] dict2) {
        StringBuffer result = new StringBuffer();
        
        int a = num / 100;
        int b = num % 100;
        int c = num % 10;
        
        if (a > 0) {
            result.append(dict1[a] + "Hundred ");
        }
        
        if (b > 0 && b < 20) {
            result.append(dict1[b]);
            c = 0; 
        } else if (b >= 20) {
            b /= 10;
            result.append(dict2[b]);
        }
        
        if (c > 0) {
            result.append(dict1[c]);
        }
        
        return result.toString();
    }
}

Summary:
There are some corner cases need to be very careful:
input = 1000, output = One Thousand, not One Thousand Zero
input = 1,000,000, output is One million , not One Million Thousand.  

Leetcode: Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Hint:

1. The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
4. Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

Understand the problem:
We can maintain three lists of ugly numbers:
1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2, etc..
1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3, etc..
1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5, etc...

Then we can see that in each list, the ugly number is the ugly number itself times 2, 3 or 5. 
Then we can maintain three pointers of i, j, and k, and the next ugly number must be minimum number of Li, Lj and Lk. At last, we move forward the pointer. 

Code (Java):

public class Solution {
    public int nthUglyNumber(int n) {
        if (n <= 0) {
            return 0;
        }
        
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        
        int i = 0;
        int j = 0;
        int k = 0;
        
        while (nums.size() < n) {
            int m2 = nums.get(i) * 2;
            int m3 = nums.get(j) * 3;
            int m5 = nums.get(k) * 5;
            
            int mn = Math.min(Math.min(m2, m3), m5);
            nums.add(mn);
            
            if (mn == m2) {
                i++;
            }
            
            if (mn == m3) {
                j++;
            }
            
            if (mn == m5) {
                k++;
            }
        }
        
        return nums.get(nums.size() - 1);
    }
}

Leetcode: Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Hint:

1. A naive implementation of the above process is trivial. Could you come up with other methods?
2. What are all the possible results?
3. How do they occur, periodically or randomly?
4. You may find this Wikipedia article useful

Brute-force solution:

public class Solution {
    public int addDigits(int num) {
        if (num < 10) {
            return num;
        }
        
        int result = num;
        
        while (result >= 10) {
            // Get each didgit of the number
            int digit = 0;
            while (result > 0) {
                digit += result % 10;
                result /= 10;
            }
            
            result = digit;
        }
        
        return result;
    }
}

O(1) time solution:
Let's enumerate numbers from 1 - 19, 
in out 
1   1
2   2
3   3
 ...
9   9
10  1
11  2
12  3
13  4
14  5
...
19  1
20  2
21  3

...
28  1
29  2
30  3
...

So the result = (n - 1) % 9 + 1

Code (Java):

public class Solution {
    public int addDigits(int num) {
        if (num <= 0) {
            return 0;
        }
        
        return (num - 1) % 9 + 1;
    }
}

Leetcode: Count Primes

Description:

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

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Hint:

1. Let's start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. The runtime complexity of isPrimefunction would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better?
2. As we know the number must not be divisible by any number > n / 2, we can immediately cut the total iterations half by dividing only up to n / 2. Could we still do better?
3. Let's write down all of 12's factors:

   2 × 6 = 12
   3 × 4 = 12
   4 × 3 = 12
   6 × 2 = 12
   

   As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n= p × q and since p ≤ q, we could derive that p ≤ √n.
   Our total runtime has now improved to O(n1.5), which is slightly better. Is there a faster approach?

   public int countPrimes(int n) {
      int count = 0;
      for (int i = 1; i < n; i++) {
         if (isPrime(i)) count++;
      }
      return count;
   }
   
   private boolean isPrime(int num) {
      if (num <= 1) return false;
      // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
      // to avoid repeatedly calling an expensive function sqrt().
      for (int i = 2; i * i <= num; i++) {
         if (num % i == 0) return false;
      }
      return true;
   }
   

4. The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n. But don't let that name scare you, I promise that the concept is surprisingly simple.
   
   Sieve of Eratosthenes: algorithm steps for primes below 121. "Sieve of Eratosthenes Animation" by SKopp is licensed under CC BY 2.0.
   We start off with a table of n numbers. Let's look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. What does this tell you? Should you mark off all multiples of 4 as well?
5. 4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, ... can be marked off. There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off?
6. In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, ... Now what should be the terminating loop condition?
7. It is easy to say that the terminating loop condition is p < n, which is certainly correct but not efficient. Do you still remember Hint #3?
8. Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off. When the loop terminates, all the numbers in the table that are non-marked are prime.
   The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n). For the more mathematically inclined readers, you can read more about its algorithm complexity on Wikipedia.

   public int countPrimes(int n) {
      boolean[] isPrime = new boolean[n];
      for (int i = 2; i < n; i++) {
         isPrime[i] = true;
      }
      // Loop's ending condition is i * i < n instead of i < sqrt(n)
      // to avoid repeatedly calling an expensive function sqrt().
      for (int i = 2; i * i < n; i++) {
         if (!isPrime[i]) continue;
         for (int j = i * i; j < n; j += i) {
            isPrime[j] = false;
         }
      }
      int count = 0;
      for (int i = 2; i < n; i++) {
         if (isPrime[i]) count++;
      }
      return count;
   }

Summary:
The optimization tricks for determining if a number is Prime:
1. Check all n's factors from 2 to n - 1
2. Check until n/2, because n must not be divisible by the number greater than n/2
3. Check until sqrt(n). Because if n is dividible by some number p, then n = p * q, since p <= q, so p is up to sqrt(n). 

So the time complexity is O(sqrt(n)) to determine if a number is prime. 


The optimization tricks for count the number of primes less than n
1. If the current number is p, we only need to start from p^2, because 2*p, 3*p, 4*p, ..., has already been marked off. So we start from p^2, and p^2 + p, p^2 + 2p, ...
2. we terminate the loop condition at sqrt(n), because all non-primes >= sqrt(n) must have already been marked off. 

Leetcode: Happy Number

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

Understand the problem:
The hint of the problem is if the input number is a happy number, it will end with 1. 
Else, it will loop endlessly in a cycle. Therefore, we could use a hash set to keep track of each number we have visited. If we saw a visited number, that means the loop has been formed and it will return a false. 

Code (Java):

public class Solution {
    public boolean isHappy(int n) {
        if (n <= 0) {
            return false;
        }
        
        Set<Integer> set = new HashSet<Integer>();
        
        while (true) {
            int square = getSumOfSquare(n);
            
            if (square == 1) {
                return true;
            } else if (set.contains(square)) {
                return false;
            }
            
            set.add(square);
            n = square;
        }
    }
    
    private int getSumOfSquare(int n) {
        int result = 0;
        
        while (n > 0) {
            int digit = n % 10;
            n = n / 10;
            result += digit * digit;
        }
        
        return result;
    }
}

An O(1) space solution:

int digitSquareSum(int n) {
    int sum = 0, tmp;
    while (n) {
        tmp = n % 10;
        sum += tmp * tmp;
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) {
    int slow, fast;
    slow = fast = n;
    do {
        slow = digitSquareSum(slow);
        fast = digitSquareSum(fast);
        fast = digitSquareSum(fast);
    } while(slow != fast);
    if (slow == 1) return 1;
    else return 0;
}

Questions: Why unhappy number must end with a loop?
There is a proof from wiki:
https://en.wikipedia.org/wiki/Happy_number

Numbers that are happy, follow a sequence that ends in 1. All non-happy numbers follow sequences that reach the cycle:

4, 16, 37, 58, 89, 145, 42, 20, 4, ...

To see this fact, first note that if n has m digits, then the sum of the squares of its digits is at most ${\displaystyle 9^{2}m}$, or ${\displaystyle 81m}$.

For ${\displaystyle m=4}$ and above,

${\displaystyle n\geq 10^{m-1}>81m}$

so any number over 1000 gets smaller under this process and in particular becomes a number with strictly fewer digits. Once we are under 1000, the number for which the sum of squares of digits is largest is 999, and the result is 3 times 81, that is, 243.

• In the range 100 to 243, the number 199 produces the largest next value, of 163.
• In the range 100 to 163, the number 159 produces the largest next value, of 107.
• In the range 100 to 107, the number 107 produces the largest next value, of 50.

Considering more precisely the intervals [244,999], [164,243], [108,163] and [100,107], we see that every number above 99 gets strictly smaller under this process. Thus, no matter what number we start with, we eventually drop below 100. An exhaustive search then shows that every number in the interval [1,99] either is happy or goes to the above cycle.

The above work produces the interesting result that no positive integer other than 1 is the sum of the squares of its own digits, since any such number would be a fixed point of the described process.

Leetcode: Factorial Trailing Zeroes

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

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Understand the problem:
The naive solution would be first calculate the n!, can then count how many number of zeros. Here the question requires the log time complexity. 

Let's take several examples then we may find some patterns. 
5 ! = 1 * 2 * 3 * 4 * 5 = 120,  -> 1 zero
6 ! = 1 * 2 * 3 * ... * 6 = 720, -> 1 zero
10 ! = 1 * 2 * ... * 5 * ... 10 = 362800  -> 2 zeros. 

Therefore, the number of trailing zeros are determined by the number of pair of (2 ,5) for the number. Since number of 2 are always greater than number of 5. We only need to count how many 5s in the number. 

Code (Java):

public class Solution {
    public int trailingZeroes(int n) {
        if (n <= 0) {
            return 0;
        }
        
        int count = 0;
        
        while (n > 1) {
            count += n / 5;
            n /= 5;
            
        }
        
        return count;
    }
}

Update on 10/14/15:

public class Solution {
    public int trailingZeroes(int n) {
        if (n < 5) {
            return 0;
        }
        
        int count = 0;
        for (long i = 5; n / i > 0; i *= 5) {
            count += n / i;
        }
        
        return count;
    }
}

Leetcode: Excel Sheet Column Number

Related to question Excel Sheet Column Title

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 

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Understand the problem:
This question is an reverse question of the previous one. Let's still an transforming 26-base number to a 10-base number. Before we solve this question, let's consider how to convert a string to a number. For e.g. "123" -> 123, we start from the most significant digit,
1 + result * 10 = 1
2 + rssult * 10 = 12
3 + result * 10 = 123

So the solution here is the same, except for replacing the 10 by 26. Also noted that we need to add number by 1 each time since this question is index-1 started. 

Code (Java):

public class Solution {
    public int titleToNumber(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        int result  = 0;
        
        for (int i = 0; i < s.length(); i++) {
            result = result * 26 + s.charAt(i) - 'A' + 1;
        }
        
        return result;
    }
}

Leetcode: 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 

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases.

Understand the problem:
A classic 10-based math to 26-based math. Remember for a 10-based integer, e.g. 123, how can we extract each digit?  The idea is from the least significant digit and use %10 and /10 respectively. e.g. 
123 % 10 = 3, 123 / 10 = 12
12 % 10 = 2, 12 / 10 = 1
1 % 10 = 1, 1 / 10 - 0.

Therefore, for this question, we only need to replace 10 to 26. Note that for this question, the map is from 1 to 26. Therefore, we need to minus 1 for each number before the computation.  

Code (Java):

public class Solution {
    public String convertToTitle(int n) {
        if (n <= 0) {
            return "";
        }
        
        StringBuffer sb = new StringBuffer();
        convertToTitleHelper(n, sb);
        
        sb.reverse();
        
        return sb.toString();
    }
    
    private void convertToTitleHelper(int n, StringBuffer sb) {
        if (n <= 0) {
            return;
        }
        n--;
        int val = n % 26;
        val = val < 0 ? val + 26 : val;
        char title = (char) (val + 'A');
        
        sb.append(title);
        
        convertToTitleHelper(n / 26, sb);
    }
}

Update on 10/14/15:

public class Solution {
    public String convertToTitle(int n) {
        if (n <= 0) {
            return "";
        }
        
        StringBuffer sb = new StringBuffer();
        
        while (n > 0) {
            n--;
            
            int val = n % 26;
            char title = (char) (val + 'A');
            sb.insert(0, title);
            
            n /= 26;
        }
        
        return sb.toString();
    }
}

Leetcode: Compare Version Numbers

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

Understand the problem:
The tricky part of the problem is to understand that 1.0 and 1 are the same version. 

Code (Java):

public class Solution {
    public int compareVersion(String version1, String version2) {
        if ((version1 == null || version1.length() == 0) && 
            (version2 == null || version2.length() == 0)) {
            return 0;
        }
        
        if (version1 == null || version1.length() == 0) {
            return -1;
        }
        
        if (version2 == null || version2.length() == 0) {
            return 1;
        }
        
        String delim = "[.]";
        String[] v1 = version1.split(delim);
        String[] v2 = version2.split(delim);
        
        int i;
        int j;
        for (i = 0, j = 0; i < v1.length || j < v2.length; i++, j++) {
            String s1 = "";
            String s2 = "";
            if (i < v1.length) {
                s1 = v1[i];
            }
            
            if (j < v2.length) {
                s2 = v2[j];
            }
            
            s1 = removeLeadingZeros(s1);
            s2 = removeLeadingZeros(s2);
            
            if (s1.isEmpty() && s2.isEmpty()) {
                continue;
            }
            
            if (s2 == null || s2.length() == 0) {
                return 1;
            }
            
            if (s1 == null || s1.length() == 0) {
                return -1;
            }
            
            if (s1.length() > s2.length()) {
                return 1;
            } else if (s1.length() < s2.length()) {
                return -1;
            } else {
                for (int k = 0; k < s1.length(); k++) {
                    if (Character.getNumericValue(s1.charAt(k)) > 
                        Character.getNumericValue(s2.charAt(k))) {
                        return 1;
                    } else if (Character.getNumericValue(s1.charAt(k)) < 
                        Character.getNumericValue(s2.charAt(k))) {
                        return -1;
                    }
                }
            }
        }
        
        return 0;
    }
    
    private String removeLeadingZeros(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '0') {
                break;
            } else {
                start++;
            }
        }
        
        return s.substring(start);
    }
}

A neater code:
If in each sub-version, we assume that the length is not greater than the upper bound of an integer number, we don't need to parse it character-by-character. 

Code (Java):

public int compareVersion(String version1, String version2) {
    String[] arr1 = version1.split("\\.");
    String[] arr2 = version2.split("\\.");
 
    int i=0;
    while(i<arr1.length || i<arr2.length){
        if(i<arr1.length && i<arr2.length){
            if(Integer.parseInt(arr1[i]) < Integer.parseInt(arr2[i])){
                return -1;
            }else if(Integer.parseInt(arr1[i]) > Integer.parseInt(arr2[i])){
                return 1;
            }
        } else if(i<arr1.length){
            if(Integer.parseInt(arr1[i]) != 0){
                return 1;
            }
        } else if(i<arr2.length){
           if(Integer.parseInt(arr2[i]) != 0){
                return -1;
            }
        }
 
        i++;
    }
 
    return 0;
}

Update on 10/14/15:
The very tricky part is the corner cases need to consider:
1. v1 = 1.0.0, v2 = 1, => so they should be the same version

Therefore, when we went through one of the arrays, we need to also iterate the rest of the array until it's to the end. 

Code (Java):

public class Solution {
    public int compareVersion(String version1, String version2) {
        String delim = "[.]";
        String[] v1 = version1.split(delim);
        String[] v2 = version2.split(delim);
        
        int i = 0; 
        int j = 0;
        
        while (i < v1.length && j < v2.length) {
            int seg1 = Integer.parseInt(v1[i]);
            int seg2 = Integer.parseInt(v2[j]);
            
            if (seg1 > seg2) {
                return 1;
            } else if (seg1 < seg2) {
                return -1;
            } else {
                i++;
                j++;
            }
        }
        
        while (i < v1.length) {
            int seg1 = Integer.parseInt(v1[i]);
            if (seg1 != 0) {
                return 1;
            } else {
                i++;
            }
        }
        
        while (j < v2.length) {
            int seg2 = Integer.parseInt(v2[j]);
            if (seg2 != 0) {
                return -1;
            } else {
                j++;
            }
        }
        
        return 0;
    }
}

Update on 11/20/18:

class Solution {
    public int compareVersion(String version1, String version2) {
        String delim = "[.]";
        String[] s1 = version1.split(delim);
        String[] s2 = version2.split(delim);
        
        int i = 0;
        int j = 0;
        
        while (i < s1.length || j < s2.length) {
            int i1 = 0;
            int i2 = 0;
            if (i < s1.length) {
                i1 = Integer.parseInt(s1[i]);
            }
            
            if (j < s2.length) {
                i2 = Integer.parseInt(s2[j]);
            }
            
            if (i1 == i2) {
                i++;
                j++;
            } else {
                return i1 - i2 < 0 ? -1 : 1;
            }
        }
        
        return 0;
    }
}

Leetcode: Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

Understand the problem:

    0.16  
6 ) 1.00
    0 
    1 0       <-- Remainder=1, mark 1 as seen at position=0.
    - 6 
      40      <-- Remainder=4, mark 4 as seen at position=1.
    - 36 
       4      <-- Remainder=4 was seen before at position=1, so the fractional part which is 16 starts repeating at position=1 => 1(6).

The key insight here is to notice that once the remainder starts repeating, so does the divided result.

You will need a hash table that maps from the remainder to its position of the fractional part. Once you found a repeating remainder, you may enclose the reoccurring fractional part with parentheses by consulting the position from the table.

The remainder could be zero while doing the division. That means there is no repeating fractional part and you should stop right away.

Just like the question Divide Two Integers, be wary of edge case such as negative fractions and nasty extreme case such as -2147483648 / -1.

Code (Java):

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (denominator == 0) {
            return "inf";
        }
        
        if (numerator == 0) {
            return "0";
        }
        
        String result = "";
        boolean neg = false;
        
        // Chceck if any negative number
        if ((numerator < 0) ^ (denominator < 0)) {
            neg = true;
        }
        
        // Transform to long to avoid overflow
        long num = numerator;
        long den = denominator;
        
        num = Math.abs(num);
        den = Math.abs(den);
        
        // Get the integer part
        long integer = num / den;
        result = String.valueOf(integer);
        
        // Get the remindar times 10
        long remindar = (num % den) * 10;
        if (remindar == 0) {
            if (neg) {
                return "-" + result;
            } else {
                return result;
            }
        }
        
        Map<Long, Integer> map = new HashMap<Long, Integer>();
        result += ".";
        
        while (remindar != 0) {
            if (map.containsKey(remindar)) {
                int pos = map.get(remindar);
                String part1 = result.substring(0, pos);
                String part2 = result.substring(pos, result.length());
                result = part1 + "(" + part2 + ")";
                
                if (neg) {
                    return "-" + result;
                } else {
                    return result;
                }
            }
            
            result += String.valueOf(remindar / den);
            map.put(remindar, result.length() - 1);
            remindar = (remindar % den) * 10;
        }
        
        if (neg) {
            return "-" + result;
        } else {
            return result;
        }
    }
}

Leetcode: Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Understand the problem:

This problem can be solved by using greedy algorithm. First check if it could be divided by 2s, if not then 3s, and then 5s. Finally check if the number is 1. If yes, return true else return false. 

Code (Java):

public class Solution {
    public boolean isUgly(int num) {
        if (num <= 0) {
            return false;
        }
        
        while (num > 1 && num % 2 == 0) {
            num /= 2;
        }
        
        while (num > 1 && num % 3 == 0) {
            num /= 3;
        }
        
        while (num > 1 && num % 5 == 0) {
            num /= 5;
        }
        
        if (num == 1) {
            return true;
        } else {
            return false;
        }
    }
}

Leetcode: Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Understand the problem:
The problem asks for implementing the sqrt(x). Note that the input and return value are integer types. For the mathematical related questions, we should naturally think of using binary search ideas. 

Solution:
The square root of an integer n is within [1, n/2 + 1]. Thus we can binary search from 1 to n/2 + 1. If the square root of the middle is less than n, the target must be in the left part. Else it must be in the right part.

Code (Java):

public class Solution {
    public int sqrt(int x) {
        if (x == 0) {
            return 0;
        }
        
        if (x < 0) {
            return -1;
        }
        
        long lo = 0;
        long hi = x / 2 + 1;
        
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            long sq = mid * mid;
            if (sq == x) {
                return (int) mid;
            }
            
            if (sq < x) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        
        return (int) hi;
    }
}

Leetcode: Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Understand the problem:
The problem is quite easy to understand. It add two binary numbers and return their sum as a string as well. The crux to solve the problem is you cannot convert the string to binary numbers and add them up, then convert back to binary. The major reason is the overflow problem. 

Solution:
We can scan the two strings from the end in reverse order. The only thing to note is the carry number. 

Code (Java):

public class Solution {
    public String addBinary(String a, String b) {
        if (a == null || a.length() == 0) {
            return b;
        }
        
        if (b == null || b.length() == 0) {
            return a;
        }
        
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        
        StringBuilder sb = new StringBuilder();
        
        while (i >= 0 || j >= 0) {
            if (i >= 0) {
                carry += a.charAt(i) - '0';
                i--;
            }
            
            if (j >= 0) {
                carry += b.charAt(j) - '0';
                j--;
            }
            
            sb.insert(0, carry % 2);
            carry /= 2;
        }
        
        if (carry == 1) {
            sb.insert(0, 1);
        }
        
        return sb.toString();
    }
}

Discussion:
The problem itself is very easy. The major concern is the insertion at the head, which may take O(n) time. An alternative solution is to append at the tail, i.e, construct the result in reverse order, and then reverse at least. Since reversing at end only takes O(n) time,  the overall time complexity is still O(n). 

Code (Java):

public class Solution {
    public String addBinary(String a, String b) {
        if (a == null || a.length() == 0) {
            return b;
        }
        
        if (b == null || b.length() == 0) {
            return a;
        }
        
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        
        StringBuilder sb = new StringBuilder();
        
        while (i >= 0 || j >= 0) {
            if (i >= 0) {
                carry += a.charAt(i) - '0';
                i--;
            }
            
            if (j >= 0) {
                carry += b.charAt(j) - '0';
                j--;
            }
            
            sb.append(carry % 2);
            carry /= 2;
        }
        
        if (carry == 1) {
            sb.append(1);
        }
        
        return sb.reverse().toString();
    }
}

Summary:
The problem itself is very easy. Several take-away messages:
1. Iterate from the end.
2. Don't forget the last carry number after iterations.
3. Try not convert the string to numbers due to the possible overflow matters. 

Leetcode: Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

Understand the problem:
The problem gives a dividend and divisor, of which are integer types. Return the division result with int type as well. Note that the problem does not allow to use multiplication, division and mod operator. 

Several special cases need to think about:
For dividend is 0, return 0.
For divisor equals to 0, we check if the dividend is positive or negative, and return the Integer.MAX_VALUE, and Integer.MIN_VALUE, respectively. 
For negative numbers. If either is negative, the result is negative. If both are negative, result is positive. 

Solution:

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (divisor == 0 && dividend > 0) return Integer.MAX_VALUE;
        if (divisor == 0 && dividend < 0) return Integer.MIN_VALUE;
        if (divisor == 1) return dividend;
        if (divisor == -1) return -dividend;
        
        boolean isDividendNeg = false;
        boolean isDivisorNeg = false;
        if (dividend < 0) {
            isDividendNeg = true;
            dividend = -dividend;
        }
        if (divisor < 0) {
            isDivisorNeg = true;
            divisor = -divisor;
        }
        
        int result = 0;
        while (dividend > divisor) {
            dividend = dividend - divisor;
            result++;
        }
        
        if ((isDividendNeg == true && isDivisorNeg == false) || 
            (isDividendNeg == false && isDivisorNeg == true))
            result = -result;
            
        return result;
    }
}

The code above has one bug: It does not handle negative number overflow problem. Consider the input -1010369383, -2147483648. The divisor is Integer.MIN_VALUE. When we flip it, it is overflowed. Consider the integer number ranges from -2^31 to 2^31 - 1. 

It is a very common bug in doing integer math arithmetic. The common approach to handle this is to convert the integer to long first. We actually have seen this situation many times before. So the correct code is:

Code (Java):

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (divisor == 0 && dividend > 0) return Integer.MAX_VALUE;
        if (divisor == 0 && dividend < 0) return Integer.MIN_VALUE;
        if (divisor == 1) return dividend;
        if (divisor == -1) return -dividend;
        
        long dividendL = (long) dividend;
        long divisorL = (long) divisor;
        
        boolean isDividendNeg = false;
        boolean isDivisorNeg = false;
        if (dividendL < 0) {
            isDividendNeg = true;
            
            dividendL = -dividendL;
        }
        if (divisor < 0) {
            isDivisorNeg = true;
            divisorL = -divisorL;
        }
        
        int result = 0;
        while (dividendL > divisorL) {
            dividendL = dividendL - divisorL;
            result++;
        }
        
        if ((isDividendNeg == true && isDivisorNeg == false) || 
            (isDividendNeg == false && isDivisorNeg == true))
            result = -result;
            
        return result;
    }
}

Discussion:
The implementation above is very inefficient especially when divisor is relative small compared to the dividend. Note that the solution above we deduct the divisor once a time. If we can deduct the divisor in exponential rate, the algorithm could be much faster.  For example, 16 / 3 = 5. In the naive solution, 
16 - 3 = 13
13 - 3 = 11
11 - 3 = 8
8 - 3 = 5
5 - 3 = 2 

We can increase the rate of divisor in exponential rate. 
16 - 3 * 2^1 = 7
16 - 3 * 2^2 = 4
16 - 3 * 2^3 < 0 
So in this case, we can see that the total number of times to shift is 3. We stop at when b is just greater than a, then go back one step where b is just less than a. Then we can calculate the partial result, in this case is 2^2 = 4. We deduct a from b,  and update a. Then we repeat the process again until a is less than b. 

Code (Java):

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        
        boolean isNeg = false;
        if ((dividend > 0 && divisor < 0) || 
            (dividend < 0 && divisor > 0))
            isNeg = true;
        
        long a = Math.abs((long)dividend);
        long b = Math.abs((long)divisor);
        
        int ans = 0;
        
        while (a >= b) {
            int shift = 0;
            while (a >= (b << shift)) {
                shift++;
            }
            
            ans += (1 << (shift - 1));
            a -= b << (shift - 1);
        }
        
        if (isNeg) ans = -ans;
        return ans;
    }
}

Summary:
This is a very interesting problem, but tricky. Two things you must be careful: Integer overflow, and we usually use a longer data type to avoid that. Secondly, the O(logn) solution is very tricky. Do understand the details.