Problem

/*

Algo :

1. Find the maximum element in the array

2. Find the minimum element in the array

while minimum < maximum, choose the pair (min, prev(min)) or (min, next(min)) depending on the value of prev(min) and next(min)

update minimum

*/

#include <iostream>

#include <algorithm>

#include <iterator>

using namespace std;

int numMoves(int a[], int ret[], int n){

int mx = 0, mn = 0;

for (int i = 1; i < n; ++i ) {

if(a[mx] < a[i])

mx = i;

if(a[mn] > a[i])

mn = i;

}

int m = a[mx], prev, next;

while(a[mn] < m) {

prev = mn == 0 ? n - 1 : mn - 1;

next = mn == n - 1 ? 0 : mn + 1;

if(a[prev] <= a[next]) {

ret[prev]++;

a[prev]++;

a[mn]++;

if(a[prev] > m) return 0;

}else {

ret[next]++;

a[next]++;

a[mn]++;

if(a[next] > m) return 0;

}

copy(a, a + n, ostream_iterator<int>(cout, " "));

cout<<endl;

mn = min_element(a, a + n) - a;

}

return a[mn] == a[mx];

}

int main() {

int a[6] = {2, 1, 1, 0, 0, 2};

int ret[6] = {0};

int success = numMoves(a, ret, 6);

cout<<"\nOutput: \n";

if(success) {

copy(ret, ret + 6, ostream_iterator<int>(cout, " "));

} else{

fill_n(ostream_iterator<int>(cout, " "), 6, -1);

}

cout<<endl;

return 0;

}

Advertisements