Entering edit mode

Click here to Practice

Submit Problem to OJ

**Problem Statement**

You are given a function: *char FindExtraLetter(string A, string B, int N)*;

The function accepts two strings 'A' and 'B' of size 'N' and 'N' + 1 respectively, if we remove one character from 'B' then 'B' becomes the permutation of 'A'. Your task is to return that character.

**Example**:

**Input**:

```
A="cocubes", B="ocucybse", N = 7
```

**Output**:

```
y
```

**Explanation**:

If we remove character 'y' from B then B becomes "ocucbse" which is a permutation of A ("cocubes").

**The custom input format of the above case:**

```
5
cocubes
ocucybse
```

(The first line represents 'N', the second line represents the string 'A' and the third line represents the string 'B' which is of size 'N + 1')

**Sample input**

```
A = "abcdefghij", B = "jihgfedkcba", N = 10
```

**Sample Output**

```
k
```

**The custom input format for the above case:**

```
10
abcdefghij
jihgfedkcba
```

(The first line represents 'N', the second line represents the string 'A' and the third line represents the string 'B' which is of size 'N+1')

Problem Statement

You are given a function:

char findExtraLetter(string A, string B, int N);

The function accepts two strings *A' and 'B' of size 'N' and 'N'+1 respectively. If we remove one character from 'B', then '8' becomes the permutation of 'A'. Your task is to return that

character.

Example:

Input:

A- "cocubes*, B= "ocucybse", N = 7

Output:

Explanation:

If we remove character 'y' from | Y then B becomes "ocucbse" which is a permutation of A ("cocubes"),

The custom input format for the above case:

cocubes

ocucybse

(The first line represents 'N', the second line represents the string 'A' and the third line represents the string 'B' which is of size 'N+1")

Sample input

A

"abcdefghig", B - "jingfedkeba", N - 10

Sample Output

1560

k

The custom input format for the above case:

10

abodefghij

jihgfedkeba

(The first line represents 'N', the second line represents the string *A' and the third line

represents the string 'B' which is of size 'N+1')

Problem Statement

A binary tree is represented by the following structure:

```
struct TreeNode
{
int data;
struct TreeNode* left;
struct TreeNode* right;
};
```

Implement the following function:

```
int LeafNodesLevel(struct TreeNode* root);
```

The function accepts the root node of a binary tree 'root' as its argument. Implement the function to find the sum of leaf nodes at same level and return the product of all the sums.

**Assumption**:

- Level of input tree is between D and 2D

**Note**:

- If the input tree is NULL (None in case of Python), then return D
- If all leaf nodes are at the same level then return the sum of leaf nodes

**Example**:

**Input**:

**Output**:

```
36
```

**Explanation**:

Sum of the leaf nodes at level 3 is 3 ( 1+ 2) and sum of leaf nodes at level 2 is 12 ( 5+ 4+ 3) and the product of these sums is 36 ( 3 x 12).

**The custom input format for the above case**:

```
3
9 8 7 6 5 4 3 1 2 -1 -1 -1 -1 -1 -1
```

(The first line represents the height of the tree, the second line represents the level order traversal of the given tree, in second line -1 represents an empty node)

**Sample Input**

**Sample output**

```
16
```

**The custom input format for the above case:**

```
2
10 9 2 1 7 -1 -1
```

(The first line represents the height of the tree, the second line represents the level order traversal of the given tree, in second line -1 represents an empty node)

**Instructions** :

- This is a template based question, DO NOT write the "main" function.
- Your code is judged by an automated system, do not write any additional welcome/greeting messages.
- "Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
- Additional score will be given for writing optimized code both in terms of memory and execution time.

A binary tree is represented by the following structure:

struct TreeNode

{

int data;

struct TreeNade* left;

struct TreeNode* right;

};

Implement the following function:

int LeafNodesLevel (struct TreeNode* root) ;

the of a binary tree 'root' as its argument. Implement the function to find root nade The function accepts the 80209 0 N

at same level and return the product of all the sums

Assumption:

Level of input tree is between 0 and 20

Note:

If the input tree is NULL (None of in case of Python), then return D

If all leaf nodes are at the same level then return the sum of leaf nodes

Example:

Input:

root:

Output:

36

Explanation:

Sum of leaf nodes at level 3 is 3 (1 + 2) and sum of leaf nodes at level 2 is 12 (5

+ 3) and the product of these sums is 36 (3 * 12).

The custom input format for the above case:

9 8 7 6 5 4 3 1 2 -1 -1 -1 -1 -1 -1

Sample Output

16

2

The custom input format for the above case:

10 9 2 1 7 -1 -1

(The first line represents the height of the tree, the second line represents the level order

traversal of the given tree, in second line -1 represents an empty node)

Instructions:

• This is a template based question, DO NOT write the "main" function.

• Your code is judged by an automated system, do not write any additional welcome/greeting messages.

• "Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring

•Additional score will be given for writing optimized code both in terms of memory and execution time.

Entering edit mode

**Question 1:**

`Approach:`

- If String
`X`

is a permutation of String`Y,`

then each frequency of each character in`X`

is the same as`Y`

. - So find the frequency of each character in strings
`A`

and`B,`

and check for which character they are different. Output that.

`PseudoCode:`

```
char findExtraLetter(string A, string B, int N)
{
vector<int> A1(26, 0), B1(26, 0);
for (int i = 0; i < N; i++)
{
A1[int(A[i] - 'a')]++;
B1[int(B[i] - 'a')]++;
}
B1[int(B[N] - 'a')]++;
char ans;
for (int i = 0; i < 26; i++)
{
if (A1[i] != B1[i])
{
ans = char(int(i + 'a'));
break;
}
}
return ans;
}
```

Entering edit mode

- Given a Binary tree. Implement an function to find the sum of leaf nodes at same level and return the product of all the sums.
- 20 >= Height of Binary tree (H) >= 0

- Maintain an heightSum array (
**i***th*value of heightSum array contains the sum of leaf nodes at level).*i* - Do a dfs on the tree with height of the node passed to the dfs function.
- check if the current node is leaf node. If
*Yes*then add the value of that node to**heightSum[**, else dfs to its child node with*height*]*childHeight=height+1* - Now initialize
variable*ans*and iterate over the*= 1**heightSum*array and if the**i***th*height contains a leaf node ( We can check it by keeping a*th**hasLeaf**boolean array, if its true, it means their is a leaf node at**i***height) multiply that ***heightSum [ i ]*** to our ans. - return ans

- Eg: Take below tree as an example with root value 10 and leaf nodes marked in green color. [graph image][1]
- Lets start dfs from root node, We pass root node and height = 0 to dfs.
- we are now at node with value 10. Check whether its a leaf node. Its not a leaf node. Now call dfs on its left and right child with height = prev_height + 1 i.e. 0 + 1 = 1
- left child of 10 i.e. 9 . Check whether its a leaf node. Its not a leaf node. Now call dfs on its left and right child with height = prev_height+1 i.e. 1+1 = 2
- left child of 9 i.e 1. Now this is a leaf node with height 2, we mark
and*hasLeaf [ 2 ] = true*, and heightSum [ 2 ] = 1*heightSum [ 2 ] += value (here 1)* - right child of 9 i.e. 7. Now this is a leaf node with height 2, we mark
and*hasLeaf [ 2 ] = true***heightSum [ 2 ] += value (here 7)**i.e. { 1 + 7 } heightSum [ 2 ] = 8. - right child of 10 i.e. 2 . Now this is a leaf node with height 1, we mark
and*hasLeaf [ 1 ] = true*i.e. { 0 + 2 } heightSum [ 1 ] = 2.*heightSum [ 1 ] += value (here 2)* - dfs ends as no more children are left
- As we are given that the maximum height of tree can be 20. Then we iterate on height from 0 to 20. Initialize
**ans = 1**and whenever we find*hasLeaf [ height ] = true*, we multiply**ans**with**heightSum [ height ]**i.e. - For
*height = 1*,**ans = ans x heightSum [ 1 ]**=>**ans = ans x 2**=>**ans = 2** - For
*height = 2*,**ans = ans x heightSum [ 2 ]**=>**ans = ans x 8**=>**ans = 16** - return ans; { ans = 16 }

- O(N) | N is the number of nodes.

```
void dfs(vector<int> &heightSum,vector<int>&hasLeaf,int height,TreeNode* root){
if(root->left == NULL && root->right == NULL){ // check whether node is a leaf node
hasLeaf[height]=1; // *height* has a leaf node
heightSum[height]+=root->data; // adding value of leaf node to this height
return;
}
dfs(heightSum,vis,height+1,root->left); // dfs on left child
dfs(heightSum,vis,height+1,root->right); // dfs on right child
}
int Solution(TreeNode* Root){
if(Root == NULL) return 0; // returning D=0 if tree is empty
vector<int> heightSum(20,0);
vector<int> hasLeaf(20,0);
dfs(heightSum,hasLeaf,0,Root);
long long int ans=1;
long long int mod=1e9+7;
for(int i=0;i<20;i++){
if(hasLeaf[i]==1)
ans*=heightSum[i];
ans%=mod;
}
return ans;
}
```