Find the largest multiple of 3, given an array of n digits

#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