## Yahoo Interview Question

Software Engineers**Country:**United States

Its mentioned that "every rotation of the array". So, sorting the array and calculating PEMAN will not give the correct result. Correct me if I am wrong.

It is mentioned "for every rotation of the array", so sorting the array and calculating PMEAN should not give correct result always. correct me if I am wrong.

Solution in C++:

```
#include <vector>
int pmean(const std::vector<int> &V)
{
int n = V.size();
int i;
int sum = 0;
int pmean = 0;
int best = 0;
for (i = 0; i < n; ++i) {
sum += V[i];
}
for (i = 0; i < n; ++i) {
pmean += V[i] * (i+1);
}
best = pmean;
for (i = 0; i < (n-1); ++i) {
pmean -= sum;
pmean += V[i] * n;
if (pmean > best) {
best = pmean;
}
}
return best;
}
```

def pmean(array):

sum = 0

for n in range(len(array)):

sum += array[n] * n+1

return sum

def max_pmean(array):

if len(array) == []:

return 0

elif len(array) == 1:

return array[0]

else:

max_p = pmean(array)

for i in range(len(array)):

missing_i_array = array[0:i] + array[i+1:]

p_mean_missing_i_array = max_pmean(missing_i_array)

temp_pmean = p_mean_missing_i_array + len(array)*array[i]

if temp_pmean > max_p:

max_p = temp_pmean

last_number = array[i]

return max_p

print max_pmean([10,20,30])

Use Pmean1 and then use the fact that as you rotate left

each value moves to one smaller location.

This means you are multiplying that

number with one less than prev location.

For eg

for PMEAN1 : 10 was multiplied by 3

for PMEAN2 : 10 is multiplied by 2

for PMEAN3 : 10 is multiplied by 1

This means for each successive rotation: you subtract PMEAN by 10.

you do the same for all entries except for the first. As the first moves to the last location

so you multiply that by (index).

Illustratively:

PMEAN1 = 0 + 1*20 + 2*30 + 3*10 = 110

PMEAN2 = 110 + (3-1)*20 - 30 - 10 = 110

and so on...

C++ implementation

```
#include <vector>
size_t MaxSumOfElementsTimeIndicesViaRotation(const std::vector<size_t> input)
{
size_t fPrev = 0;
size_t sum = 0;
size_t index = 1;
for (auto x : input) {
fPrev += x*index;
sum += x;
++index;
}
size_t maxVal = fPrev;
const size_t SizeOfInput = input.size();
size_t fCur;
for (index = 1; index < SizeOfInput; ++index) {
fCur = fPrev + input[index - 1] * SizeOfInput - sum;
if (fCur > maxVal) {
maxVal = fCur;
}
fPrev = fCur;
}
return maxVal;
}
```

See the sub-problem deduction:cpluspluslearning-petert.blogspot.co.uk/2015/02/data-structure-and-algorithm-max-sum-of.html

Test:

```
#include <cassert>
void TestCases()
{
{
std::vector<size_t> input = { 1, 2, 3, 4, 5, 6, 7 };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}
{
std::vector<size_t> input = { 2, 3, 4, 5, 6, 7, 1 };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}
{
std::vector<size_t> input = { 3, 4, 5, 6, 7, 1, 2 };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}
{
std::vector<size_t> input = { 4, 5, 6, 7, 1, 2, 3 };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}
{
std::vector<size_t> input = { 5, 6, 7, 1, 2, 3, 4 };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}
{
std::vector<size_t> input = { 6, 7, 1, 2, 3, 4, 5 };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}
{
std::vector<size_t> input = { 7, 1, 2, 3, 4, 5, 6, };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}
}
```

```
def pmeans_alt(array_test):
loops = len(array_test)
pnt = 0;
means = []
while pnt < loops:
total = 0
for i,x in enumerate(array_test):
total += (i+1)*x
means.append(total)
print array_test
##now pop and insert at the beginning
final_element = array_test[loops-1]
array_test.pop()
array_test.insert(0,final_element);
pnt += 1
print "total means added",len(means)
max_mean = 0
for x in means:
print x
if x > max_mean:
max_mean = x
print "max mean: ",max_mean
```

```
def pmeans_alt(array_test):
loops = len(array_test)
pnt = 0;
means = []
while pnt < loops:
total = 0
for i,x in enumerate(array_test):
total += (i+1)*x
means.append(total)
print array_test
##now pop and insert at the beginning
final_element = array_test[loops-1]
array_test.pop()
array_test.insert(0,final_element);
pnt += 1
print "total means added",len(means)
max_mean = 0
for x in means:
print x
if x > max_mean:
max_mean = x
print "max mean: ",max_mean
```

```
public static int getPMean(int nums[]){
int maxPMeanValue = Integer.MIN_VALUE;
for(int i =0; i<nums.length;i++){
int pmean = calcuateMean(nums, i);
if(pmean > maxPMeanValue){
maxPMeanValue = pmean;
}
}
return maxPMeanValue;
}
private static int calcuateMean(int nums[], int startIndex){
int sum = 0;
int n = nums.length;
for(int i =0; i<nums.length;i++){
sum = sum + (nums[startIndex] *(i+1));
startIndex = (startIndex+1)%n;
}
return sum;
}
```

}

- Vir Pratap Uttam April 12, 2015