Count the number of beautiful numbers

Question

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

Answer 1

My guess is that there may be even an analytical solution.

But we can survive with a little bit brute forcing. We only need to concentrate on the first 6 digits of the number.

We calculate the number of different sums for all possible numbers that can be generated with 6 digits.

Having digit values between 0 and 12, there are 6 * 12 + 1 (for the 0) sums possible. The same sums may appear several times.

Example for 3 digit numbers

0 + 0 + 1 = 1
0 + 1 + 0 = 1
1 + 0 + 0 = 1

So, for the sum 1, we would have 3 different combinations. The count of sums can be calculated for all possible combination of digits.

The requirement for the beautiful number is that left digits are same as right digits.

For the above example it would mean

001 001
001 010
001 100

010 001
010 010
010 100

100 001
100 010
100 100

So, logically 3*3 = 9 combinations.

The same can be done for each other count of sums.

This leads to the following design:

• Calculate the count of sums for each possible combination of 6 digits with 13 values
• Square all the sums
• Add the squares
• Multiply by 13 for the middle value

One of many possible implementations:

#include <iostream>
#include <array>
#include <numeric>

constexpr size_t NumberOfDigits = 6u;
constexpr size_t NumberSystem = 13u;

using NumberData = std::array<unsigned int, NumberOfDigits>;
using Counter = std::array<unsigned int, NumberOfDigits * (NumberSystem-1) + 1>;

// Small helper class for handling numbers based on an arbitrary numbering system
struct Number {
    NumberData data{};

    // Increase by one. The old school way
    void operator++() {
        int index{ NumberOfDigits - 1 };
        unsigned int carry = 0;
        do {
            const unsigned int sum = data[index] + 1 + carry;
            carry = sum / NumberSystem;

            data[index] = sum % NumberSystem;

            --index;
        } while (index >= 0 and carry);
    }
    // Calculate the sum of all digits
    unsigned int sum() { return std::accumulate(data.begin(), data.end(),0); }
};

int main() {

    // How many calculations do we need to do, e,g, 6^13
    size_t numberOfCalculations{ 1 };
    for (size_t k = 0; k < NumberOfDigits; ++k)
        numberOfCalculations *= NumberSystem;

    // Here we will count equal sums
    Counter counter{};
    Number number{};

    // Calculate sum of digits for all possible combination of digits
    for (size_t k = 0; k < numberOfCalculations; ++k) {
        counter[number.sum()]++;
        ++number;
    }
    // No get the sum of squares of all sums
    unsigned long long sum{};
    for (const auto& count : counter) {
        sum += (static_cast<unsigned long long>(count) * static_cast<unsigned long long>(count));

    }
    // And times 13 for the middle digit
    std::cout << (sum * NumberSystem) << '\n';
    return 0;
}

Answer 2

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.

Answer 3

Create a matrix of integers 6 rows 13*6=78 columns. Row i col j holds the count of numbers with i+1 digits whose digits sum to j.

Initialize row 1 to having a 1 in columns 0 - 12. Each successive row is filled by adding the counts for the prior row shifted 0 to 12 spaces.

At the end you have the counts of all possible digit sums.

Take the sum of the squares of the digit counts, and multiply by 13 for the possible center values.

Answer 4

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.