Advanced Application Engineer Analyst

You are given a sorted array A consisting of N integers. Your task is to find the magic index in the given array.

Note :

1. A magic index in an array A[0 ... N - 1] is defined to be an index i such that A[i] = i.
2. The elements in the array can be negative.
3. The elements in the array can be repeated multiple times.
4. There can be more than one magic index in an array.

Peter Parker (Spider-Man) want to time travel to save Tony Stark.

So Peter came to Doctor Strange for help. Doctor strange told Peter that he would help him if he can solve Strange’s problem. Peter accepts the challenge.

Doctor Strange gave Peter a grid having ‘N’ strings of size ‘M’ each. Then he gave Peter a string ‘S’. The task is to count the total number of paths in grid starting from any coordinate in the grid by moving only in left, right, up and down directions such that the string formed by characters in the path will be equal to ‘S’. Also, visiting a coordinate twice in a path is not allowed.

As Peter wants to bring Tony back as soon as possible, he called you for help.

The fate of Tony and Peter lies in your hand.

You have been given a Binary Tree where the value of each node is either 0 or 1. Your task is to return the same Binary Tree but all of its subtrees that don't contain a 1 have been removed.

Note :

A subtree of a node X is X, plus every node that is a descendant of X.

For Example :

Look at the below example to see a Binary Tree pruning.
Input: [1, 1, 1, 0, 1, 0, 1, 0, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

Output: [1, 1, 1, -1, 1, -1, 1, -1, -1, -1, -1]

For example, the input for the tree depicted in the below image would be :

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

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree.

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1