Wednesday, September 9, 2015

Perfect Squares [LeetCode] Part 2: Solve it Mathematically

This is continuation of the previous post - Perfect Squares. I've decided to separate the problem into two parts because the solution using maths knowledge recalled me the happy time when I studied maths in high school.

Before we start, I want to confirm that all the returned values will always be in range [1,4] inclusively. Why is that? It is because we have Lagrange's Four Square Theorem, also known as Bachet's conjecture:
Every natural numbers can be expressed as a sum of four square numbers. (*)

 The theorem is proved by Lagrange in 1770. To understand the proof, I suggest you read the provided link from Wiki. And later, the talented mathematician Ramanujan did a generalization on the theorem.  I have to say it is extremely sad that Ramanujan's life was too short, even though his legacy is more than 3900 results (mostly identities and equations).

As a note, many proofs of the theorem use the Euler's four square identity:
Picture 1: Euler's Four Square Identity

Now I suggest you read this page. After reading it, you can solve this LeetCode problem mathematically! And you can also understand the algorithm to represent a natural number as a sum of four perfect squares!

Let me help you to summarize the related part of it.
From the article, you can find that if a number is in the form n = 4^r (8k+7) (Where ^ is power), then n cannot be represented as a sum of less than 4 perfect squares. If n is not in the above form, then n can be represented as a sum of 1, 2, or 3 perfect squares.

So now you know the basic theory behind, we can start coding!

I. Python Code
view plainprint?
  1. class Solution(object):  
  2.       
  3.     def is_square(self, n):  
  4.         temp = int(math.sqrt(n))  
  5.         return temp*temp == n  
  6.           
  7.     def numSquares(self, n):  
  8.         """ 
  9.         :type n: int 
  10.         :rtype: int 
  11.         """  
  12.         while n & 3 == 0: #n % 4  
  13.             n = n >> 2  
  14.         if n % 8 == 7: return 4  
  15.           
  16.         sqrt_n = int(math.sqrt(n))  
  17.         if self.is_square(n): return 1  
  18.         else:  
  19.             for i in range(1, sqrt_n+1):  
  20.                 if self.is_square(n-i*i):  
  21.                     return 2  
  22.         return 3  
II. Java Code
view plainprint?
  1. public class Solution {  
  2.     public boolean is_square(int n){  
  3.         int temp = (int) Math.sqrt(n);  
  4.         return temp * temp == n;  
  5.     }  
  6.     public int numSquares(int n) {  
  7.         while ((n & 3) == 0) //n % 4 == 0  
  8.             n >>= 2;  
  9.         if ((n & 7) == 7) return 4; //n% 8 == 7  
  10.           
  11.         if(is_square(n)) return 1;  
  12.         int sqrt_n = (int) Math.sqrt(n);  
  13.         for (int i = 1; i<= sqrt_n; i++){  
  14.             if (is_square(n-i*i)) return 2;  
  15.         }  
  16.         return 3;  
  17.     }  
  18. }  
III. C++ Code
view plainprint?
  1. class Solution {  
  2. public:  
  3.     int is_square(int n){  
  4.         int temp = (int) sqrt(n);  
  5.         return temp * temp == n;  
  6.     }  
  7.     int numSquares(int n) {  
  8.         while ((n & 3) == 0) //n%4 == 0  
  9.             n >>= 2;  
  10.         if ((n & 7) == 7) return 4; //n % 8 == 7  
  11.         if(is_square(n)) return 1;  
  12.         int sqrt_n = (int) sqrt(n);  
  13.         for(int i = 1; i<= sqrt_n; i++){  
  14.             if (is_square(n-i*i)) return 2;  
  15.         }  
  16.         return 3;  
  17.     }  
  18. };  
IV. Javascript Code
view plainprint?
  1. /** 
  2.  * @param {number} n 
  3.  * @return {number} 
  4.  */  
  5. var is_square = function(n){  
  6.     var t = Math.floor(Math.sqrt(n));  
  7.     return t * t == n;  
  8. }  
  9. var numSquares = function(n) {  
  10.     while ((n & 3) ===0) //n%4 == 0  
  11.         n >>=2;  
  12.     if((n&7) == 7) return 4; //n % 8 = 7  
  13.     if(is_square(n)) return 1;  
  14.     var sqrt_n = Math.floor(Math.sqrt(n));  
  15.     for(var i=1; i<= sqrt_n; i++){  
  16.         if(is_square(n-i*i)) return 2;  
  17.     }  
  18.     return 3;  
  19. };  
No comments:
Labels: , , , , ,

Perfect Squares [LeetCode]

Problem Description
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
Solutions

 I. Dynamic Programming
This problem can be solved by dynamic programming. If we call dp is the array of least numbers of perfect square numbers for each integer from 1 to n, we have the following relation:
dp[n] = 1 + min (dp[n-i*i] for i from 1 to square root of n)
However, (as of 2015-09-09) I saw people complain that the dynamic programming solution got Time Limit Exception (TLE) with Python. Therefore, StefanPochmann, a member of LeetCode, solved the solution by using "Static" dynamic programming. That means the array dp is a static variable of the class Solution.
Dynamic Programming C++ Code
view plainprint?
  1. int numSquares(int n) {  
  2.     static vector<int> dp {0};  
  3.     while (dp.size() <= n) {  
  4.         int m = dp.size(), squares = INT_MAX;  
  5.         for (int i=1; i*i<=m; ++i)  
  6.             squares = min(squares, dp[m-i*i] + 1);  
  7.         dp.push_back(squares);  
  8.     }  
  9.     return dp[n];  
  10. }  
Dynamic Programming C++ : Reverse for-loops inside out
view plainprint?
  1. int numSquares(int n) {  
  2.     static vector<int> dp {0};  
  3.     int m = dp.size();  
  4.     dp.resize(max(m, n+1), INT_MAX);  
  5.     for (int i=1, i2; (i2 = i*i)<=n; ++i)  
  6.         for (int j=max(m, i2); j<=n; ++j)  
  7.             if (dp[j] > dp[j-i2] + 1)  
  8.                 dp[j] = dp[j-i2] + 1;  
  9.     return dp[n];  
  10. }  
Dynamic Programming Python Code
view plainprint?
  1. class Solution(object):  
  2.     _dp = [0]  
  3.     def numSquares(self, n):  
  4.         dp = self._dp  
  5.         while len(dp) <= n:  
  6.             dp += min(dp[-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1,  
  7.         return dp[n]  
Dynamic Programming Ruby Code
view plainprint?
  1. $dp = [0]  
  2. def num_squares(n)  
  3.   $dp << (1..$dp.size**0.5).map { |i| $dp[-i*i] }.min + 1 until $dp[n]  
  4.   $dp[n]  
  5. end  

However, in Python, if you test that code with test case 1,000,000, you will get the TLE error.
NOTE: I'm very happy that LeetCode now provides testing against custom input (From 2015-09-09). This feature I've seen in Hackerrank and wanted LeetCode to implemente it for quite a long time ago.

II. Breadth First Search
Picture 1: Graph of numbers 
In this problem, we define a graph where each number from 0 to n is a node. Two numbers p < q is connected if (q-p) is a perfect square.
So we can simply do a Breadth First Search from the node 0.
Below is the Python code that even can pass the custom test case of 1,000,000.
Breadth First Search Python Code
view plainprint?
  1. class Solution(object):  
  2.     _dp = [0]  
  3.     def numSquares(self, n):  
  4.         """ 
  5.         :type n: int 
  6.         :rtype: int 
  7.         """  
  8.          
  9.         q1 = [0]  
  10.         q2 = []  
  11.         level = 0  
  12.         visited = [False] * (n+1)  
  13.         while True:  
  14.             level += 1  
  15.             for v in q1:  
  16.                 i = 0  
  17.                 while True:  
  18.                     i += 1  
  19.                     t = v + i * i  
  20.                     if t == n: return level  
  21.                     if t > n: break  
  22.                     if visited[t]: continue  
  23.                     q2.append(t)  
  24.                     visited[t] = True  
  25.             q1 = q2  
  26.             q2 = []  
  27.                   
  28.         return 0  
PS: For now, I do not have very much time to write the code in Java, C++, C#, Javacript or Ruby, so you are extremely welcome to post your solutions as a comment!
1 comment:
Labels: , , , , , ,

Monday, September 7, 2015

First Bad Version [LeetCode]

Problem Description
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Solution
This is a typical example of type of binary search that does not return immediately after finding the satisfied element.
Suppose we have 2 pointers start and end. We take middle = (start + end) / 2. Now we check if middle is a bad version. If it is yes, we do not stop here, but we will search on the left, in order to find out that whether there is some smaller bad version. By going to the left, we set end = middle - 1. So if we find nothing on the left, we return end + 1, because it is the last time we saw a bad version. If middle is not a bad version, we simply go to the right by setting start = middle + 1.

One thing to note is that in some programming language, to avoid overflow, we use (end-start)/2 + start instead of (start + end)/2
I. Python Code
view plainprint?
  1. # The isBadVersion API is already defined for you.  
  2. # @param version, an integer  
  3. # @return a bool  
  4. # def isBadVersion(version):  
  5.   
  6. class Solution(object):  
  7.     def firstBadVersion(self, n):  
  8.         """ 
  9.         :type n: int 
  10.         :rtype: int 
  11.         """  
  12.         start, middle, end = 1, 1, n  
  13.         while start <= end:  
  14.             middle = (start + end) >> 1  
  15.             if isBadVersion(middle): end = middle - 1  
  16.             else: start = middle + 1  
  17.         return end + 1  
II. Java Code
view plainprint?
  1. /* The isBadVersion API is defined in the parent class VersionControl. 
  2.       boolean isBadVersion(int version); */  
  3.   
  4. public class Solution extends VersionControl {  
  5.     public int firstBadVersion(int n) {  
  6.         int start = 1;  
  7.         int end = n;  
  8.         int middle;  
  9.         while(start <= end){  
  10.             middle = ((end - start)>>1) + start;  
  11.             if (isBadVersion(middle)) end = middle - 1;  
  12.             else start = middle + 1;  
  13.         }  
  14.         return end + 1;  
  15.     }  
  16. }  
III. C++ Code
view plainprint?
  1. // Forward declaration of isBadVersion API.  
  2. bool isBadVersion(int version);  
  3.   
  4. class Solution {  
  5. public:  
  6.     int firstBadVersion(int n) {  
  7.         int start = 1;  
  8.         int end = n;  
  9.         int middle;  
  10.         while(start <= end){  
  11.             middle = ((end-start)>> 1) + start;  
  12.             if(isBadVersion(middle)) end = middle - 1;  
  13.             else start = middle + 1;  
  14.         }  
  15.         return end + 1;  
  16.     }  
  17. };  
IV. Javascript Code
view plainprint?
  1. /**  
  2.  * Definition for isBadVersion()  
  3.  *   
  4.  * @param {integer} version number  
  5.  * @return {boolean} whether the version is bad  
  6.  * isBadVersion = function(version) {  
  7.  *     ...  
  8.  * };  
  9.  */  
  10.   
  11. /**  
  12.  * @param {function} isBadVersion()  
  13.  * @return {function}  
  14.  */  
  15. var solution = function(isBadVersion) {  
  16.     /**  
  17.      * @param {integer} n Total versions  
  18.      * @return {integer} The first bad version  
  19.      */  
  20.     return function(n) {  
  21.         var start = 1;  
  22.         var end = n;  
  23.         while(start <= end){  
  24.             var middle = ((end-start) >> 1) + start;  
  25.             if (isBadVersion(middle)) end = middle - 1;  
  26.             else start = middle + 1;  
  27.         }  
  28.         return end + 1;  
  29.     };  
  30. };  
3 comments:
Labels: , , , , ,

Sunday, September 6, 2015

H-Index II [LeetCode]

Problem Description
Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?
Solution
In the previous version, we sorted citations in reverse order. In this version of problem, the citations array is in ascending order.
I. O(n) Solution
As we already know in the previous version of finding H-Index, we can solve the problem in linear time. Below is the 1-line Python solution:
view plainprint?
  1. class Solution(object):  
  2.     def hIndex(self, citations):  
  3.         """ 
  4.         :type citations: List[int] 
  5.         :rtype: int 
  6.         """  
  7.         return max(min(v, len(citations)-k) for k, v in enumerate(citations + [0]))  
II. O(logn) Solution
Since we already knew about how to solve the problem in linear time, we try to find another solution. As usual, the idea is to find O(logn) solution by binary search.
Our normal logic when using binary search is that we have a start and end point. We will check the middle= (start + end) /2. (In some language, to avoid overflow we can use (end-start)/2 + start )
What we need to find out now is when we should stop the search, or going to left or right.


1. When we should stop?
Suppose that middle is not in final stage (where start > end) and we decide to stop. There are (n-middle) elements are at least citations[middle], and other (middle ) elements are at most citations[middle]. This suggests that if citations[middle] = (n-middle) = h (where n is the number of elements in citations),  then we have at least h elements are at least h, and other middle = n-h elements are at most h. So h is an H-index.
Is it h  the largest? Suppose there is another h" > h and h" is also an H-index. Consider the element at n-h". Since there are at least h" elements which are at least h", then citations[n-h"] >= h">h. However, we have n-h" < n-h, therefore citations[n-h"] < citations[n-h] = h, or we have h > h. This is contradictory. So h is the largest H-index. This means that we should stop the search here!

2. When we should go to the left and right
The analysis in (1) suggest that we should compare citations[middle] and (n-middle) in order to decide whether we should go to left or right in binary search.

a. If citations[middle] < n-middle: 
Is it possible to stop or go left in this case? Suppose it is. That means there is a number h >= n-middle, and h is an H-index. Then there are h elements which are at least h. Therefore:
citations[n-h] > h >= n-middle > citations[middle]
However,
h >= n-middle  => middle >= n-h
That means citations[n-h] <= citations[middle]. This is contradictory.
So we should go to the right in this case.

b. If citations[middle] > n-middle: 
This is not same as the case (a). Easily we can see that h = n-middle is an H-index. But there might be other elements on the left satisfy the H-index condition. So we simply go to the left to search more.
Note that the current position is end + 1 after we set the end pointer to middle-1. And also, while searching on the left, if we go to the left another time, then current h= n-middle is not the largest H-index. But if we never go to the left again, then the pointer end keeps unchanged, so we can simply return n-end-1 when the search is terminated.
We come to coding now.

I. Python Code
view plainprint?
  1. class Solution(object):  
  2.     def hIndex(self, citations):  
  3.         """ 
  4.         :type citations: List[int] 
  5.         :rtype: int 
  6.         """  
  7.         n = len(citations)   
  8.         start, end = 0, n-1  
  9.         while start <= end:  
  10.             middle = (start + end) / 2  
  11.             if citations[middle] == n-middle: return citations[middle]  
  12.             elif citations[middle] < n - middle: start = middle + 1  
  13.             else: end = middle - 1  
  14.         return n-end-1  
II. Java Code
view plainprint?
  1. public class Solution {  
  2.     public int hIndex(int[] citations) {  
  3.         int n = citations.length;  
  4.         int start = 0;  
  5.         int end = n-1;  
  6.         int middle;  
  7.         while (start <= end){  
  8.             middle = (end-start)/2 + start;  
  9.             if (citations[middle] == n-middle) return citations[middle];  
  10.             else if(citations[middle] < n-middle) start = middle + 1;  
  11.             else end = middle - 1;  
  12.         }  
  13.         return n - end - 1;  
  14.     }  
  15. }  
III. C++ Code
view plainprint?
  1. class Solution {  
  2. public:  
  3.     int hIndex(vector<int>& citations) {  
  4.         int n = citations.size();  
  5.         int start = 0;  
  6.         int end = n - 1;  
  7.         int middle = 0;  
  8.         while(start <= end){  
  9.             middle = (end-start)/2 + start;  
  10.             if (citations[middle] == n-middle) return citations[middle];  
  11.             else if(citations[middle] < n-middle) start = middle + 1;  
  12.             else end = middle - 1;  
  13.         }  
  14.         return n-end-1;  
  15.     }  
  16. };  
2 comments:
Labels: , , , ,

Thursday, September 3, 2015

H-Index [LeetCode]

Problem Description
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.
Note: If there are several possible values for h, the maximum one is taken as the h-index.
Solution

As we know, H-Index is a measure of productivity and citation impact of a researcher. It is also called Hirsch index or Hirsch number after the name of the physicist Jorge Hirsch.
Picture 1: H-Index for decreasing citations array (Credit: Wiki)

Supposed that citations is an array of numbers of citations of a researcher. We can easily see that the following formula holds if citations is sorted in decreasing order:

h-index of citations = max (min (citations[i], i) for all i from 1 to number of papers)

Therefore, we can easily implement the calculation of h-index by sorting the array in decreasing order then applying the above formula. Below is the 2-line Python code in O(nlogn) time.
view plainprint?
  1. class Solution(object):  
  2.     def hIndex(self, citations):  
  3.         """ 
  4.         :type citations: List[int] 
  5.         :rtype: int 
  6.         """  
  7.         citations.sort(reverse=True)  
  8.         return max([min(k+1, v) for k,v in enumerate(citations)]) if citations else 0  
By sorting, it takes O(nlogn) time complexity.
However, we can do much better by an O(n) time algorithm. Pause yourself for a few minutes to think about it before continue reading ^_^.

We have some simple observation here, but it really helps to improve the performance. For each number h from 0 to n where n is the number of papers, we need to find out how many citations of a paper equal h called equal_h. Based on this, we can find the number of citations values that is at least h, and no more than h. To find the number of citations value that is at least h, we take sum of equal_h[i] for i from h to n!!! And similarly, to find the number of citations values that is no more than h citations each, we can sum up equal_h[i] for i from 0 to i. And we can find the h-index by simple running from the back of the array equal_h.
So if running from the back of the array equal_h , and h is the first index that satisfies the following conditions:
equal_h[h] + equal_h[h+1] + ... + equal_h[n] >= h (*)
equal_h[0] + equal_h[1] + ... + equal_h[h] >= N-h (**)
Then h is what we are looking for.
However, we have:
equal_h[0] + equal_h[1] + ... + equal_h[n] = n
Therefore:
equal_h[0] + equal_h[1] + ... + equal_h[h] = n- (equal_h[h+1] + ... + equal_h[n])
Another note is that since h is the first element satisfies the 2 above conditions, then h+1 does not satisfies one of them, meaning that either
(1): { equal_h[h+1] + equal_h[h+2] + ... + equal_h[n] <= h
or (2): { equal_h[h+1] + equal_h[h+2] + ... + equal_h[n] >= h+1
and equal_h[0] + equal_h[1] + ... + equal_h[h+1] < N-(h+1) }
(1) suggests that:
equal_h[0] + equal_h[1] + ... + equal_h[h] >=N-h which is (**)
(2) suggests that:
equal_h[h+2] + equal_h[h+3] + ... + equal_h[n] >= h+2
This inequality will be repeated until equal_h[n] >= n , which is wrong.

So all we need is to find the first h satisfies the condition (*), and we do not need to check the condition (**).
Below are the codes implement in different languages.

I. Python code - O(n) 
view plainprint?
  1. class Solution(object):  
  2.     def hIndex(self, citations):  
  3.         """ 
  4.         :type citations: List[int] 
  5.         :rtype: int 
  6.         """  
  7.         n = len(citations)  
  8.         equal_h = [0] * (n+1)  
  9.         for h in range(n):  
  10.             if citations[h] >= n: equal_h[n] += 1  
  11.             else: equal_h[citations[h]] += 1  
  12.           
  13.         s = 0  
  14.         for h in range(n,0, -1):  
  15.             s += equal_h[h]  
  16.             if s>=h:  
  17.                 return h  
  18.               
  19.         return 0  
II. Java Code - O(n)
view plainprint?
  1. public class Solution {  
  2.     public int hIndex(int[] citations) {  
  3.         int n = citations.length;  
  4.         int [] equal_h = new int[n+1];  
  5.         for (int h = 0; h<n; h++){  
  6.             if(citations[h] >= n) equal_h[n] += 1;  
  7.             else equal_h[citations[h]] += 1;  
  8.         }  
  9.         int s = 0; //we don't need check overflow here coz sum always <= n  
  10.         for (int h = n; h>0; h--){  
  11.             s += equal_h[h];  
  12.             if (s >= h) return h;  
  13.               
  14.         }  
  15.         return 0;  
  16.     }  
  17. }  
No comments:
Labels: , , ,

Wednesday, September 2, 2015

Integer to English Words [LeetCode]

Problem Description
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"
Solution
To solve it, we divide the input number into chunks so that each has 3 digits.
One note about this LeetCode problem is that some edge cases such as "101" is considered as "One Hundred One" instead of "One Hundred And One". So this should not be correct in real life application!

I. Java Solution
view plainprint?
  1. public class Solution {  
  2.       
  3.     String[] map1 = new String [] {"", " One", " Two", " Three", " Four", " Five",   
  4.             " Six", " Seven", " Eight", " Nine", " Ten", " Eleven", " Twelve",   
  5.             " Thirteen", " Fourteen", " Fifteen", " Sixteen", " Seventeen",   
  6.             " Eighteen", " Nineteen" };  
  7.               
  8.     String[] map2 = new String[] {"", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty",   
  9.         " Seventy", " Eighty", " Ninety" };  
  10.           
  11.     String[] map3 = new String[] {"", " Thousand", " Million", " Billion" };  
  12.     final String HUNDRED = " Hundred";  
  13.       
  14.     public String threeDigitToWords(int num){  
  15.         String result = "";  
  16.         if (num > 99){  
  17.             result = map1[num / 100] + HUNDRED;  
  18.         }  
  19.         num %= 100;  
  20.         if(num < 20){  
  21.             result +=  map1[num];  
  22.         }else {  
  23.             result += map2[num/10] + map1[num%10];  
  24.         }  
  25.         return result;  
  26.     }  
  27.       
  28.     public String numberToWords(int num) {  
  29.         if (num == 0) return "Zero";  
  30.         String result = "";  
  31.           
  32.         int i = 0; //check if it is thousand, million, billion  
  33.         while(num != 0){  
  34.             if(num % 1000 != 0)  
  35.                 result = threeDigitToWords(num % 1000) + map3[i] + result;  
  36.             i++;  
  37.             num /= 1000;  
  38.         }  
  39.         return result.trim();  
  40.     }  
  41. }  
II. Python Solution
view plainprint?
  1. class Solution(object):  
  2.     def __init__(self):  
  3.         self.map1 = ["", " One", " Two", " Three", " Four", " Five",   
  4.             " Six", " Seven", " Eight", " Nine", " Ten", " Eleven", " Twelve",   
  5.             " Thirteen", " Fourteen", " Fifteen", " Sixteen", " Seventeen",   
  6.             " Eighteen", " Nineteen" ]  
  7.               
  8.         self.map2 = ["", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty",   
  9.             " Seventy", " Eighty", " Ninety" ]  
  10.               
  11.         self.map3 = ["", " Thousand", " Million", " Billion"]  
  12.         self.HUNDRED = " Hundred"  
  13.           
  14.     def threeDigitToWords(self, num):  
  15.         result = ""  
  16.         if num > 99 :   
  17.             result = self.map1[num / 100] + self.HUNDRED  
  18.   
  19.         num %= 100  
  20.         if num < 20:  
  21.             result +=  self.map1[num]  
  22.         else:  
  23.             result += self.map2[num/10] + self.map1[num%10]  
  24.           
  25.         return result  
  26.       
  27.     def numberToWords(self, num):  
  28.         """ 
  29.         :type num: int 
  30.         :rtype: str 
  31.         """  
  32.         if num == 0: return "Zero"  
  33.         result = ""  
  34.           
  35.         i = 0 #check if it is thousand, million, billion  
  36.         while num != 0:  
  37.             if num % 1000 != 0:  
  38.                 result = self.threeDigitToWords(num % 1000) + self.map3[i] + result  
  39.             i+=1  
  40.             num /= 1000  
  41.           
  42.         return result[1:];  
Appendix B: Pythonic Solution
Below is the short pythonic code.
view plainprint?
  1. class Solution(object):  
  2.     def numberToWords(self, num):  
  3.         """ 
  4.         :type num: int 
  5.         :rtype: str 
  6.         """  
  7.         def make_lists(s): return [[]] + [[i] for i in s.split()]  
  8.           
  9.         under20 =  make_lists('One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \  
  10.                'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen')  
  11.         tens = [[]] + make_lists('Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety')  
  12.         thousands =  make_lists("Thousand Million Billion")  
  13.           
  14.         def threeDigitToWords(n):  
  15.             return (under20[n/100] + ['Hundred'] if n>99 else []) + tens[n%100/10] + (under20[n%100] if n%100 < 20 else under20[n%100%10])  
  16.               
  17.         def toWords(n,i):  
  18.             return (toWords(n/1000,i+1) if n else []) + threeDigitToWords(n%1000) + (thousands[i] if n%1000 else [])    
  19.           
  20.         return ' '.join(toWords(num,0)) or 'Zero'  
view plainprint?
  1. class Solution(object):  
  2.     def numberToWords(self, num):  
  3.         """ 
  4.         :type num: int 
  5.         :rtype: str 
  6.         Credited: LeetCode 
  7.         """  
  8.         under20 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \  
  9.                'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()  
  10.         tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()  
  11.         def find_words(n):  
  12.             if n < 20:  
  13.                 return under20[n-1:n]  
  14.             if n < 100:  
  15.                 return [tens[n/10-2]] + find_words(n%10)  
  16.             if n < 1000:  
  17.                 return [under20[n/100-1]] + ['Hundred'] + find_words(n%100)  
  18.             for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):  
  19.                 if n < 1000**(p+1):  
  20.                     return find_words(n/1000**p) + [w] + find_words(n%1000**p)  
  21.         return ' '.join(find_words(num)) or 'Zero'  
No comments:
Labels: , , , , , ,

Tuesday, September 1, 2015

Missing Number [LeetCode]

Problem Description
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Solution
Again, similar to other bit manipulation problems, we can use XOR operator. One NOTE about XOR:
1. if A ^ B = C then A = B ^ C, and B = A ^ C,
2. and A^A = 0, 0 ^ A = A,
where ^ is XOR bit operator.
Since nums contains numbers from 0 to n with one number is missing, then if we xor all the numbers in nums with 0 ^ 1 ^ 2 ... ^ n, we will get the number we need to find.
Below is the codes.

I. Java Code
view plainprint?
  1. public class Solution {  
  2.     public int missingNumber(int[] nums) {  
  3.         int r = 0;  
  4.         for (int i = 0; i<nums.length; i++){  
  5.             r ^=  i ^ nums[i];  
  6.         }  
  7.         return r ^ nums.length;  
  8.     }  
  9. }  
II. Python Code
view plainprint?
  1. class Solution(object):  
  2.     def missingNumber(self, nums):  
  3.         """ 
  4.         :type nums: List[int] 
  5.         :rtype: int 
  6.         """  
  7.         r = 0  
  8.         for i in range(len(nums)):  
  9.             r ^= i ^ nums[i]  
  10.         return r ^ len(nums)  
III. C++ Code
view plainprint?
  1. class Solution {  
  2. public:  
  3.     int missingNumber(vector<int>& nums) {  
  4.         int r = 0;   
  5.         for (int i = 0; i<nums.size(); i++){  
  6.             r ^= i ^ nums[i];  
  7.         }  
  8.         return r ^ nums.size();  
  9.     }  
  10. };  
IV. Javascript Code
view plainprint?
  1. /**  
  2.  * @param {number[]} nums  
  3.  * @return {number}  
  4.  */  
  5. var missingNumber = function(nums) {  
  6.     var r = 0;  
  7.     for(var i = 0; i<nums.length; i++){  
  8.         r ^= i ^ nums[i];  
  9.     }  
  10.     return r ^ nums.length;  
  11. };  
Appendix A: Other methods
We can use other methods such as Hash Table with O(n) space complexity. We also can get the number by summing up all the elements in the array, the take the difference of n(n+1)/2 and that sum. (NOTE: n(n+1)/2 is the sum of numbers from 0 to n).
No comments:
Labels: , , , , ,

Single Number III [LeetCode]

Problem Description
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
Solution 
Again, Hash Table solution is not discussed here.
This problem is an extension of the other two problems Single Number and Single Number II. As we know that for an integer N:
0 ^ N = N
N ^ N = 0
where ^ is XOR bit operator.
If we call the two numbers that we need to find is A and B. We all know that if we XOR all the elements in the provided array, we will get A ^ B. This is a lot of information!
Now, we notice that A and B must be different at some bit at position t in their binary representations. So if we divide the set of numbers into 2 set, one is the set of all the numbers that have the same bit at position t as A, the other is the set of all numbers that have the same bit at position t as B. These 2 sub-sets have a special characteristic: all numbers appear 2 times, except 1. This bring us to the Single Number problem.

I. Java Code
view plainprint?
  1. public class Solution {  
  2.     public int[] singleNumber(int[] nums) {  
  3.         int A = 0;  
  4.         int B = 0;  
  5.         int AXORB = 0;  
  6.         for(int i = 0; i<nums.length; i++){  
  7.             AXORB ^= nums[i];  
  8.         }  
  9.           
  10.         AXORB = (AXORB & (AXORB - 1)) ^ AXORB; //find the different bit  
  11.         for(int i = 0; i<nums.length; i++){  
  12.             if((AXORB & nums[i]) == 0)  
  13.                 A ^= nums[i];  
  14.             else  
  15.                 B ^= nums[i];  
  16.         }  
  17.         return new int[]{A, B};  
  18.     }  
  19. }  
No comments:
Labels: , ,
Subscribe to: Posts (Atom)