# Week 3 | Grind 169 | Blind 75

Posted on Dec 25, 2020

## 1. Same Tree

Given the roots of two binary trees `p` and `q`, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

### Iterative

`````` bool isSameTree(TreeNode* p, TreeNode* q) {
queue<TreeNode*> que;
if(p==NULL || q==NULL) return p==q;
que.push(p); que.push(q);
while(!que.empty())  {
TreeNode* left = que.front(); que.pop();
TreeNode *right = que.front(); que.pop();
if(left==NULL && right==NULL) continue;
if(left==NULL || right==NULL) return false;
if(left->val != right->val) return false;
que.push(left->left);
que.push(right->left);
que.push(left->right);
que.push(right->right);
}
return true;
}
``````

### Recursive

``````bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == NULL &&  q== NULL) return true;
if(p == NULL ||  q== NULL) return false;
if(p->val != q->val) return false;
return isSameTree(p->right, q->right) && isSameTree(p->left, q->left) ;
}
``````

## 2. Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the `Hamming weight`).

Note:

• Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.

• In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer.

• Practice

### Naive

``````int setBits(int N) {

int count = 0;
while(N){
count += (N & 1);
N = N >> 1;
}
return count;
}
``````

### Brian Kernighan’s Algorithm

``````int setBits(int N) {
int count = 0;
while (N) {
N &= (N - 1);
count++;
}
return count;
}
``````

### STL

``````int hammingWeight(uint32_t n) {
return __builtin_popcount(n);
}
``````

### Converting to string

``````int hammingWeight(uint32_t n){

string bin = bitset<32>(n).to_string();
int counter = count(bin.begin(), bin.end(), '1');
return counter;

}
``````

## 3. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string `""`.

### Horizontal scanning

``````    string longestCommonPrefix(vector<string>& str) {

int n = str.size();

if(n == 1) return str;

string ans = "";
int longest = INT_MAX, curr, j, k;

for(int i=0; i<n-1; i++){
curr = j = k = 0;
int a = str[i].size(), b = str[i+1].size();
while(j < a  and k < b and str[i][j++] == str[i+1][k++])
curr++;
if(curr == 0) return "";
if(curr < longest){
ans = str[i].substr(0 , curr);
longest = curr;
}
}

return ans;

}
``````

### Vertical scanning

``````    string longestCommonPrefix(vector<string>& str) {

int n = str.size();
if (n == 0) return "";
for (int i = 0; i < str.size(); i++){
char c = str[i];
for (int j = 1; j < n; j ++)
if (i == str[j].size() || str[j][i] != c)
return str.substr(0, i);
}
return str;
}
``````

## 4. Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

``````int singleNumber(vector<int>& nums) {
int ans = 0;

for(auto e: nums)
ans ^= e;

return ans;
}
``````