# Ugly_Numbers challenge

Here's the challenge:

Once upon a time in a strange situation, people called a number ugly if it was divisible by any of the one-digit primes ($2$, $3$, $5$ or $7$). Thus, $14$ is ugly, but $13$ is fine. $39$ is ugly, but $121$ is not. Note that $0$ is ugly. Also note that negative numbers can also be ugly: $-14$ and $-39$ are examples of such numbers.

One day on your free time, you are gazing at a string of digits, something like:

123456


You are amused by how many possibilities there are if you are allowed to insert plus or minus signs between the digits. For example you can make:

1 + 234 - 5 + 6 = 236


which is ugly. Or:

123 + 4 - 56 = 71


which is not ugly.

It is easy to count the number of different ways you can play with the digits: Between each two adjacent digits you may choose put a plus sign, a minus sign, or nothing. Therefore, if you start with N digits there are $3^{N-1}$ expressions you can make. Note that it is fine to have leading zeros for a number. If the string is '01023', then '01023', '0+1-02+3' and '01-023' are legal expressions.

Your task is simple: Among the $3^{N-1}$ expressions, count how many of them evaluate to an ugly number.

Input Sample:

Your program should accept as its first argument a path to a filename. Each line in this file is one test case. Each test case will be a single line containing a non-empty string of decimal digits. The string in each test case will be non-empty and will contain only characters '$0$' through '$9$'. Each string is no more than 13 characters long. E.g.

1
9
011
12345


Output Sample:

Print out the number of expressions that evaluate to an ugly number for each test case, each one on a new line. E.g.

0
1
6
64


Is the code understandable? How can it be improved?

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <bitset>
#include <cmath>
#include <sstream>
#include <numeric>
using namespace std;

const int one_prime[4] = {2,3,5,7};
bool isUgly(int number)
{
if(number == 0) return true;
for(int i=0; i<4; i++)
{
if(number % one_prime[i] == 0)
return true;
}
return false;
}
vector<string> makeBinary(size_t perm)
{
vector<string> output;
size_t eraseLength = bitset<32>(perm).to_string().find_first_of('1');
while(perm--)
{
string binary = bitset<32>(perm).to_string();
binary.erase(binary.begin(), binary.begin() + eraseLength);
output.push_back(binary);
}
return output;
}
vector<string> getPartitions(const vector<string>& binarySet, const string& input)
{
vector<string> binOperator;
for(size_t idx = 0; idx < binarySet.size(); idx++)
{
string str(input);
for(size_t pos = 0,opCount = 1; (pos = binarySet[idx].find('1',pos) )!= string::npos; pos++,opCount++)
str.insert(pos+opCount, " ");
binOperator.push_back(str);
}
return binOperator;
}
vector<int> makePartitionsToNum(const string& str)
{
vector<int> numbers;
stringstream split(str);
string buf;
while(split >> buf)
{
int value;
istringstream toNum(buf);
toNum >> value;
numbers.push_back(value);
}
return numbers;
}
{
if(numbers.size() == 1)
{
}
else if(numbers.size() == 2)
{
}
else
{
size_t possiblePerm = pow(2,static_cast<double>(numbers.size() - 1) );
vector<string> binSet(makeBinary(possiblePerm));
for(size_t i=0; i<binSet.size(); i++)
{
int result = numbers[0];
for(size_t binCounter=1; binCounter<numbers.size(); binCounter++)
{
if(binSet[i][binCounter - 1] == '1')
{
result += numbers[binCounter];
}
else
{
result -= numbers[binCounter];
}
}
}
}
}
{
size_t UglyNumberCount = 0;
{
{
UglyNumberCount++;
}
}
cout << UglyNumberCount << endl;
}
int main(int argc, char *argv[])
{
ifstream stream(argv[1]);
string input;
while (getline(stream, input))
{
size_t perm = pow(2,static_cast<double>(input.size() - 1) );
vector<string> binarySet(makeBinary(perm));
vector<string> partitionSet (getPartitions(binarySet, input));
for(size_t idx=0; idx<partitionSet.size(); idx++)
{
vector<int> numbers(makePartitionsToNum(partitionSet[idx]));
}
}
return 0;
}

• Hello guys i try to edit the post but i constantly get errors for wrong code formating so i would ask if someone edit it for me, this is the edit i try to do : pastebin.com/9meTRuKe Jul 24, 2015 at 7:35

• Your isUgly function can be improved greatly.

For example, if the input begins with 0, 2, 4, 6, 8, a number is divisible by 2, hence an important execution time can be skipped by this trick:

bool isUgly(int number)
{
if ((number&1)==0) return true;
//...
}


Therefore, with the divisibility by 5 (the case a number begins by 5 or 10), you can expel larger ranges of multiples of 5 from the division process. Just check out occurrence of the sequences 101 in a binary-formatted number.

• Why are you checking the divisibility of any number by 2 after summing up (or subtracting) an even number of odd sub-values?

For instance, (3+51)+(-7+11) or (3+5-1)+(-7+1+1) is always even, which means it's divisible by 2 because the sum of an even number of odd numbers is always even.

int odd_digits=0,even_digits=strlen(argv[1]), j=0,borderdigit=0;

for (int i=0;i<strlen(argv[1]);i++)

if((atoi(argv[1][i])&1)==1)
{
if (i==strlen(argv[1])-1) borderdigit+=1;
if (i==0) borderdigit-=2;
odd_digits++;
}

even_digits-=odd_digits;


Any number xyz....XYZT... where all letters are odd and last numbers are necessarily even (odd_digits = 7, borderdigit = -2)

or

xyz....XYZT, where the last numbers are necessarily odd (borderdigit = 1)

or

xyz....XYZT, where the last and first numbers are necessarily odd (borderdigit = -1)

would be manipulated automatically without the pain of calculating each combinatory readynumber, according to many variants:

• Number of odd sub-numbers
• Number of odd inner digits of any odd sub-number
• Number of even digits
• Last digit in the number
• First digit in the number

• If number of odd digits $n$ = odd_digits is even

• If an odd digit is not the last in whole number (borderdigit=/=(+/-)1)

• UglyNumberCount is multiplied by $(4^{0/2}\binom{0}{n}+4^{2/2}\binom{2}{n}+...+4^{n/2}\binom{n}{n})$
• If an odd digit is last one in whole number (borderdigit==(+/-)1)

• UglyNumberCount *= $(4^{0/2}\binom{0}{(n-1)}+4^{2/2}\binom{2}{(n-1)}+...+4^{(n-2)/2}\binom{(n-2)}{(n-1)})$
• If number of odd digits $n$ is odd

• If an odd digit is not last one in whole number (borderdigit=/=(+/-)1)

• UglyNumberCount is multiplied by $(4^{0/2}\binom{0}{n}+4^{2/2}\binom{2}{n}+...+4^{(n-1)/2}\binom{n-1}{n})$
• If an odd digit is last one in whole number (borderdigit==(+/-)1)

• UglyNumberCount *= $(4^{0/2}\binom{0}{(n-1)}+4^{2/2}\binom{2}{(n-1)}+...+4^{(n-1)/2}\binom{(n-1)}{(n-1)})$
• About even digits multiplication is done by $2^k$ instead of $4^k$

Number of digits is fix $n$ = even_digits

• If an even digit is not last one in whole number (borderdigit==(+/-)1)

• UglyNumberCount is multiplied by $(2^{0}\binom{0}{n}+2^{1}\binom{1}{n}+...+2^{n}\binom{n}{n})=3^{n}$
• If an even digit is last one in whole number (borderdigit=/=(+/-)1)

• UglyNumberCount *= $(2^{0}\binom{0}{n-1}+2^{1}\binom{1}{n-1}+...+2^{n-1}\binom{n-1}{n-1})=3^{n-1}$

• Note: The same procedure can be applied with multiples of 5. Just replace (even, odd) selections by (5 or 0, x) where x is any digit else.
• Note 2: divisibility-check by 3 and 7 doesn't encompass combinations where both two previous cases occur because they are already ugly, I wont claim to have any magical trick but until here a large number of possibilities would have been got rid of.
• Comments are not for extended discussion; this conversation has been moved to chat. Jul 24, 2015 at 13:46