1
00:00:00,610 --> 00:00:01,690
Welcome back.

2
00:00:01,690 --> 00:00:05,080
Now let's discuss how we can solve this problem.

3
00:00:05,080 --> 00:00:07,270
Now for this let's take an example.

4
00:00:07,270 --> 00:00:08,830
Let's take this example itself.

5
00:00:08,830 --> 00:00:09,130
Right.

6
00:00:09,130 --> 00:00:10,300
We have one two.

7
00:00:10,330 --> 00:00:13,390
Then the next element is an array three comma four.

8
00:00:13,390 --> 00:00:15,310
And the next element is an array.

9
00:00:15,310 --> 00:00:19,780
And that array again has another array as its element which is this two over here.

10
00:00:19,780 --> 00:00:20,980
So this is the input.

11
00:00:20,980 --> 00:00:23,170
Now we need to write a function.

12
00:00:23,170 --> 00:00:25,450
So let's call this function some power.

13
00:00:25,450 --> 00:00:25,840
All right.

14
00:00:25,840 --> 00:00:27,670
So we have function some power.

15
00:00:27,670 --> 00:00:30,100
And we will be passing the array to this function.

16
00:00:30,100 --> 00:00:30,400
Right.

17
00:00:30,400 --> 00:00:32,440
So let's pass the array over here.

18
00:00:32,440 --> 00:00:36,430
And then initially as we have seen this level over here is one.

19
00:00:36,430 --> 00:00:36,790
Right.

20
00:00:36,790 --> 00:00:43,090
So the power to which we will raise these elements one plus two plus this equivalent value plus this

21
00:00:43,090 --> 00:00:44,440
equivalent value is going to be one.

22
00:00:44,440 --> 00:00:44,710
Right.

23
00:00:44,710 --> 00:00:46,090
So the initial power is one.

24
00:00:46,090 --> 00:00:47,590
So let's pass that also.

25
00:00:47,590 --> 00:00:48,190
All right.

26
00:00:48,220 --> 00:00:52,840
Now once we have the array what is the output that is requested from us.

27
00:00:52,840 --> 00:00:56,440
It's the sum of the elements to the power which we have passed over here.

28
00:00:56,440 --> 00:00:56,770
Right.

29
00:00:56,770 --> 00:01:02,470
So we will be returning the sum of the elements and we will raise that sum to the power which is passed

30
00:01:02,470 --> 00:01:02,980
over here.

31
00:01:02,980 --> 00:01:04,900
So this is a basic understanding.

32
00:01:04,900 --> 00:01:05,290
Right.

33
00:01:05,290 --> 00:01:08,830
So this is something that we have understood because we have understood the question.

34
00:01:08,830 --> 00:01:13,030
Now let's proceed and see how we can solve this problem actually.

35
00:01:13,030 --> 00:01:17,350
So we will be having this input array and we will need to traverse it.

36
00:01:17,350 --> 00:01:17,710
Right.

37
00:01:17,710 --> 00:01:20,440
So let's say we are traversing it in this direction.

38
00:01:20,440 --> 00:01:26,380
Now what we will do while traversing this array, we will take each element and we will check whether

39
00:01:26,380 --> 00:01:29,950
this element is an integer or it's whether it's an array.

40
00:01:30,580 --> 00:01:31,060
All right.

41
00:01:31,060 --> 00:01:33,910
Now if it is an integer then it's very easy.

42
00:01:33,910 --> 00:01:35,530
Just add it to the sum right.

43
00:01:35,530 --> 00:01:37,570
So at the beginning we will have some.

44
00:01:37,570 --> 00:01:40,210
Let's say we initialize some to zero.

45
00:01:41,090 --> 00:01:43,280
So sum is equal to zero right.

46
00:01:43,280 --> 00:01:46,130
So let's just write that over here initially.

47
00:01:46,130 --> 00:01:51,410
And then if we found that that particular element is an integer then we just add it to sum.

48
00:01:51,410 --> 00:01:53,420
So that's not difficult right.

49
00:01:53,420 --> 00:01:55,160
So we can just add it to sum.

50
00:01:55,160 --> 00:02:00,800
Now if we see that the element is not an integer but an array, then what do we do.

51
00:02:00,830 --> 00:02:03,410
We need to get its equivalent value right.

52
00:02:03,410 --> 00:02:09,290
And you can see that based on the way this is constructed, we can get the equivalent value of this

53
00:02:09,290 --> 00:02:13,130
array by passing this array to another sum function.

54
00:02:13,130 --> 00:02:13,400
Right.

55
00:02:13,400 --> 00:02:20,510
So we can recursively call the same function sum pow, which is this function which we are writing over

56
00:02:20,510 --> 00:02:21,410
here itself.

57
00:02:21,410 --> 00:02:25,340
And we will be passing the particular array which we got over here.

58
00:02:25,340 --> 00:02:25,730
Right.

59
00:02:25,730 --> 00:02:27,740
So this array would be passed over here.

60
00:02:27,740 --> 00:02:30,110
And the power will be incremented by one.

61
00:02:30,110 --> 00:02:32,690
Because let's say we got this element over here.

62
00:02:32,690 --> 00:02:39,920
At this point we will be passing three comma four as the array to the recursive call of the same function.

63
00:02:39,920 --> 00:02:44,630
And the power will be one plus one, which is two because this is in level two.

64
00:02:44,720 --> 00:02:45,170
Right.

65
00:02:45,170 --> 00:02:46,790
So these brackets are level two.

66
00:02:47,330 --> 00:02:49,340
And then again the same thing happens.

67
00:02:49,340 --> 00:02:50,660
We check the next element.

68
00:02:50,660 --> 00:02:52,760
If it's an integer we add it to the sum.

69
00:02:52,760 --> 00:02:56,030
If not we will again recursively call the function right.

70
00:02:56,030 --> 00:02:59,000
So what happens when we recursively call the function over here.

71
00:02:59,000 --> 00:03:03,380
What happens is it will find whatever is going to be returned over here.

72
00:03:03,380 --> 00:03:04,100
It will come back.

73
00:03:04,100 --> 00:03:04,550
Right.

74
00:03:04,550 --> 00:03:07,520
And once it comes back we can just add it to sum.

75
00:03:07,520 --> 00:03:08,060
All right.

76
00:03:08,060 --> 00:03:10,280
So let's walk through this example over here.

77
00:03:10,280 --> 00:03:12,950
Now let's say initially sum is equal to zero.

78
00:03:12,950 --> 00:03:13,220
All right.

79
00:03:13,220 --> 00:03:15,020
So we have sum equal to zero.

80
00:03:15,020 --> 00:03:20,270
And now we are going to check this logic over here which we have written right.

81
00:03:20,270 --> 00:03:22,640
So if it's an integer we add it to sum.

82
00:03:22,640 --> 00:03:26,000
If it's an array we will recursively call the same function.

83
00:03:26,000 --> 00:03:27,290
So let's walk through it.

84
00:03:27,290 --> 00:03:30,200
Now we take the first element which is equal to one.

85
00:03:30,200 --> 00:03:32,030
And we see that it's an integer.

86
00:03:32,030 --> 00:03:33,320
So we add it to the sum.

87
00:03:33,320 --> 00:03:35,870
So zero plus one is equal to one.

88
00:03:35,870 --> 00:03:38,120
So the sum at this point is equal to one.

89
00:03:38,120 --> 00:03:39,860
Again we proceed further.

90
00:03:39,860 --> 00:03:42,530
We look at the next element which is two over here.

91
00:03:43,190 --> 00:03:45,230
And we see that it's an integer.

92
00:03:45,230 --> 00:03:46,580
So we add it to the sum.

93
00:03:46,580 --> 00:03:48,050
So we do one plus two.

94
00:03:48,080 --> 00:03:48,770
All right.

95
00:03:48,770 --> 00:03:51,380
Now we take the next element which is an array right.

96
00:03:51,380 --> 00:03:53,030
So we see that it's an array.

97
00:03:53,030 --> 00:03:57,200
So we call the sum power function recursively.

98
00:03:57,200 --> 00:04:00,170
And we pass the array three comma four.

99
00:04:00,170 --> 00:04:02,990
And the power at this point is equal to two.

100
00:04:02,990 --> 00:04:03,410
Right.

101
00:04:03,410 --> 00:04:05,420
So again what will this call do.

102
00:04:05,420 --> 00:04:05,780
Right.

103
00:04:05,780 --> 00:04:09,200
When we are inside this call we are going to repeat this same logic right.

104
00:04:09,200 --> 00:04:11,000
So we will take the first element.

105
00:04:11,000 --> 00:04:13,880
Sum is now zero and we will take the first element.

106
00:04:13,880 --> 00:04:16,040
And at this point this is an integer right.

107
00:04:16,040 --> 00:04:19,430
So we add 3 to 0 and we get the sum as three.

108
00:04:19,460 --> 00:04:23,000
Now we move we move the pointer and we check the next element.

109
00:04:23,000 --> 00:04:24,920
We again see that's an integer.

110
00:04:24,920 --> 00:04:26,360
So we add it to the sum.

111
00:04:26,360 --> 00:04:28,880
So three plus four is equal to seven.

112
00:04:28,880 --> 00:04:35,660
And once we have the sum we just return the sum of elements which at this point is seven raised to the

113
00:04:35,660 --> 00:04:36,380
power right.

114
00:04:36,380 --> 00:04:39,230
And the power we have passed over here is equal to two.

115
00:04:39,260 --> 00:04:41,990
So we will be returning seven to the power.

116
00:04:41,990 --> 00:04:42,170
Two.

117
00:04:42,200 --> 00:04:42,530
Right.

118
00:04:42,530 --> 00:04:48,800
So this function over here, what it does this call what it does is it will return three plus four to

119
00:04:48,800 --> 00:04:51,500
the power two which is equal to 49.

120
00:04:51,500 --> 00:04:51,830
Right.

121
00:04:51,830 --> 00:04:53,240
So this will be returned.

122
00:04:53,240 --> 00:04:55,550
And we are back again in the first call.

123
00:04:55,550 --> 00:04:55,730
Right.

124
00:04:55,730 --> 00:04:59,240
So at this point we have one plus two plus 49.

125
00:04:59,240 --> 00:05:03,260
So we are we have done with this element this element and this element.

126
00:05:03,260 --> 00:05:05,690
Again we move to the next element which is this one.

127
00:05:05,690 --> 00:05:07,760
Over here we see it's an array.

128
00:05:07,760 --> 00:05:11,510
And hence we recursively call the sum power function.

129
00:05:11,510 --> 00:05:13,610
So let's write that over here some power.

130
00:05:13,610 --> 00:05:16,970
And we are passing these two right.

131
00:05:16,970 --> 00:05:20,240
So we are passing this element over here right.

132
00:05:20,240 --> 00:05:22,250
So that's the element over here.

133
00:05:22,250 --> 00:05:25,400
And the level was one initially.

134
00:05:25,400 --> 00:05:28,340
So we increment that level by the power was one.

135
00:05:28,340 --> 00:05:28,610
Right.

136
00:05:28,610 --> 00:05:29,510
So the level was one.

137
00:05:29,510 --> 00:05:30,440
So power was one.

138
00:05:30,440 --> 00:05:33,380
So we increment that and we change it to two.

139
00:05:33,380 --> 00:05:35,570
And we recursively call this function.

140
00:05:35,570 --> 00:05:38,300
Now once we are inside the function what will happen.

141
00:05:38,300 --> 00:05:40,670
The array now which we have is this over here right.

142
00:05:40,670 --> 00:05:42,800
This one over here we again check.

143
00:05:42,800 --> 00:05:44,600
We take the first element we see.

144
00:05:44,600 --> 00:05:45,410
It's not an integer.

145
00:05:45,410 --> 00:05:46,490
This is again an array.

146
00:05:46,490 --> 00:05:46,820
Right.

147
00:05:46,820 --> 00:05:48,020
So what happens.

148
00:05:48,020 --> 00:05:51,410
We will again come over here and recursively call some power.

149
00:05:51,440 --> 00:05:51,770
Right.

150
00:05:51,770 --> 00:05:55,610
So after this call again we will recursively call some power.

151
00:05:55,610 --> 00:05:59,600
And at this point we will just pass array two which is this element over here.

152
00:05:59,600 --> 00:05:59,900
Right.

153
00:05:59,900 --> 00:06:03,470
And the power will be again incremented from 2 to 3.

154
00:06:03,470 --> 00:06:04,070
Right.

155
00:06:04,700 --> 00:06:06,620
Again we are inside the function over here.

156
00:06:06,620 --> 00:06:08,360
Now sum is again zero.

157
00:06:08,360 --> 00:06:13,400
Now when we look at the elements we see that the element over here is just two which is an integer.

158
00:06:13,400 --> 00:06:13,730
Right.

159
00:06:13,730 --> 00:06:17,450
So we just add 2 to 0 and we get the sum as two.

160
00:06:17,480 --> 00:06:21,080
So sum of elements at this point is equal to two and the power is three.

161
00:06:21,080 --> 00:06:25,460
So we return two to the power three which is equal to eight right.

162
00:06:25,460 --> 00:06:27,110
So this eight is returned.

163
00:06:27,110 --> 00:06:27,650
All right.

164
00:06:27,650 --> 00:06:28,850
So we found eight.

165
00:06:28,850 --> 00:06:30,380
So it's returning back.

166
00:06:30,380 --> 00:06:31,430
It's returning back.

167
00:06:31,430 --> 00:06:33,830
And we will put eight over here.

168
00:06:33,830 --> 00:06:37,430
Right again in this call we got this as eight.

169
00:06:37,430 --> 00:06:40,430
Now we can just calculate this over here right sum.

170
00:06:40,870 --> 00:06:43,600
And the array is just eight and the power is two.

171
00:06:43,630 --> 00:06:44,020
Right.

172
00:06:44,020 --> 00:06:48,250
So to calculate this again we come inside the function over here sum is zero.

173
00:06:48,280 --> 00:06:51,100
We look at the first element which is just an integer.

174
00:06:51,100 --> 00:06:52,480
So we add it to sum.

175
00:06:52,480 --> 00:06:54,550
So zero plus eight is equal to eight.

176
00:06:54,550 --> 00:06:57,340
And then we raise it to the power which is equal to two.

177
00:06:57,370 --> 00:07:00,220
So eight to the power two gives us 64.

178
00:07:00,220 --> 00:07:01,750
So that's what's returned over here right.

179
00:07:01,750 --> 00:07:04,090
Sum of elements is eight and power is two.

180
00:07:04,120 --> 00:07:09,580
So eight square which is 64 is returned back right when we call this.

181
00:07:09,580 --> 00:07:12,340
So the return function gives us six.

182
00:07:12,340 --> 00:07:15,010
The return statement over here returns 64.

183
00:07:15,010 --> 00:07:16,840
So over here we have 64.

184
00:07:16,840 --> 00:07:19,750
And now we just add that to the existing sum.

185
00:07:19,750 --> 00:07:22,540
The sum so far was one plus two plus 49.

186
00:07:22,540 --> 00:07:24,580
And we add 64 to that.

187
00:07:24,580 --> 00:07:27,040
And we get the answer as 116.

188
00:07:27,040 --> 00:07:31,390
And again when we return this is the sum of elements which is 116.

189
00:07:31,390 --> 00:07:35,710
And we raise this to the power one which is again 116 and we return it.

190
00:07:35,710 --> 00:07:38,830
And this is how we are going to solve this question.

191
00:07:39,310 --> 00:07:41,170
So let's quickly recap.

192
00:07:41,170 --> 00:07:44,650
We are going to solve this using recursive function calls.

193
00:07:44,650 --> 00:07:47,290
So we traverse the given array input array.

194
00:07:47,290 --> 00:07:50,980
And we are going to check whether each element is an integer or an array.

195
00:07:50,980 --> 00:07:53,590
If it's an integer, we will just add it to the sum.

196
00:07:53,590 --> 00:07:59,230
If it's an array, we will recursively call the same function and pass this particular array, and we

197
00:07:59,230 --> 00:08:02,650
will increment the power and we will pass that over here.

198
00:08:02,650 --> 00:08:05,740
And once it is returned, like for example, it returned over here.

199
00:08:05,740 --> 00:08:08,680
49 again we will look at the next element.

200
00:08:08,680 --> 00:08:13,840
Again we recursively call the sum function till it returned the value 64.

201
00:08:13,840 --> 00:08:15,670
And that is again added to the sum.

202
00:08:15,670 --> 00:08:18,970
And that gives us the final sum which is 116.

203
00:08:18,970 --> 00:08:23,860
And that would be raised just to the power one, because at this level the the level is one.

204
00:08:23,860 --> 00:08:25,090
So the power is just one.

205
00:08:25,090 --> 00:08:27,190
And we have our solution.

206
00:08:27,190 --> 00:08:27,790
All right.

207
00:08:27,790 --> 00:08:34,630
Now let me just clear this up and let's quickly look at the time and space complexity of this solution.

208
00:08:35,690 --> 00:08:41,540
Now, when it comes to the time complexity, you can see that we have to traverse this array once,

209
00:08:41,540 --> 00:08:41,870
right?

210
00:08:41,870 --> 00:08:44,780
So the time complexity over here is O of n.

211
00:08:44,780 --> 00:08:48,950
But remember n over here is not 1234 right.

212
00:08:48,950 --> 00:08:52,010
The initial array which is given to us has four elements.

213
00:08:52,010 --> 00:08:53,900
But that is not this n over here.

214
00:08:53,900 --> 00:09:00,890
This n is the total number of elements in the main array and all subarrays because we have to traverse

215
00:09:00,890 --> 00:09:02,570
through all of these elements, right.

216
00:09:02,570 --> 00:09:04,790
So in this case what is the total.

217
00:09:04,790 --> 00:09:10,160
What is n in the example which is given to us we have one two right.

218
00:09:10,160 --> 00:09:11,360
This is one this is two.

219
00:09:11,390 --> 00:09:13,400
This element over here is three.

220
00:09:13,490 --> 00:09:15,860
And inside this we have two integers.

221
00:09:15,860 --> 00:09:16,730
So this is four.

222
00:09:16,760 --> 00:09:17,690
This is five.

223
00:09:17,720 --> 00:09:19,430
Now this element over here.

224
00:09:19,430 --> 00:09:20,630
This one over here.

225
00:09:22,100 --> 00:09:22,790
Is six.

226
00:09:22,790 --> 00:09:24,500
So this is one element.

227
00:09:24,530 --> 00:09:27,740
Now inside this element we have this array right.

228
00:09:27,740 --> 00:09:28,970
So this is seven.

229
00:09:28,970 --> 00:09:30,890
And inside this we have one element.

230
00:09:30,890 --> 00:09:31,910
So this is eight.

231
00:09:31,910 --> 00:09:36,230
So in this case in the example which we have over here n is equal to eight.

232
00:09:36,230 --> 00:09:38,870
So the time complexity is o of n.

233
00:09:38,870 --> 00:09:44,510
And in this example n is equal to eight and n over here it's important.

234
00:09:44,510 --> 00:09:48,050
Remember in the interview you have to explain what you mean with n.

235
00:09:48,050 --> 00:09:52,850
So in this case n is the total number of elements in the main array.

236
00:09:52,850 --> 00:09:57,140
And all subarrays which we have seen over here is equal to eight.

237
00:09:57,470 --> 00:09:57,860
All right.

238
00:09:57,860 --> 00:10:00,020
So the time complexity is O of n.

239
00:10:00,020 --> 00:10:03,080
Now let's look at the space complexity of this solution.

240
00:10:04,120 --> 00:10:09,880
Now the space complexity will be the number of recursive calls in the call stack.

241
00:10:09,910 --> 00:10:14,590
The maximum number of recursive calls in the call stack at any point of time.

242
00:10:14,590 --> 00:10:14,860
Right.

243
00:10:14,860 --> 00:10:17,260
Because we are not using any extra space.

244
00:10:17,470 --> 00:10:18,430
Apart from that.

245
00:10:18,430 --> 00:10:22,300
So we are going to use space because this is a recursive solution.

246
00:10:22,300 --> 00:10:29,110
So the space complexity over here is O of D where d is the maximum depth of the call stack.

247
00:10:29,110 --> 00:10:29,440
Right.

248
00:10:29,440 --> 00:10:35,950
So this is the maximum depth of the call stack, which is the maximum number of recursive calls at a

249
00:10:35,950 --> 00:10:37,030
particular given time.

250
00:10:37,030 --> 00:10:38,320
So it should be at once.

251
00:10:38,320 --> 00:10:40,900
So in this case we have three levels right.

252
00:10:40,900 --> 00:10:41,980
So this is level one.

253
00:10:41,980 --> 00:10:43,420
This is level two.

254
00:10:43,420 --> 00:10:45,910
And over here we have level two and level three.

255
00:10:45,910 --> 00:10:48,280
So the maximum depth will occur over here.

256
00:10:48,280 --> 00:10:50,140
And that would be three right.

257
00:10:50,140 --> 00:10:54,430
So in this example which we saw D over here will be equal to three.

258
00:10:54,430 --> 00:11:01,000
So the space complexity of this solution is O of d where d is the maximum depth of the call stack.