leetcode Question: Minimum Size Subarray Sum

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

Analysis:

Here in this post we just implement O(n log n) solution using binary search.

At first it took me so much time to design the binary search on the original data array, however it is neither a neat binary search algorithm nor pass the OJ time limits.

Then from the problem description I found that "sum >= s" and word "subarray". In other words, this means we don't have to know each number, we just need to know the sum, and start/end positions (end-start leads to length).

OK, so first step is to get the sum array "ss[ ]" , where ss[0] = 0, ss[1] = sum(nums[0..1]), ss[i] = sum(nums[0,i-1]).

Then next step is to design the binary search. We know that for binary search, each time we split "some" array into two parts (remember mid = st + (ed-st)/2 ?),  check some conditions (e.g., key ? > mid element), then decide keep searching one part until meet terminating conditions.

In this problem, my solution is slight different but essentially it is the same to binary search, the key idea is:
(1) We fix starting point "st".
(2) Two pointers, p,q
(3) Binary search between p and q
(4) According to the problem, find min length starting from st.

The above steps takes O(log n) complexity. Iterate every element as the starting point will result in the final result. Therefore the time complexity n log n.


For example, let's say the number array is :
[10, 5, 13, 4, 18, 4, 5, 11, 14, 9, 16, 10, 20, 18]
We calculate the sum array:
[0, 10, 15, 28, 32 40, 44, 49, 60, 74, 83, 99, 109, 129, 137]
Set the starting points, set two pointers, and starting search:

Note that, when we get mid element between p and q, the subarray sum is ss[mid] - ss[st], but not ss[mid] - ss[p], since we fix the starting point st, only using binary search to find the other position, which has min length and sum from st is larger than s.

     [0, 10, 15, 28, 32 40, 44, 49, 60, 74, 83, 99, 109, 129, 137]
1. st,p                                                                              q
2. st,p                                mid                                        q       ss[mid]-ss[st] < s, search right half
3.  st                                    p'                                          q'
4.  st                                    p'               mid'                    q'      ss[mid]-ss[st] >= s, search left half
*(Because the length from st to any element in left half is smaller than any element in right half.)
5.  st                                    p''               q''
6.  st                                    p'' mid''       q''
7.  st                                           p'''        q'''
8.  st                                           p'''mid'''q'''
9.  st                                                  p''''q''''
So, the min length starting from 0 is (q''''- st)

Iterate st from 0 to n-1, the min length is the final result.

Code(C++):

class Solution {
public:
    void search(vector<int> &ss, int st, int p, int q, int &res, int &s){
        if (ss[q]-ss[st] >= s && p < q){
            res = min(res, q-st);    
            int mid = p + (q-p)/2;
            if (ss[mid]-ss[st] >= s){
                search(ss, st, p, mid, res, s);
            }else{
                if (mid != p){ 
                    search(ss,st, mid ,q,res, s);
                }
          }
        }
    }
    
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n==0) return 0;
        vector<int> ss(n+1,0);
        int res = n;
        
        for (int i=0;i<n;i++){
            ss[i+1] = ss[i] + nums[i];
        }
        
        if (ss[n] < s) return 0;
        
        for (int i=0;i<n;i++){
            search(ss,i, i, n,res,s);
        }
        
        return res;
    }
};

Code(Python):

class Solution:
    def search(self, ss, st, p, q, res,s):
        if ss[q]-ss[st] >= s and p < q:
            res[0] = min(res[0], q-st)
            mid = p + (q-p)/2
            if ss[mid]-ss[st] >= s:
                self.search(ss, st, p, mid, res, s)
            else:
                if mid != p:
                    self.search(ss,st, mid ,q,res, s)
                    
    # @param {integer} s
    # @param {integer[]} nums
    # @return {integer}
    def minSubArrayLen(self, s, nums):
        n = len(nums)
        if n==0:
            return 0
        ss = [0 for x in range(n+1)]
        res = [n]
        for i in range(n):
            ss[i+1] = ss[i] + nums[i]
        if ss[n] < s:
            return 0
        
        for i in range(n):
            self.search(ss, i, i, n, res, s)
        
        return res[0];
        

leetcode Qeustion: Combination Sum III

Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

Analysis:

This is quite similar to the previous problems Combination Sum I and Combination Sum II, please refer these two problems. Basically  DFS is enough to solve this problem.

Code(C++):

class Solution {
public:
    void search(vector<int> &candidates, int target, int i, int &k, vector<vector<int> >&res, vector<int> &ress){
        if (target < 0){
            return;
        }else{
            if (target == 0 && ress.size()==k){
                res.push_back(ress);
            }else{
                for (int j=i;j<candidates.size();j++){
                    if (j==0 || candidates[j] != candidates[j-1]){
                        ress.push_back(candidates[j]);
                        search(candidates, target-candidates[j], j+1, k, res, ress);
                        ress.pop_back();
                    }
                }
            }
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int> >res;
        vector<int> ress;
        vector<int> candidates(9);
        for (int i=1;i<=9;i++){
            candidates[i-1] = i;
        }
        search(candidates, n, 0, k, res, ress);
        return res;
    }
};

Code(Python):

class Solution:
    def search(self, candidates, target, i, k, res, ress):
        if target < 0:
            return
        else:
            if target == 0 and len(ress)==k:
                res.append(ress[:]) #It is important to use "ress[:]" instead of "ress"
            else:
                for j in xrange(i, len(candidates)):
                    if j==0 or candidates[j] != candidates[j-1]:
                        ress.append(candidates[j])
                        self.search(candidates, target-candidates[j], j+1, k, res, ress)
                        ress.pop(-1) #if use "ress", this will pop the elemtnes in res also
    # @param {integer} k
    # @param {integer} n
    # @return {integer[][]}
    def combinationSum3(self, k, n):
        res =[]
        ress = []
        self.search([1,2,3,4,5,6,7,8,9], n, 0, k, res, ress)
        return res
        

leetcode Question: Implement Trie (Prefix Tree)

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Analysis:

This is a classic problem related to data structure Trie. Trie is an important data structure which is very efficient for searching.  In this post, I just present the basic structure of the Trie as an introduction for beginners.

Typically, the Trie is an n-nodes tree structure, where each node has two fields:
(1) int value; //Briefly understanding, this value is to check weather this node is a word end or not.
(2) TrieNode* children[size_of_alphabet]; //This saves the tree structure.

Figure (coming from wikipedia) below shows a Trie, given keys "A", "to", "tea", "ted", "ten", "i", "in", and "inn".:

The general idea of building a Trie given a set of keys(strings) is as following:
1.  Get string S.
2.  Set pointer P as the root.
3.  Start from the 1st char C in S,
         if C does not exist in the children of current node P:
                 add a new node C to P
4.  Set P = P.C, goto step 3.
5. Set a value to the last char node (indicate this node is not only a prefix but a word).          


Some basic operations of Trie (only for this problem):
1. Insert String:
      Step 1: set pointer p as the root node
      Step 2: Start from the 1st char in the string, get the char, check if exist in p's children.
      Step 3: if not exist, create a new children for p,
      Step 4: set p = p->children[ current char], continue search until meets the string end.
      Step 5: set p->value to 1; (in this problem set to a constant is enough)  

2. Search String is pretty much similar to the insert operation. Only differences are (1) If no children exists, return false. (2) When meets the end of string, check the value of last node, to see if this is the word end, or just a prefix key.

3. Startwith is very similar to search, but no need to check the value of the node.

This problem is pretty, details see the code below. I will write more details related to Trie later.

Code(C++):

class TrieNode {
public:
    // Initialize your data structure here.
    TrieNode() {
        value = 0;
        for (int i=0;i<26;i++){
            children[i] = NULL;
        }
    }
    int value;
    TrieNode* children[26];
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
        count = 0;
    }

    // Inserts a word into the trie.
    void insert(string s) {
        TrieNode *p = root;
        int len = s.size();
        for (int i=0;i<len;i++){
            int idx = s[i] - 'a';
            if (! p->children[idx]){
                p->children[idx] = new TrieNode();
            }
            p = p->children[idx];
        }
        count++;
        p->value = count;
    }

    // Returns if the word is in the trie.
    bool search(string key) {
        TrieNode *p = root;
        int len = key.size();
        for (int i=0;i<len;i++){
            int idx = key[i] - 'a';
            if (p->children[idx]){
                p = p->children[idx];
            }else{
                return false;
            }
        }
        if (p->value!=0){
            return true;
        }else{
            return false;
        }
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *p = root;
        int len = prefix.size();
        for (int i=0;i<len;i++){
            int idx = prefix[i] - 'a';
            if (p->children[idx]){
                p = p->children[idx];
            }else{
                return false;
            }
        }
      return true;
    }

private:
    TrieNode* root;
    int count;
};

// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");

Code(Python):

class TrieNode:
    # Initialize your data structure here.
    def __init__(self):
        self.value = 0
        self.children = [None] * 26
        

class Trie:

    def __init__(self):
        self.root = TrieNode()

    # @param {string} word
    # @return {void}
    # Inserts a word into the trie.
    def insert(self, word):
        p = self.root
        for ch in word:
            idx = ord(ch) - ord('a')
            if not p.children[idx]:
                p.children[idx] = TrieNode()
            p = p.children[idx]
        p.value = 1;
                

    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the trie.
    def search(self, word):
        p = self.root
        for ch in word:
            idx = ord(ch) - ord('a')
            if not p.children[idx]:
                return False
            p = p.children[idx]
        if p.value != 0:
            return True
        else:
            return False
                

    # @param {string} prefix
    # @return {boolean}
    # Returns if there is any word in the trie
    # that starts with the given prefix.
    def startsWith(self, prefix):
        p = self.root
        for ch in prefix:
            idx = ord(ch) - ord('a')
            if not p.children[idx]:
                return False
            p = p.children[idx]
        return True
        

# Your Trie object will be instantiated and called as such:
# trie = Trie()
# trie.insert("somestring")
# trie.search("key")

leetcode Question: Course Schedule

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

Analysis:

This is a classic Graph topology sorting problem, but an easy version. We don't have to store the sort, in other words, we only need to detect if exists cycle in a directed graph.

Both DFS and BFS can be used to solve this problem.

First of all, we need to get a representation of the graph, either adjacency matrix or adjacency list is OK. In my code, you can see both ways. But note that, when the number of vertex is large, adjacency matrix usually is NOT a good option.

In DFS, the general idea, is to search each vertex in the graph recursively, if the current vertex has been visited in this search, then there must be a cycle. Be careful with the status of each vertex, here in my code, it has three states:  unvisited (=0), visited(=1), searching(=-1). The third states is to detect the existence of cycle, while the 2nd state indicate that the vertex is already checked and there is no cycle.

In BFS, the idea is much easier.  We store the indegree of each vertex, push the vertices with 0 indegree in stack (remember general BFS framwork?).  Every time, pop the stack and set indegree of connected vertices -1. In the end, if the number of popped out vertices is less than the total number of vertices in the original graph, there is cycle.


Note, in the test cases, there exist duplicates in prerequisites array.
    

BFS
Code(C++):

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        int plen = prerequisites.size();
        vector<int> ind(numCourses,0); //indegree vector
        
        //construct map & get indegree of each vertex
        vector<vector<bool> > map(numCourses, vector<bool>(numCourses, false));
        for (int i=0;i<plen;i++){
            //Important: in case of duplicates in prerequisites, only +1 indegree 
            if (map[prerequisites[i].first][prerequisites[i].second] == false){
                map[prerequisites[i].first][prerequisites[i].second] = true;
                ind[prerequisites[i].first]++;
            }
        }
        
        //BFS
        stack<int> st;
        for (int i=0;i<numCourses;i++){
            if (ind[i]==0) st.push(i);
        }
        
        int count = 0;  // to get the bool result
        
        while (!st.empty()){
            int tmp = st.top();
            st.pop();
            count ++;
            for (int i=0;i<numCourses;i++){
                if (map[i][tmp]){
                    ind[i]--;
                    if (ind[i]==0) st.push(i);
                }
            }
        }
        return count < numCourses ? false : true;
        
    }
};

Code(Python):

class Solution:
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {boolean}
    def canFinish(self, numCourses, prerequisites):
        map = [[] for x in range(numCourses)]
        ind = [0 for x in range(numCourses)]
        
        for p in prerequisites:
            if p[0] not in map[p[1]]:
                ind[p[0]] += 1
                map[p[1]].append(p[0])
        st = []
        for i in range(numCourses):
            if ind[i] == 0:
                st.append(i)
        count = 0
        while st:
            tmp = st[0]
            st.pop(0)
            count += 1
            for i in map[tmp]:
                ind[i] -= 1
                if ind[i] == 0:
                    st.append(i)
                        
        if count < numCourses:
            return False
        else: 
            return True
        
        

DFS
Code(C++):

class Solution {
public:
    bool dfs(int v, vector<int> &visit, vector<set<int> > &gr){
        if (visit[v] == 1){return true;}
        visit[v] = -1;
        for (auto it = gr[v].begin(); it != gr[v].end(); it++){
            if (visit[*it] == -1 || ! dfs(*it, visit, gr)){
                return false;
            }
        }
        visit[v] = 1;
        return true;
    }
    
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        int plen = prerequisites.size();
        vector<int> visit(numCourses,0);
        vector<set<int> > gr(numCourses);
        
        for (int i=0;i<plen;i++){
            gr[prerequisites[i].second].insert(prerequisites[i].first);
        }
        
        for (int i=0;i<numCourses;i++){
            if (!dfs(i, visit, gr)) return false;
        }
        return true;
    }
};

Code(Python):

class Solution:
    def dfs(self, v, visit, gr):
        if visit[v] == 1:
            return True
        visit[v] = -1;
        for i in gr[v]:
            if visit[i] == -1 or not self.dfs(i, visit, gr):
                return False
        visit[v] = 1
        return True
    
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {boolean}
    def canFinish(self, numCourses, prerequisites):
        gr = [[] for x in range(numCourses)]
        visit = [0 for x in range(numCourses)]
        
        for p in prerequisites:
            if p[0] not in gr[p[1]]:
                gr[p[1]].append(p[0])
                
        for v in range(numCourses):
            if visit[v]!=1:
                if not self.dfs(v, visit, gr):
                    return False
        return True

leetcode Question: Reverse Linked List

Reverse Linked List

Reverse a singly linked list.

Analysis:

Classic problem. There are multiple algorithms to reverse the linked list. Here in this post I just describe the very basics. Some advanced algorithms can be found in other problems in my blog.

To illustrate the process, say we have the linked list:
  1->2->3->4->5->null
head

In order to reverse it, we define a new pointer:
newhead->null

Iterate the original list, each time insert the node to the start of the new linked list:
1. newhead->1->null
2. newhead->2->1->null
...
5 newhead->5->4->3->2->1->null

Then just return newhead->next.

Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode * newhead = new ListNode(0);
        while (head){
            ListNode * tmp = newhead->next;
            newhead->next = head;
            head = head->next;
            newhead->next->next = tmp;
        }
        return newhead->next;
        
    }
};

Code(Python):

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param {ListNode} head
    # @return {ListNode}
    def reverseList(self, head):
        newhead = ListNode(0)
        while head:
            tmp = newhead.next
            newhead.next = head
            head = head.next
            newhead.next.next = tmp
        return newhead.next
        

leetcode Question: Isomorphic Strings

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Analysis:

    Using hashmap (dict for python) is a good idea solving this problem, since the two strings require some unique mapping. Note that it also requires no two characters may map to the same char, e.g., s="ab", t = "aa", when we check 'b' in s, although the key 'b' has not been in the map (dict for python), its value 'a' has already been used previously. So, in our implementation, we need to take care of this issue. Here I use two maps to store s->t mapping and t->s mapping, only when both maps has no key/value pairs, new pair is added to maps.

Code(C++):

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char,char> mp1;
        map<char,char> mp2;
        for (int i=0;i<s.size();i++){
            if (mp1.find(s[i])== mp1.end() && mp2.find(t[i]) == mp2.end()){
                mp1[s[i]] = t[i]; 
                mp2[t[i]] = s[i];
            }else{
                if (mp1[s[i]]!=t[i] || mp2[t[i]]!=s[i]){
                    return false;
                }
            }
        }
        return true;
    }
};

Code(Python):

class Solution:
    # @param {string} s
    # @param {string} t
    # @return {boolean}
    def isIsomorphic(self, s, t):
        d1 = {}
        d2 = {}
        for (cs, ct) in zip(s, t):
            if d1.get(cs) is None and d2.get(ct) is None:
                d1[cs] = ct
                d2[ct] = cs
            else:
                if d1.get(cs) != ct or d2.get(ct) != cs:
                    return False
        return True

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;

leetcode Question: Remove Linked List Elements

Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

Analysis:

This is a fundamental pointer manipulation question.
Just be careful with the case that removing 1st element. In the code below, a new pointer is assigned to link to the 1st element.


Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (!head) return NULL;
        ListNode *h = new ListNode(0);
        h->next = head;
        head = h;
        while (h->next){
            if (h->next->val == val){
                h->next = h->next->next;
            }else{
                h = h->next;
            }
        }
        return head->next;
    }
};

Code(Python):

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param {ListNode} head
    # @param {integer} val
    # @return {ListNode}
    def removeElements(self, head, val):
        if not head:
            return None
        h = ListNode(0)
        h.next = head
        head = h
        while h.next:
            if h.next.val == val:
                h.next = h.next.next
            else:
                h = h.next
        return head.next
        

leetcode Question: Happy Number

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

Analysis:

This problem is not difficult, just be careful with the terminating condition. In my answer, I use a set to store the previous numbers in each round. If current number is in this set, then this number cannot be "happy" since there must have an endless loop.

In python, list has the "in" operation to check the existence of individual member, in C++ I used a unordered_set from STL, and used "find" operation to check the element.

Code(C++):

class Solution {
public:
    bool isHappy(int n) {
        int res = 0;
        unordered_set<int> hist;
        
        while(true){
            if (n==1) return true;
            
            while (n > 0){
                res += (n%10)*(n%10);
                n = n/10;
            }
            
            if (hist.find(res) != hist.end()){
                return false;
            }else{
                hist.insert(res);
                n = res;
                res = 0;
            }
        }
    }
};

Code(Python):

class Solution:
    # @param {integer} n
    # @return {boolean}
    def isHappy(self, n):
        hist = []
        res = 0
        while 1:
            if n==1:
                return True
            while n > 0:
                res += (n%10) * (n%10)
                n = n/10
            if res in hist:
                return False
            else:
                hist.append(res)
                n = res
                res = 0
        

leetcode Question: Bitwise AND of Numbers Range

Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

Analysis:

At the first glance, looping from m to n seems straightforward but obviously time-consuming.
Looping from number to number seems unavailable, but we can considering looping from bit to bit.
Let's first write down some binary numbers:

1    000001
2    000010
3    000011
4    000100
5    000101
6    000110
7    000111
8    001000

Let's consider each bit from low to high, we can observe that the lowest bit, is either 1 or 0 after a number of AND operation. In this problem, because the range is continuous, the only case that lowest bit will become 1 is when m==n, and the lowest bit is 1. In other words,  for the range [m, n], if n > m, the lowest bit is always 0. Why? Because either the lowest bit of m is 0 or 1, the lowest bit of (m AND m+1) must be 0.

Now we have get the lowest bit for final result, next step is to check the 2nd lowest bit. How to do it? Just using bit shifting!  m >> 1 and n >> 1 is all we need.

When to stop looping? Consider the case that:
m =  01000
n =   01011

(1)   01011 > 01000  ->  lowest bit = 0
(2)   0101 > 0100      ->  2nd lowest bit  = 0
(3)   010 = 010          ->  3rd lowest bit = current lowest bit  0
(4)   01 = 01              ->  4th lowest bit = current lowest bit   1
(5)   0 = 0                  ->  5th lowest bit = current lowest bit   0

Final result:   01000
We can see that step (3)-(5) is unnecessary, when m=n, the other bits are just the same as current m (or n), then we can easily get the final result.

The code below are writing in two fashions: using loop and recursion. The former is easy understand, while the later is neat and simple.

Loop:
Code(C++):

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int k=0;
        while (1) {
            if (n>m){
               k = k + 1;  
            }else{
                return m << k;
            }
            m = m >> 1;
            n = n >> 1;
        }
        return m;
    }
};

Code(Python):

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def rangeBitwiseAnd(self, m, n):
        k = 0
        while True:
            if n > m:
                k += 1
            else:
                return m<<k
            m = m >> 1
            n = n >> 1
            
                
        

Recursive:
Code(C++):

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
       if (n>m){
           return rangeBitwiseAnd(m>>1, n>>1)<<1;
       }else{
           return m;
       }
    }
};

Code(Python):

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def rangeBitwiseAnd(self, m, n):
        if n > m:
            return self.rangeBitwiseAnd(m>>1, n>>1) << 1
        else:
            return m