#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <assert.h>
#include <ctime>
#include <limits.h>
using namespace std;
class Solution
{
public:
vector<int> constructLargestNumberOf3(const vector<int> &arr) {
int n = arr.size();
vector<int> result;
if (n == 0) return result;
int digitSum = getDigitSum(arr);
if (digitSum % 3 == 0) {
result = arr;
sort(result.begin(), result.end(), customizedCmp);
return result;
}
if (digitSum % 3 == 1) {
int num1_1 = -1, num1_2 = -1;
searchSmallestWithRemainder(arr, num1_1, num1_2, 1);
int num2_1 = -1, num2_2 = -1;
searchSmallestWithRemainder(arr, num2_1, num2_2, 2);
if (num1_1 >= 0 && num2_2 < 0) {
copyDataWithException(result, arr, num1_1, -1);
}
else if (num1_1 < 0 && num2_2 >= 0) {
copyDataWithException(result, arr, num2_1, num2_2);
}
else if (num1_1 >= 0 && num2_2 >= 0) {
string res1 = constructNumber(0, num1_1);
string res2 = constructNumber(num2_1, num2_2);
string res3 = constructNumber(num2_2, num2_1);
if (res1.size() > res2.size() && res1.size() > res3.size())
copyDataWithException(result, arr, num2_1, num2_2);
else if (res2.size() > res1.size() || res3.size() > res1.size())
copyDataWithException(result, arr, num1_1, -1);
else if (res1 >= res2 && res1 >= res3)
copyDataWithException(result, arr, num2_1, num2_2);
else
copyDataWithException(result, arr, num1_1, -1);
}
}
else {
int num1_1 = -1, num1_2 = -1;
searchSmallestWithRemainder(arr, num1_1, num1_2, 1);
int num2_1 = -1, num2_2 = -1;
searchSmallestWithRemainder(arr, num2_1, num2_2, 2);
if (num2_1 >= 0 && num1_2 < 0) {
copyDataWithException(result, arr, num2_1, -1);
}
else if (num2_1 < 0 && num1_2 >= 0) {
copyDataWithException(result, arr, num1_1, num1_2);
}
else if (num2_1 >= 0 && num1_2 >= 0) {
string res1 = constructNumber(0, num2_1);
string res2 = constructNumber(num1_1, num1_2);
string res3 = constructNumber(num1_2, num1_1);
if (res1.size() > res2.size() && res1.size() > res3.size())
copyDataWithException(result, arr, num1_1, num1_2);
else if (res2.size() > res1.size() || res3.size() > res1.size())
copyDataWithException(result, arr, num2_1, -1);
else if (res1 >= res2 && res1 >= res3)
copyDataWithException(result, arr, num1_1, num1_2);
else
copyDataWithException(result, arr, num2_1, -1);
}
}
sort(result.begin(), result.end(), customizedCmp);
return result;
}
private:
int getDigitSum(int n) {
int sum = 0;
int r = 0;
while (n) {
r = n % 10;
n /= 10;
sum += r;
}
return sum;
}
void searchSmallestWithRemainder(const vector<int> &arr, int &res1, int &res2, int target_r) {
int n = arr.size();
res1 = res2 = INT_MAX;
for (int i = 0; i < n; ++i) {
if (arr[i] % 3 != target_r) continue;
if (arr[i] < res1) {
res2 = res1;
res1 = arr[i];
}
else if (arr[i] < res2)
res2 = arr[i];
}
if (res1 == INT_MAX) res1 = -1;
if (res2 == INT_MAX) res2 = -1;
}
void copyDataWithException(vector<int> &dest, const vector<int> &src, int t1, int t2) {
for (int i = 0; i < src.size(); ++i) {
if (src[i] == t1)
t1 = -1;
else if (src[i] == t2)
t2 = -1;
else
dest.push_back(src[i]);
}
}
static string constructNumber(int n1, int n2) {
if (n1 == 0 && n2 == 0) return "0";
int r = 0;
string result;
while (n1) {
r = n1 % 10;
n1 /= 10;
result += '0' + r;
}
int start = 0, end = result.size() - 1;
while (start < end)
swap(result[start++], result[end--]);
start = result.size();
while (n2) {
r = n2 % 10;
n2 /= 10;
result += '0' + r;
}
end = result.size() - 1;
while (start < end)
swap(result[start++], result[end--]);
return result;
}
static bool customizedCmp(const int &n1, const int &n2) {
string res1 = constructNumber(n1, n2);
string res2 = constructNumber(n2, n1);
if (res1.size() > res2.size()) return true;
if (res2.size() > res1.size()) return false;
return res1 > res2;
}
public:
int getDigitSum(const vector<int> &arr) {
int sum = 0;
for (int i = 0; i < arr.size(); ++i)
sum += getDigitSum(arr[i]);
return sum;
}
};
void Output(const vector<int> &arr) {
for (int i = 0; i < arr.size(); ++i)
cout << arr[i] << " ";
cout << endl;
}
void GenerateArray(vector<int> &arr, int n, int MAX_VAL) {
for (int i = 0; i < n; ++i)
arr.push_back(rand() % MAX_VAL + 1);
}
int main()
{
const int MAX_NUM = 600;
const int MAX_TRY = 30;
const int MAX_ARR_SIZE = 30;
vector<int> srcArr;
Solution so;
vector<int> result;
int tryTimes = MAX_TRY;
srand(time(NULL));
while (tryTimes-- > 0) {
srcArr.clear();
GenerateArray(srcArr, rand() % MAX_ARR_SIZE + 1, MAX_NUM);
result = so.constructLargestNumberOf3(srcArr);
assert(so.getDigitSum(result) % 3 == 0);
cout << "Original Array is:" << endl;
Output(srcArr);
cout << "Constructed Maximum Number that is multiple of 3 is:" << endl;
Output(result);
cout << "-------------------------------------------" << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8YXNzZXJ0Lmg+CiNpbmNsdWRlIDxjdGltZT4KI2luY2x1ZGUgPGxpbWl0cy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgU29sdXRpb24KewpwdWJsaWM6CiAgICB2ZWN0b3I8aW50PiBjb25zdHJ1Y3RMYXJnZXN0TnVtYmVyT2YzKGNvbnN0IHZlY3RvcjxpbnQ+ICZhcnIpIHsKICAgICAgICBpbnQgbiA9IGFyci5zaXplKCk7CiAgICAgICAgdmVjdG9yPGludD4gcmVzdWx0OwogICAgICAgIGlmIChuID09IDApIHJldHVybiByZXN1bHQ7CgogICAgICAgIGludCBkaWdpdFN1bSA9IGdldERpZ2l0U3VtKGFycik7CiAgICAgICAgaWYgKGRpZ2l0U3VtICUgMyA9PSAwKSB7CiAgICAgICAgICAgIHJlc3VsdCA9IGFycjsKICAgICAgICAgICAgc29ydChyZXN1bHQuYmVnaW4oKSwgcmVzdWx0LmVuZCgpLCBjdXN0b21pemVkQ21wKTsKICAgICAgICAgICAgcmV0dXJuIHJlc3VsdDsKICAgICAgICB9CgogICAgICAgIGlmIChkaWdpdFN1bSAlIDMgPT0gMSkgewogICAgICAgICAgICBpbnQgbnVtMV8xID0gLTEsIG51bTFfMiA9IC0xOwogICAgICAgICAgICBzZWFyY2hTbWFsbGVzdFdpdGhSZW1haW5kZXIoYXJyLCBudW0xXzEsIG51bTFfMiwgMSk7CiAgICAgICAgICAgIGludCBudW0yXzEgPSAtMSwgbnVtMl8yID0gLTE7CiAgICAgICAgICAgIHNlYXJjaFNtYWxsZXN0V2l0aFJlbWFpbmRlcihhcnIsIG51bTJfMSwgbnVtMl8yLCAyKTsKICAgICAgICAgICAgaWYgKG51bTFfMSA+PSAwICYmIG51bTJfMiA8IDApIHsKICAgICAgICAgICAgICAgIGNvcHlEYXRhV2l0aEV4Y2VwdGlvbihyZXN1bHQsIGFyciwgbnVtMV8xLCAtMSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSBpZiAobnVtMV8xIDwgMCAmJiBudW0yXzIgPj0gMCkgewogICAgICAgICAgICAgICAgY29weURhdGFXaXRoRXhjZXB0aW9uKHJlc3VsdCwgYXJyLCBudW0yXzEsIG51bTJfMik7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSBpZiAobnVtMV8xID49IDAgJiYgbnVtMl8yID49IDApIHsKICAgICAgICAgICAgICAgIHN0cmluZyByZXMxID0gY29uc3RydWN0TnVtYmVyKDAsIG51bTFfMSk7CiAgICAgICAgICAgICAgICBzdHJpbmcgcmVzMiA9IGNvbnN0cnVjdE51bWJlcihudW0yXzEsIG51bTJfMik7CiAgICAgICAgICAgICAgICBzdHJpbmcgcmVzMyA9IGNvbnN0cnVjdE51bWJlcihudW0yXzIsIG51bTJfMSk7CiAgICAgICAgICAgICAgICBpZiAocmVzMS5zaXplKCkgPiByZXMyLnNpemUoKSAmJiByZXMxLnNpemUoKSA+IHJlczMuc2l6ZSgpKQogICAgICAgICAgICAgICAgICAgIGNvcHlEYXRhV2l0aEV4Y2VwdGlvbihyZXN1bHQsIGFyciwgbnVtMl8xLCBudW0yXzIpOwogICAgICAgICAgICAgICAgZWxzZSBpZiAocmVzMi5zaXplKCkgPiByZXMxLnNpemUoKSB8fCByZXMzLnNpemUoKSA+IHJlczEuc2l6ZSgpKQogICAgICAgICAgICAgICAgICAgIGNvcHlEYXRhV2l0aEV4Y2VwdGlvbihyZXN1bHQsIGFyciwgbnVtMV8xLCAtMSk7CiAgICAgICAgICAgICAgICBlbHNlIGlmIChyZXMxID49IHJlczIgJiYgcmVzMSA+PSByZXMzKQogICAgICAgICAgICAgICAgICAgIGNvcHlEYXRhV2l0aEV4Y2VwdGlvbihyZXN1bHQsIGFyciwgbnVtMl8xLCBudW0yXzIpOwogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIGNvcHlEYXRhV2l0aEV4Y2VwdGlvbihyZXN1bHQsIGFyciwgbnVtMV8xLCAtMSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgZWxzZSB7CiAgICAgICAgICAgIGludCBudW0xXzEgPSAtMSwgbnVtMV8yID0gLTE7CiAgICAgICAgICAgIHNlYXJjaFNtYWxsZXN0V2l0aFJlbWFpbmRlcihhcnIsIG51bTFfMSwgbnVtMV8yLCAxKTsKICAgICAgICAgICAgaW50IG51bTJfMSA9IC0xLCBudW0yXzIgPSAtMTsKICAgICAgICAgICAgc2VhcmNoU21hbGxlc3RXaXRoUmVtYWluZGVyKGFyciwgbnVtMl8xLCBudW0yXzIsIDIpOwogICAgICAgICAgICBpZiAobnVtMl8xID49IDAgJiYgbnVtMV8yIDwgMCkgewogICAgICAgICAgICAgICAgY29weURhdGFXaXRoRXhjZXB0aW9uKHJlc3VsdCwgYXJyLCBudW0yXzEsIC0xKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGlmIChudW0yXzEgPCAwICYmIG51bTFfMiA+PSAwKSB7CiAgICAgICAgICAgICAgICBjb3B5RGF0YVdpdGhFeGNlcHRpb24ocmVzdWx0LCBhcnIsIG51bTFfMSwgbnVtMV8yKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGlmIChudW0yXzEgPj0gMCAmJiBudW0xXzIgPj0gMCkgewogICAgICAgICAgICAgICAgc3RyaW5nIHJlczEgPSBjb25zdHJ1Y3ROdW1iZXIoMCwgbnVtMl8xKTsKICAgICAgICAgICAgICAgIHN0cmluZyByZXMyID0gY29uc3RydWN0TnVtYmVyKG51bTFfMSwgbnVtMV8yKTsKICAgICAgICAgICAgICAgIHN0cmluZyByZXMzID0gY29uc3RydWN0TnVtYmVyKG51bTFfMiwgbnVtMV8xKTsKICAgICAgICAgICAgICAgIGlmIChyZXMxLnNpemUoKSA+IHJlczIuc2l6ZSgpICYmIHJlczEuc2l6ZSgpID4gcmVzMy5zaXplKCkpCiAgICAgICAgICAgICAgICAgICAgY29weURhdGFXaXRoRXhjZXB0aW9uKHJlc3VsdCwgYXJyLCBudW0xXzEsIG51bTFfMik7CiAgICAgICAgICAgICAgICBlbHNlIGlmIChyZXMyLnNpemUoKSA+IHJlczEuc2l6ZSgpIHx8IHJlczMuc2l6ZSgpID4gcmVzMS5zaXplKCkpCiAgICAgICAgICAgICAgICAgICAgY29weURhdGFXaXRoRXhjZXB0aW9uKHJlc3VsdCwgYXJyLCBudW0yXzEsIC0xKTsKICAgICAgICAgICAgICAgIGVsc2UgaWYgKHJlczEgPj0gcmVzMiAmJiByZXMxID49IHJlczMpCiAgICAgICAgICAgICAgICAgICAgY29weURhdGFXaXRoRXhjZXB0aW9uKHJlc3VsdCwgYXJyLCBudW0xXzEsIG51bTFfMik7CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgY29weURhdGFXaXRoRXhjZXB0aW9uKHJlc3VsdCwgYXJyLCBudW0yXzEsIC0xKTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgc29ydChyZXN1bHQuYmVnaW4oKSwgcmVzdWx0LmVuZCgpLCBjdXN0b21pemVkQ21wKTsKICAgICAgICByZXR1cm4gcmVzdWx0OwogICAgfQoKcHJpdmF0ZToKICAgIGludCBnZXREaWdpdFN1bShpbnQgbikgewogICAgICAgIGludCBzdW0gPSAwOwogICAgICAgIGludCByID0gMDsKICAgICAgICB3aGlsZSAobikgewogICAgICAgICAgICByID0gbiAlIDEwOwogICAgICAgICAgICBuIC89IDEwOwogICAgICAgICAgICBzdW0gKz0gcjsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHN1bTsKICAgIH0KCiAgICB2b2lkIHNlYXJjaFNtYWxsZXN0V2l0aFJlbWFpbmRlcihjb25zdCB2ZWN0b3I8aW50PiAmYXJyLCBpbnQgJnJlczEsIGludCAmcmVzMiwgaW50IHRhcmdldF9yKSB7CiAgICAgICAgaW50IG4gPSBhcnIuc2l6ZSgpOwogICAgICAgIHJlczEgPSByZXMyID0gSU5UX01BWDsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgewogICAgICAgICAgICBpZiAoYXJyW2ldICUgMyAhPSB0YXJnZXRfcikgY29udGludWU7CgogICAgICAgICAgICBpZiAoYXJyW2ldIDwgcmVzMSkgewogICAgICAgICAgICAgICAgcmVzMiA9IHJlczE7CiAgICAgICAgICAgICAgICByZXMxID0gYXJyW2ldOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYgKGFycltpXSA8IHJlczIpCiAgICAgICAgICAgICAgICByZXMyID0gYXJyW2ldOwogICAgICAgIH0KCiAgICAgICAgaWYgKHJlczEgPT0gSU5UX01BWCkgcmVzMSA9IC0xOwogICAgICAgIGlmIChyZXMyID09IElOVF9NQVgpIHJlczIgPSAtMTsgICAgCiAgICB9CgogICAgdm9pZCBjb3B5RGF0YVdpdGhFeGNlcHRpb24odmVjdG9yPGludD4gJmRlc3QsIGNvbnN0IHZlY3RvcjxpbnQ+ICZzcmMsIGludCB0MSwgaW50IHQyKSB7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzcmMuc2l6ZSgpOyArK2kpIHsKICAgICAgICAgICAgaWYgKHNyY1tpXSA9PSB0MSkKICAgICAgICAgICAgICAgIHQxID0gLTE7CiAgICAgICAgICAgIGVsc2UgaWYgKHNyY1tpXSA9PSB0MikKICAgICAgICAgICAgICAgIHQyID0gLTE7CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIGRlc3QucHVzaF9iYWNrKHNyY1tpXSk7CiAgICAgICAgfSAgICAKICAgIH0KCiAgICBzdGF0aWMgc3RyaW5nIGNvbnN0cnVjdE51bWJlcihpbnQgbjEsIGludCBuMikgewogICAgICAgIGlmIChuMSA9PSAwICYmIG4yID09IDApIHJldHVybiAiMCI7CiAgICAgICAgaW50IHIgPSAwOwogICAgICAgIHN0cmluZyByZXN1bHQ7CiAgICAgICAgd2hpbGUgKG4xKSB7CiAgICAgICAgICAgIHIgPSBuMSAlIDEwOwogICAgICAgICAgICBuMSAvPSAxMDsKICAgICAgICAgICAgcmVzdWx0ICs9ICcwJyArIHI7CiAgICAgICAgfQoKICAgICAgICBpbnQgc3RhcnQgPSAwLCBlbmQgPSByZXN1bHQuc2l6ZSgpIC0gMTsKICAgICAgICB3aGlsZSAoc3RhcnQgPCBlbmQpCiAgICAgICAgICAgIHN3YXAocmVzdWx0W3N0YXJ0KytdLCByZXN1bHRbZW5kLS1dKTsKCiAgICAgICAgc3RhcnQgPSByZXN1bHQuc2l6ZSgpOwogICAgICAgIHdoaWxlIChuMikgewogICAgICAgICAgICByID0gbjIgJSAxMDsKICAgICAgICAgICAgbjIgLz0gMTA7CiAgICAgICAgICAgIHJlc3VsdCArPSAnMCcgKyByOwogICAgICAgIH0KCiAgICAgICAgZW5kID0gcmVzdWx0LnNpemUoKSAtIDE7CiAgICAgICAgd2hpbGUgKHN0YXJ0IDwgZW5kKQogICAgICAgICAgICBzd2FwKHJlc3VsdFtzdGFydCsrXSwgcmVzdWx0W2VuZC0tXSk7CiAgICAgICAgcmV0dXJuIHJlc3VsdDsgICAgCiAgICB9CgogICAgc3RhdGljIGJvb2wgY3VzdG9taXplZENtcChjb25zdCBpbnQgJm4xLCBjb25zdCBpbnQgJm4yKSB7CiAgICAgICAgc3RyaW5nIHJlczEgPSBjb25zdHJ1Y3ROdW1iZXIobjEsIG4yKTsKICAgICAgICBzdHJpbmcgcmVzMiA9IGNvbnN0cnVjdE51bWJlcihuMiwgbjEpOwogICAgICAgIGlmIChyZXMxLnNpemUoKSA+IHJlczIuc2l6ZSgpKSByZXR1cm4gdHJ1ZTsKICAgICAgICBpZiAocmVzMi5zaXplKCkgPiByZXMxLnNpemUoKSkgcmV0dXJuIGZhbHNlOwogICAgICAgIHJldHVybiByZXMxID4gcmVzMjsKICAgIH0KCnB1YmxpYzoKICAgIGludCBnZXREaWdpdFN1bShjb25zdCB2ZWN0b3I8aW50PiAmYXJyKSB7CiAgICAgICAgaW50IHN1bSA9IDA7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBhcnIuc2l6ZSgpOyArK2kpCiAgICAgICAgICAgIHN1bSArPSBnZXREaWdpdFN1bShhcnJbaV0pOwogICAgICAgIHJldHVybiBzdW07CiAgICB9Cn07Cgp2b2lkIE91dHB1dChjb25zdCB2ZWN0b3I8aW50PiAmYXJyKSB7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IGFyci5zaXplKCk7ICsraSkKICAgICAgICBjb3V0IDw8IGFycltpXSA8PCAiICI7CiAgICBjb3V0IDw8IGVuZGw7Cn0KCnZvaWQgR2VuZXJhdGVBcnJheSh2ZWN0b3I8aW50PiAmYXJyLCBpbnQgbiwgaW50IE1BWF9WQUwpIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKQogICAgICAgIGFyci5wdXNoX2JhY2socmFuZCgpICUgTUFYX1ZBTCArIDEpOwp9CgppbnQgbWFpbigpCnsKICAgIGNvbnN0IGludCBNQVhfTlVNID0gNjAwOwogICAgY29uc3QgaW50IE1BWF9UUlkgPSAzMDsKICAgIGNvbnN0IGludCBNQVhfQVJSX1NJWkUgPSAzMDsKICAgIHZlY3RvcjxpbnQ+IHNyY0FycjsKICAgIFNvbHV0aW9uIHNvOwogICAgdmVjdG9yPGludD4gcmVzdWx0OwogICAgaW50IHRyeVRpbWVzID0gTUFYX1RSWTsKCiAgICBzcmFuZCh0aW1lKE5VTEwpKTsKCiAgICB3aGlsZSAodHJ5VGltZXMtLSA+IDApIHsKICAgICAgICBzcmNBcnIuY2xlYXIoKTsKICAgICAgICBHZW5lcmF0ZUFycmF5KHNyY0FyciwgcmFuZCgpICUgTUFYX0FSUl9TSVpFICsgMSwgTUFYX05VTSk7CiAgICAgICAgcmVzdWx0ID0gc28uY29uc3RydWN0TGFyZ2VzdE51bWJlck9mMyhzcmNBcnIpOwogICAgICAgIGFzc2VydChzby5nZXREaWdpdFN1bShyZXN1bHQpICUgMyA9PSAwKTsKCiAgICAgICAgY291dCA8PCAiT3JpZ2luYWwgQXJyYXkgaXM6IiA8PCBlbmRsOwogICAgICAgIE91dHB1dChzcmNBcnIpOwogICAgICAgIGNvdXQgPDwgIkNvbnN0cnVjdGVkIE1heGltdW0gTnVtYmVyIHRoYXQgaXMgbXVsdGlwbGUgb2YgMyBpczoiIDw8IGVuZGw7CiAgICAgICAgT3V0cHV0KHJlc3VsdCk7CiAgICAgICAgY291dCA8PCAiLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSIgPDwgZW5kbDsgICAgCiAgICB9CgoJcmV0dXJuIDA7Cn0=