Note: I'm not good at my English, and edits is greatly accepted
I have a function that create the greatest number that is divisible by 30 from the user's input in c++. If can't create then return -1 .
Some sample:
input :
2 // how many input numbers
3 0 // input
output:
30
input:
2
3 1
output :
-1
input:
11
4 9 6 0 6 9 4 9 0 6 3
output:
999666300
My apporach is to check if the number is divisible by 3 and 10, because gcd(3, 10) = 1 thus if a number is divisible by 3 and 10 it will divisible by 30.
I first create a function with a string type.
Numbers is lagre, so I think it's best to store all the numbers in a vector<int>, then sorted it form biggest to smallest, because I need to crete the biggest number.
string create30div (vector<int> vecNum)
{
sort(vecNum.begin(), vecNum.end(), greater<int>());
}
Then I first checked if the array has the number 0, because a number divisible by 10 when it has a 0 in the end. I use the find function to check if the vector has a 0 on it, if not then return -1 immedialey.
string create30div (vector<int> vecNum)
{
sort(vecNum.begin(), vecNum.end(), greater<int>());
if (find(vecNum.begin(), vecNum.end(), 0) == vecNum.end())
{
return "-1";
}
}
Else, if the vector has a 0, then I add the total of all the array and first check if the total is divisible by 0, if yes then just put all the number of the vector to a string and return it.
string create30div (vector<int> vecNum)
{
sort(vecNum.begin(), vecNum.end(), greater<int>());
if (find(vecNum.begin(), vecNum.end(), 0) == vecNum.end())
{
return "-1";
}
else
{
if (accumulate(vecNum.begin(), vecNum.end(), 0) % 3 == 0)
{
goto sum;
}
}
sum:
string sum {};
for (auto i : vecNum)
{
sum += to_string(i);
}
return sum;
}
NOTE: I know it's not good when use goto in c++, but I really don't want to write sum all over agian. Do you guys have a better solution than me?
Back to the problem, if the number isn't divisible by 3, there is two case: divide by 3 has the remainder of 1 or remainder of 2
If divide by 3 has the remainder of 1, I first checked the vector in reverse order to see if there are any number that divide by 3 has the remainder of 1, if yes then delete the number and return sum
string create30div (vector<int> vecNum)
{
sort(vecNum.begin(), vecNum.end(), greater<int>());
if (find(vecNum.begin(), vecNum.end(), 0) == vecNum.end())
{
return "-1";
}
else
{
if (accumulate(vecNum.begin(), vecNum.end(), 0) % 3 == 0)
{
goto sum;
}
else if (accumulate(vecNum.begin(), vecNum.end(), 0) % 3 == 1)
{
bool isNumMod1Exist{false};
for (int i = 0; i < vecNum.size(); i++)
{
if (vecNum.at(vecNum.size() - i - 1) % 3 == 1)
{
vecNum.erase(vecNum.end() - i);
isNumMod1Exist = true;
break;
}
}
if (isNumMod1Exist)
{
goto sum;
}
}
sum:
string sum {};
for (auto i : vecNum)
{
sum += to_string(i);
}
return sum;
}
If there aren't, I then check if there are two numbers that divide by 3 has the remainder of 2, if yes then delete all of it, if not then return -1.
string create30div (vector<int> vecNum)
{
sort(vecNum.begin(), vecNum.end(), greater<int>());
if (find(vecNum.begin(), vecNum.end(), 0) == vecNum.end())
{
return "-1";
}
else
{
if (accumulate(vecNum.begin(), vecNum.end(), 0) % 3 == 0)
{
goto sum;
}
else if (accumulate(vecNum.begin(), vecNum.end(), 0) % 3 == 1)
{
bool isNumMod1Exist{false};
for (int i = 0; i < vecNum.size(); i++)
{
if (vecNum.at(vecNum.size() - i - 1) % 3 == 1)
{
vecNum.erase(vecNum.end() - i);
isNumMod1Exist = true;
break;
}
}
if (isNumMod1Exist)
{
goto sum;
}
else
{
int counter{0};
for (int i = 0; i < vecNum.size(); i++)
{
if (vecNum.at(vecNum.size() - i - 1) % 3 == 2)
{
vecNum.erase(vecNum.end() - i);
counter++;
i--;
if (counter >= 2)
break;
}
}
if (counter >= 2)
{
goto sum;
}
else
{
return "-1";
}
}
}
sum:
string sum {};
for (auto i : vecNum)
{
sum += to_string(i);
}
return sum;
}
The same if the whole number divide by 3 has the remainder of 2.
string create30div (vector<int> vecNum)
{
sort(vecNum.begin(), vecNum.end(), greater<int>());
if (find(vecNum.begin(), vecNum.end(), 0) == vecNum.end())
{
return "-1";
}
else
{
if (accumulate(vecNum.begin(), vecNum.end(), 0) % 3 == 0)
{
goto sum;
}
else if (accumulate(vecNum.begin(), vecNum.end(), 0) % 3 == 1)
{
bool isNumMod1Exist{false};
for (int i = 0; i < vecNum.size(); i++)
{
if (vecNum.at(vecNum.size() - i - 1) % 3 == 1)
{
vecNum.erase(vecNum.end() - i);
isNumMod1Exist = true;
break;
}
}
if (isNumMod1Exist)
{
goto sum;
}
else
{
int counter{0};
for (int i = 0; i < vecNum.size(); i++)
{
if (vecNum.at(vecNum.size() - i - 1) % 3 == 2)
{
vecNum.erase(vecNum.end() - i);
counter++;
i--;
if (counter >= 2)
break;
}
}
if (counter >= 2)
{
goto sum;
}
else
{
return "-1";
}
}
}
else
{
bool isNumMod2Exist{false};
for (int i = 0; i < vecNum.size(); i++)
{
if (vecNum.at(vecNum.size() - i - 1) % 3 == 2)
{
vecNum.erase(vecNum.end() - i);
isNumMod2Exist = true;
break;
}
}
if (isNumMod2Exist)
{
goto sum;
}
else
{
int counter{0};
for (int i = 0; i < vecNum.size(); i++)
{
if (vecNum.at(vecNum.size() - i - 1) % 3 == 1)
{
vecNum.erase(vecNum.end() - i);
counter++;
i--;
break;
}
}
if (counter >= 2)
{
goto sum;
}
else
{
return "-1";
}
}
}
}
sum:
string sum {};
for (auto i : vecNum)
{
sum += to_string(i);
}
return sum;
}
And the driver code.
int main()
{
int n;
cin >> n;
vector<int> vecNum;
for (int i = 1; i <= n; i++)
{
int inputVec;
cin >> inputVec;
vecNum.push_back(inputVec);
}
cout << create30div(vecNum);
}
But I have a problem that this program produce unexpected relsut. For example:
input:
11
4 9 6 0 6 9 4 9 0 6 3
It outputs:
-1
Why?
p/s: I know this post is much longer than it should be, but I just want to let you know what I'm thinking while doing this program.
full code:
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
using namespace std;
string create30div (vector<int> vecNum)
{
sort(vecNum.begin(), vecNum.end(), greater<int>());
if (find(vecNum.begin(), vecNum.end(), 0) == vecNum.end())
{
return "-1";
}
else
{
if (accumulate(vecNum.begin(), vecNum.end(), 0) % 3 == 0)
{
goto sum;
}
else if (accumulate(vecNum.begin(), vecNum.end(), 0) % 3 == 1)
{
bool isNumMod1Exist{false};
for (int i = 0; i < vecNum.size(); i++)
{
if (vecNum.at(vecNum.size() - i - 1) % 3 == 1)
{
vecNum.erase(vecNum.end() - i);
isNumMod1Exist = true;
break;
}
}
if (isNumMod1Exist)
{
goto sum;
}
else
{
int counter{0};
for (int i = 0; i < vecNum.size(); i++)
{
if (vecNum.at(vecNum.size() - i - 1) % 3 == 2)
{
vecNum.erase(vecNum.end() - i);
counter++;
i--;
if (counter >= 2)
break;
}
}
if (counter >= 2)
{
goto sum;
}
else
{
return "-1";
}
}
}
else
{
bool isNumMod2Exist{false};
for (int i = 0; i < vecNum.size(); i++)
{
if (vecNum.at(vecNum.size() - i - 1) % 3 == 2)
{
vecNum.erase(vecNum.end() - i);
isNumMod2Exist = true;
break;
}
}
if (isNumMod2Exist)
{
goto sum;
}
else
{
int counter{0};
for (int i = 0; i < vecNum.size(); i++)
{
if (vecNum.at(vecNum.size() - i - 1) % 3 == 1)
{
vecNum.erase(vecNum.end() - i);
counter++;
i--;
break;
}
}
if (counter >= 2)
{
goto sum;
}
else
{
return "-1";
}
}
}
}
sum:
string sum {};
for (auto i : vecNum)
{
sum += to_string(i);
}
return sum;
}
int main()
{
int n;
cin >> n;
vector<int> vecNum;
for (int i = 1; i <= n; i++)
{
int inputVec;
cin >> inputVec;
vecNum.push_back(inputVec);
}
cout << create30div(vecNum);
}
Aucun commentaire:
Enregistrer un commentaire