Problem
An array of size N is given. The array contains digits from 0 to 9.
Generate the maximum number using the digits in the array such that it is divisible by 2, 3 and 5
input: {1,8,7,6,0}, output: 8760
input: {7,7,7,6,}, output : none(-1)
Solution
1. Sort the array.
2. If the last digit is not 0, return -1;
3. If the length of array is 1, return 0 if arr[0] = 0, otherwise return -1
4. Compute the sum of array
5. Compute the residual of sum modulo 3
6, Compute the number count of 1 and 2 after num % 3
7. Select the strategy to remove one or two smallest digits
8. Compute the result
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Generate the maximum number using the digits in the array such that it is divisible by 2, 3 and 5
Created Date : 25-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <iterator>
using namespace std;
long long GenerateMaxNumDivisible235(int* arr, int len)
{
if(len == 1) return arr[0] == 0 ? 0 : -1;
sort(arr, arr + len, [](int i, int j)->bool{return i > j;});
int sum = accumulate(arr, arr + len, 0);
if(arr[len - 1] != 0) return -1;
int newLen = len;
int residual = sum % 3;
if(residual != 0){
int modulo1 = count_if(arr, arr + len, [](int i)->bool{ return i % 3 == 1; });
int modulo2 = count_if(arr, arr + len, [](int i)->bool{ return i % 3 == 2; });
int replaceMod;
int cnt;
if(modulo2 == 0){
replaceMod = 1;
cnt = residual;
}
else if(modulo1 == 0){
replaceMod = 2;
cnt = (residual == 1) ? 2 : 1;
}
else {
replaceMod = residual;
cnt = 1;
}
newLen -= cnt;
for(int i = len - 2; i >= 0; --i){
if(arr[i] % 3 == replaceMod){
arr[i] = 0;
cnt --;
if(cnt == 0) break;
}
}
}
sort(arr, arr + len, [](int i, int j)->bool{return i > j;});
long long retVal = 0;
for(int i = 0; i < newLen - 1; ++ i){
retVal += arr[i];
retVal *= 10;
}
return retVal;
}
void DoTest(int* arr, int len)
{
cout << "The array is " << endl;
copy(arr, arr + len, ostream_iterator<int>(cout, " "));
cout << endl;
long long num = GenerateMaxNumDivisible235(arr, len);
if(num != -1){
cout << "The max num is " << num << endl;
}
else{
cout << "Cannot find a num divisible by 2 3 5." << endl;
}
cout << "--------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[20] = {0};
DoTest(arr, 1);
// 18760 --> 8760
arr[0] = 1;
arr[1] = 8;
arr[2] = 7;
arr[3] = 6;
arr[4] = 0;
DoTest(arr, 5);
// 7776 --> -1
arr[0] = 7;
arr[1] = 7;
arr[2] = 7;
arr[3] = 6;
DoTest(arr, 4);
arr[0] = 1;
DoTest(arr, 1);
arr[0] = 2;
DoTest(arr, 1);
arr[0] = 1;
arr[1] = 0;
DoTest(arr, 2);
arr[0] = 2;
arr[1] = 0;
DoTest(arr, 2);
arr[0] = 3;
arr[1] = 0;
DoTest(arr, 2);
arr[0] = 3;
arr[1] = 3;
DoTest(arr, 2);
arr[0] = 1;
arr[1] = 0;
arr[2] = 0;
DoTest(arr, 3);
arr[0] = 1;
arr[1] = 1;
arr[2] = 0;
DoTest(arr, 3);
arr[0] = 1;
arr[1] = 3;
arr[2] = 0;
DoTest(arr, 3);
arr[0] = 2;
arr[1] = 5;
arr[2] = 0;
DoTest(arr, 3);
arr[0] = 1;
arr[1] = 5;
arr[2] = 0;
DoTest(arr, 3);
arr[0] = 2;
arr[1] = 5;
arr[2] = 0;
DoTest(arr, 3);
arr[0] = 1;
arr[1] = 5;
arr[2] = 0;
DoTest(arr, 3);
arr[0] = 1;
arr[1] = 5;
arr[2] = 0;
arr[3] = 4;
DoTest(arr, 4);
// 74420 --> 720
arr[0] = 7;
arr[1] = 4;
arr[2] = 0;
arr[3] = 4;
arr[4] = 2;
DoTest(arr, 5);
// 55550 --> 5550
arr[0] = 5;
arr[1] = 5;
arr[2] = 5;
arr[3] = 5;
arr[4] = 0;
DoTest(arr, 5);
// 4440 --> -4440
arr[0] = 4;
arr[1] = 4;
arr[2] = 4;
arr[3] = 0;
DoTest(arr, 4);
// 2420 --> -420
arr[0] = 2;
arr[1] = 4;
arr[2] = 2;
arr[3] = 0;
DoTest(arr, 4);
return 0;
}
Output
The array is
0
The max num is 0
--------------------
The array is
1 8 7 6 0
The max num is 8760
--------------------
The array is
7 7 7 6
Cannot find a num divisible by 2 3 5.
--------------------
The array is
1
Cannot find a num divisible by 2 3 5.
--------------------
The array is
2
Cannot find a num divisible by 2 3 5.
--------------------
The array is
1 0
The max num is 0
--------------------
The array is
2 0
The max num is 0
--------------------
The array is
3 0
The max num is 30
--------------------
The array is
3 3
Cannot find a num divisible by 2 3 5.
--------------------
The array is
1 0 0
The max num is 0
--------------------
The array is
1 1 0
The max num is 0
--------------------
The array is
1 3 0
The max num is 30
--------------------
The array is
2 5 0
The max num is 0
--------------------
The array is
1 5 0
The max num is 510
--------------------
The array is
2 5 0
The max num is 0
--------------------
The array is
1 5 0
The max num is 510
--------------------
The array is
1 5 0 4
The max num is 540
--------------------
The array is
7 4 0 4 2
The max num is 7440
--------------------
The array is
5 5 5 5 0
The max num is 5550
--------------------
The array is
4 4 4 0
The max num is 4440
--------------------
The array is
2 4 2 0
The max num is 420
--------------------
Press any key to continue . . .