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

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.

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;
}
```

Loading Similar Posts