I found an interesting problem on the Internet:

You need to count the number of beautiful (the sum of the first six numbers is equal to the sum of the last six digits) 13-digit numbers in the 13-digit number system, for example: the number 0055237050A00 is beautiful, since 0 0 5 5 2 3 = 0 5 0 A 0 0, and the number 1234AB988BABA is ugly, since 1 2 3 4 A B! = 8 8 B A B A

I decided to write a class for this, which will store the number in the form converted to an array:

struct Number
{
    explicit Number(size_t number);
    Number& operator    ();
    Number& operator    (int);
    bool is_beautiful() const;
private:
    std::array<uint8_t, 13> m_digits;
};

And then, in a loop, check all the numbers in the interval:

Number number{ 0u };
size_t count_numbers = 0u;
for (size_t i = 0u; i < std::pow(13,13);   i) {
    count_numbers |= (number  ).is_beautiful();
}

But I wanted to ask if this is the optimal solution, maybe you can somehow do without an array using arithmetic? If so, how then can this be implemented?

Maybe there is some special algorithm to solve this problem

CodePudding user response：

Observation1: The 7th digit does not matter if a number is "beautiful", so you can just multiply by the base without need to go over all numbers.

Observation2: Once you set all digit but the last, there is at most one viable solution for beautiful number. Its generalization shows that once some other numbers are created, so are others, so there is definetly room for improvement here.

Observation3: This basically boils down to "How many ways are there to get up to sum X for each number", and iterating over all these options, squaring them (for first 6 digits and for last 6 digits). Now, this is much simpler, as the sum of digits is linear in the number of them, and not exponential.

This can yield us a DP solution to get number of ways to get to each sum:

// stop clause: all zeros, you cannot get otherwise to sum 0.
DP[0, i] = 1  
// There is no way to get to 
DP[x, 0] = 0  | x > 0
DP[x, i] = DP[x-0, i-1]   DP[x-1, i-1]   ... = DP[x-(BASE-1), i-1] 

Once you fill your DP matrix with all options, the solution is:

(DP[0, 6]^2   DP[1, 6]^2   ...   DP[MAX_SUM, 6]^2) * BASE

This is because, for some sum X, you have DP[X,6]^2 ways to create beautiful numbers, DP[X,6] for the first 6 digits, similarly for the 6 last.

Additionally, you need to multiply by BASE, as the number of options of the 7th digit.

CodePudding user response：

While I generally agree with @amit's solution, one thing to notice is the DP solution actually have quite a lot of recursion for OP's particular problem if the result were not cached, which would result to about 350,000,000 call's to DP.

In fact, 350,000,000 is ~70 times greater than 13^6, so you might also consider to do the last step more naively, by first finding the digit sum of each number from 0 to 13^6, and store how many times can you sum to a particular sum, which would be in the range between 0 and 12*6. Then square the times, since there are 6 digits on each side, and times 13 for the 7th digit.