Page Contents

Want to solve **Find Total Power Amazon OA?, **if yes then this article is for you.

We have research and collected a bundle of questions which was asked in Amazon OA in the year of 2021 and 2022. Today, we are going to see another problem from amazon oa called Find Total Power which was asked in 2022, this questions might be still active in some of the Amazon OA so save all the solutions and lets see how can we solve this problem.

**Find Total Power Amazon OA Solution**

As the ruler of a kingdom, you have an army of wizards at your command.

You are given a **0-indexed** integer array `strength`

, where `strength[i]`

denotes the strength of the `i`

wizard. For a ^{th}**contiguous** group of wizards (i.e. the wizards’ strengths form a **subarray** of `strength`

), the **total strength** is defined as the **product** of the following two values:

- The strength of the
**weakest**wizard in the group. - The
**total**of all the individual strengths of the wizards in the group.

Return *the sum of the total strengths of all contiguous groups of wizards*. Since the answer may be very large, return it

**modulo**

`10`^{9} + 7

.A **subarray** is a contiguous **non-empty** sequence of elements within an array.

**Example 1:**

**Input:** strength = [1,3,1,2]**Output:** 44

**Explanation: **

**The following are all the contiguous groups of wizards:**

- [1] from [1,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1
- [3] from [1,3,1,2] has a total strength of min([3]) * sum([3]) = 3 * 3 = 9
- [1] from [1,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1
- [2] from [1,3,1,2] has a total strength of min([2]) * sum([2]) = 2 * 2 = 4
- [1,3] from [1,3,1,2] has a total strength of min([1,3]) * sum([1,3]) = 1 * 4 = 4
- [3,1] from [1,3,1,2] has a total strength of min([3,1]) * sum([3,1]) = 1 * 4 = 4
- [1,2] from [1,3,1,2] has a total strength of min([1,2]) * sum([1,2]) = 1 * 3 = 3
- [1,3,1] from [1,3,1,2] has a total strength of min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5
- [3,1,2] from [1,3,1,2] has a total strength of min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6
- [1,3,1,2] from [1,3,1,2] has a total strength of min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7

The sum of all the total strengths is 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44.

**Example 2:**

**Input:** strength = [5,4,6]**Output:** 213

**Explanation: **

**The following are all the contiguous groups of wizards:**

- [5] from [5,4,6] has a total strength of min([5]) * sum([5]) = 5 * 5 = 25
- [4] from [5,4,6] has a total strength of min([4]) * sum([4]) = 4 * 4 = 16
- [6] from [5,4,6] has a total strength of min([6]) * sum([6]) = 6 * 6 = 36
- [5,4] from [5,4,6] has a total strength of min([5,4]) * sum([5,4]) = 4 * 9 = 36
- [4,6] from [5,4,6] has a total strength of min([4,6]) * sum([4,6]) = 4 * 10 = 40
- [5,4,6] from [5,4,6] has a total strength of min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60

The sum of all the total strengths is 25 + 16 + 36 + 36 + 40 + 60 = 213.

**Constraints:**

`1 <= strength.length <= 10`

^{5}`1 <= strength[i] <= 10`

^{9}

**Related: Google Online Assessment 2022 Questions List**

**SOLUTION**

**Program:** **Find Total Power Amazon OA Solution** in Python

```
class Solution:
def totalStrength(self, A: List[int]) -> int:
N = len(A)
Q = int(1e9)+7
# monostack
# ple[i] = previous lesser element, than the one at i
st, ple = [], [-1]*N
for i in range(N-1,-1,-1):
while st and A[st[-1]] > A[i]:
ple[st.pop()] = i
st += [i]
# preprocessing
ps = [0] * (N+1) # suffix sum
ds = [0] * (N+1) # suffix sum of suffix sum
dpM = [0] * (N+1) # dpM[i] = sum( suffixMin of A[0..i] )
for z in range(N):
i, j = ~z-1, ~z
ps[i] = A[j] + ps[j]
ds[i] = ps[i] + ds[j]
k = ple[z]
dpM[z] = A[z] * (z-k)
if k != -1: dpM[z] += dpM[k]
def query(L, R): # -> sum( sum(A[k..R]) for k in [L..R] )
if R < L: return 0
diff = ds[L] - ds[R+1]
chop = ps[R+1]
size = R-L+1
return diff - chop * size
ans = 0
dpC = [0] * (N+1)
for i in range(N):
j = ple[i]
x = A[i] * query(j+1, i) % Q
if j == -1: y = 0
else:
s = ps[j+1] - ps[i+1]
y = (dpC[j] + dpM[j] * s) % Q
dpC[i] = (x + y) % Q
ans = (ans + dpC[i]) % Q
return ans
```

**Program:** **Find Total Power Amazon OA Solution** in Java

```
public int totalStrength(int[] A) {
int res = 0, ac = 0, mod = (int)1e9 + 7, n = A.length;
Stack<Integer> stack = new Stack<>();
int[] acc = new int[n + 2];
for (int r = 0; r <= n; ++r) {
int a = r < n ? A[r] : 0;
ac = (ac + a) % mod;
acc[r + 1] = (ac + acc[r]) % mod;
while (!stack.isEmpty() && A[stack.peek()] > a) {
int i = stack.pop();
int l = stack.isEmpty() ? -1 : stack.peek();
long lacc = l < 0 ? acc[i] : acc[i] - acc[l], racc = acc[r] - acc[i];
int ln = i - l, rn = r - i;
res = (int)(res + (racc * ln - lacc * rn) % mod * A[i] % mod) % mod;
}
stack.push(r);
}
return (res + mod) % mod;
}
```

**Program:** **Find Total Power Amazon OA Solution** in C++

```
int totalStrength(vector<int>& A) {
int res = 0, ac = 0, mod = 1e9 + 7, n = A.size();
vector<int> stack = {}, acc(n + 2);
for (int r = 0; r <= n; ++r) {
int a = r < n ? A[r] : 0;
ac = (ac + a) % mod;
acc[r + 1] = (ac + acc[r]) % mod;
while (!stack.empty() && A[stack.back()] > a) {
int i = stack.back(); stack.pop_back();
int l = stack.empty() ? -1 : stack.back();
long lacc = l < 0 ? acc[i] : acc[i] - acc[l], racc = acc[r] - acc[i];
int ln = i - l, rn = r - i;
res = (res + (racc * ln - lacc * rn) % mod * A[i] % mod) % mod;
}
stack.push_back(r);
}
return (res + mod) % mod;
}
```