Leveling sectors in a circle

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s