#include <stdio.h>

#include <vector>

#include <algorithm>

using namespace std;

typedef vector<int> Container;

/*

* Algorithm:

* a . Sort the array

* b . find the sum of the array

* c. find rem = sum % 3

* c1. if rem == 0 return 0;

* else

* find first digit whose remainder == rem

* if found

* erase it from the array and return 0

* else

* find first two digits whose remainder != 0 and != rem

* if found

* erase them and return 0

* else

* return -1

*/

/**

* Return:

* 0 success

* -1 failure

*/

int largestDivBy3(Container &v) {

sort(v.begin(), v.end());

int s = accumulate(v.begin(), v.end(), 0),

rem = s % 3,

tmp;

if (rem == 0) return 0;

int pos1 = -1,

pos2 = -1;

for (auto i = v.begin(); i != v.end(); ++i ) {

tmp = *i % 3;

if (tmp == rem) {

v.erase(i);

return 0;

} else if(tmp) {

if (pos1 == -1) {

pos1 = i - v.begin();

} else if(pos2 == -1) {

pos2 = i - v.begin();

}

}

}

if (pos2 != -1) {

v.erase(v.begin() + pos1);

v.erase(v.begin() + pos2 - 1);

return 0;

}

return -1;

}

int main() {

Container v = {9, 7, 6, 6, 6 };

int n = largestDivBy3(v);

if (n == 0) {

for(auto i = v.rbegin(); i < v.rend(); ++i) {

printf("%d", *i);

}

printf("\n");

} else {

printf("Not possible");

}

}

Advertisements