Welcome back.
Now let's discuss how we can solve this problem.
Now for this let's take an example.
Let's take this example itself.
Right.
We have one two.
Then the next element is an array three comma four.
And the next element is an array.
And that array again has another array as its element which is this two over here.
So this is the input.
Now we need to write a function.
So let's call this function some power.
All right.
So we have function some power.
And we will be passing the array to this function.
Right.
So let's pass the array over here.
And then initially as we have seen this level over here is one.
Right.
So the power to which we will raise these elements one plus two plus this equivalent value plus this
equivalent value is going to be one.
Right.
So the initial power is one.
So let's pass that also.
All right.
Now once we have the array what is the output that is requested from us.
It's the sum of the elements to the power which we have passed over here.
Right.
So we will be returning the sum of the elements and we will raise that sum to the power which is passed
over here.
So this is a basic understanding.
Right.
So this is something that we have understood because we have understood the question.
Now let's proceed and see how we can solve this problem actually.
So we will be having this input array and we will need to traverse it.
Right.
So let's say we are traversing it in this direction.
Now what we will do while traversing this array, we will take each element and we will check whether
this element is an integer or it's whether it's an array.
All right.
Now if it is an integer then it's very easy.
Just add it to the sum right.
So at the beginning we will have some.
Let's say we initialize some to zero.
So sum is equal to zero right.
So let's just write that over here initially.
And then if we found that that particular element is an integer then we just add it to sum.
So that's not difficult right.
So we can just add it to sum.
Now if we see that the element is not an integer but an array, then what do we do.
We need to get its equivalent value right.
And you can see that based on the way this is constructed, we can get the equivalent value of this
array by passing this array to another sum function.
Right.
So we can recursively call the same function sum pow, which is this function which we are writing over
here itself.
And we will be passing the particular array which we got over here.
Right.
So this array would be passed over here.
And the power will be incremented by one.
Because let's say we got this element over here.
At this point we will be passing three comma four as the array to the recursive call of the same function.
And the power will be one plus one, which is two because this is in level two.
Right.
So these brackets are level two.
And then again the same thing happens.
We check the next element.
If it's an integer we add it to the sum.
If not we will again recursively call the function right.
So what happens when we recursively call the function over here.
What happens is it will find whatever is going to be returned over here.
It will come back.
Right.
And once it comes back we can just add it to sum.
All right.
So let's walk through this example over here.
Now let's say initially sum is equal to zero.
All right.
So we have sum equal to zero.
And now we are going to check this logic over here which we have written right.
So if it's an integer we add it to sum.
If it's an array we will recursively call the same function.
So let's walk through it.
Now we take the first element which is equal to one.
And we see that it's an integer.
So we add it to the sum.
So zero plus one is equal to one.
So the sum at this point is equal to one.
Again we proceed further.
We look at the next element which is two over here.
And we see that it's an integer.
So we add it to the sum.
So we do one plus two.
All right.
Now we take the next element which is an array right.
So we see that it's an array.
So we call the sum power function recursively.
And we pass the array three comma four.
And the power at this point is equal to two.
Right.
So again what will this call do.
Right.
When we are inside this call we are going to repeat this same logic right.
So we will take the first element.
Sum is now zero and we will take the first element.
And at this point this is an integer right.
So we add 3 to 0 and we get the sum as three.
Now we move we move the pointer and we check the next element.
We again see that's an integer.
So we add it to the sum.
So three plus four is equal to seven.
And once we have the sum we just return the sum of elements which at this point is seven raised to the
power right.
And the power we have passed over here is equal to two.
So we will be returning seven to the power.
Two.
Right.
So this function over here, what it does this call what it does is it will return three plus four to
the power two which is equal to 49.
Right.
So this will be returned.
And we are back again in the first call.
Right.
So at this point we have one plus two plus 49.
So we are we have done with this element this element and this element.
Again we move to the next element which is this one.
Over here we see it's an array.
And hence we recursively call the sum power function.
So let's write that over here some power.
And we are passing these two right.
So we are passing this element over here right.
So that's the element over here.
And the level was one initially.
So we increment that level by the power was one.
Right.
So the level was one.
So power was one.
So we increment that and we change it to two.
And we recursively call this function.
Now once we are inside the function what will happen.
The array now which we have is this over here right.
This one over here we again check.
We take the first element we see.
It's not an integer.
This is again an array.
Right.
So what happens.
We will again come over here and recursively call some power.
Right.
So after this call again we will recursively call some power.
And at this point we will just pass array two which is this element over here.
Right.
And the power will be again incremented from 2 to 3.
Right.
Again we are inside the function over here.
Now sum is again zero.
Now when we look at the elements we see that the element over here is just two which is an integer.
Right.
So we just add 2 to 0 and we get the sum as two.
So sum of elements at this point is equal to two and the power is three.
So we return two to the power three which is equal to eight right.
So this eight is returned.
All right.
So we found eight.
So it's returning back.
It's returning back.
And we will put eight over here.
Right again in this call we got this as eight.
Now we can just calculate this over here right sum.
And the array is just eight and the power is two.
Right.
So to calculate this again we come inside the function over here sum is zero.
We look at the first element which is just an integer.
So we add it to sum.
So zero plus eight is equal to eight.
And then we raise it to the power which is equal to two.
So eight to the power two gives us 64.
So that's what's returned over here right.
Sum of elements is eight and power is two.
So eight square which is 64 is returned back right when we call this.
So the return function gives us six.
The return statement over here returns 64.
So over here we have 64.
And now we just add that to the existing sum.
The sum so far was one plus two plus 49.
And we add 64 to that.
And we get the answer as 116.
And again when we return this is the sum of elements which is 116.
And we raise this to the power one which is again 116 and we return it.
And this is how we are going to solve this question.
So let's quickly recap.
We are going to solve this using recursive function calls.
So we traverse the given array input array.
And we are going to check whether each element is an integer or an array.
If it's an integer, we will just add it to the sum.
If it's an array, we will recursively call the same function and pass this particular array, and we
will increment the power and we will pass that over here.
And once it is returned, like for example, it returned over here.
49 again we will look at the next element.
Again we recursively call the sum function till it returned the value 64.
And that is again added to the sum.
And that gives us the final sum which is 116.
And that would be raised just to the power one, because at this level the the level is one.
So the power is just one.
And we have our solution.
All right.
Now let me just clear this up and let's quickly look at the time and space complexity of this solution.
Now, when it comes to the time complexity, you can see that we have to traverse this array once,
right?
So the time complexity over here is O of n.
But remember n over here is not 1234 right.
The initial array which is given to us has four elements.
But that is not this n over here.
This n is the total number of elements in the main array and all subarrays because we have to traverse
through all of these elements, right.
So in this case what is the total.
What is n in the example which is given to us we have one two right.
This is one this is two.
This element over here is three.
And inside this we have two integers.
So this is four.
This is five.
Now this element over here.
This one over here.
Is six.
So this is one element.
Now inside this element we have this array right.
So this is seven.
And inside this we have one element.
So this is eight.
So in this case in the example which we have over here n is equal to eight.
So the time complexity is o of n.
And in this example n is equal to eight and n over here it's important.
Remember in the interview you have to explain what you mean with n.
So in this case n is the total number of elements in the main array.
And all subarrays which we have seen over here is equal to eight.
All right.
So the time complexity is O of n.
Now let's look at the space complexity of this solution.
Now the space complexity will be the number of recursive calls in the call stack.
The maximum number of recursive calls in the call stack at any point of time.
Right.
Because we are not using any extra space.
Apart from that.
So we are going to use space because this is a recursive solution.
So the space complexity over here is O of D where d is the maximum depth of the call stack.
Right.
So this is the maximum depth of the call stack, which is the maximum number of recursive calls at a
particular given time.
So it should be at once.
So in this case we have three levels right.
So this is level one.
This is level two.
And over here we have level two and level three.
So the maximum depth will occur over here.
And that would be three right.
So in this example which we saw D over here will be equal to three.
So the space complexity of this solution is O of d where d is the maximum depth of the call stack.