C++, binary search, hopefully a good explanation
IntuitionI wanted to describe what tripped me up on this problem.I stumbled upon this problem because I wanted to practice binary search problems, so I knew goi
# Intuition

I wanted to describe what tripped me up on this problem.

I stumbled upon this problem because I wanted to practice binary search problems, so I knew going in that binary search had to be used somehow.

Initially I thought I could create a function that would create a kind of step function that goes from not possible to possible (ie a step function) and I would just need to find the transition from zero to 1 (which a binary search is great at).

However, after implementing a function that just returned a bool, I saw that it was false for a long time, then true, then false for a long time, so I knew that this wasn't it.

I then looked at the left over message bytes after trying to encode it into p parts and this gave me more hope. With the examples given, it ran from positive to negative (negative meaning we used more message than we actually have available), much better for binary search!

One caveat is that the last message is allowed to have between 1 and `limit-suffix` chars. So if the suffix size of the last part is 7 but we have a limit of 9, we can have a value of -1 (one less than maximum used) and it still be OK. (0 left means all 9-7 = 2 slots used, it is ok to leave one slot unoccupied, but not two. So if it is still valid, the function adjusts the message left over size to 0.

I experimented a bit with the messages and found that the message "this is really a very awesome messag" (note the missing "e") actually has two solutions. One with 9 parts, and one with 14 parts.

Looking at the leftover message lengths, it looked like this (first number is 1 part, the zeros are at 9 and 14 parts):

`32, 28, 24, 20, 16, 12, 8, 4, 0, 7, 5, 3, 1, 0, -3, -5, -7, -9, -11` 

This tripped me up because I can't use binary search in this.

Then I realized that the issue is that I need to look at each number of part digits individually: Find if I have a solution between 1 and 9, then see if I have a solution between 10 and 99, between 100 and 999, etc...

With a constant part number length, the values are always decreasing values, so binary search can be used!
 
The rest is just mechanical coding.

# Complexity
- Time complexity:
- We do a logarithmic (base 10) number of binary searches, each of which does log  message size operations (worst case). Each operation is also logarithmic in regards to the message size.
- I hard coded 10^6 in the outer loop just because (and only requires 6 loop iterations), but it could have used the length of the string as the minimum should be one message for each character. Let's say I used message size instead of 10^6
Then the final time complexity should be O((log message_size)^3)

# Code
```cpp []
class Solution {
public:
    vector<string> splitMessage(string message, int limit) {
        int prev_ten_power = 1;
        while (prev_ten_power < 1000000) {
            int l = prev_ten_power;
            int next_ten_power = prev_ten_power * 10;
            int r = next_ten_power - 1;
            prev_ten_power = next_ten_power;
            while (l <= r) {
                int mid = (r - l) / 2 + l;
                int message_left_over =
                    LeftOverMessage(message.size(), limit, mid);
                if (message_left_over == 0)
                    return CalculateResult(message, limit, mid);
                if (message_left_over > 0) {
                    // we are too far left. Go right.
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return {};
    }

    std::vector<std::string> CalculateResult(std::string_view message,
                                             int limit, int parts) {
        std::vector<std::string> result;
        for (int i = 1; i <= parts; ++i) {
            std::string suffix = "<";
            suffix += std::to_string(i);
            suffix += "/";
            suffix += std::to_string(parts);
            suffix += ">";
            int num_chars = limit - suffix.size();
            std::string s = std::string(message.substr(0, num_chars));
            s += suffix;
            message.remove_prefix(num_chars);
            result.push_back(s);
        }
        return result;
    }

    int LeftOverMessage(int message_size, int limit, int parts) {
        int suffix_size = 0;

        int p = parts;
        while (p > 0) {
            ++suffix_size;
            p = p / 10;
        }
        suffix_size += 4; /// <1/9> (single digit included)

        int prev_ten_power = 1;
        while (parts > 0) {
            int next_ten_power = prev_ten_power * 10;
            int parts_with_digit =
                std::min(next_ten_power - prev_ten_power, parts);
            message_size -= parts_with_digit * (limit - suffix_size);
            parts -= parts_with_digit;
            suffix_size += 1;
            prev_ten_power = next_ten_power;
        }
        suffix_size = suffix_size - 1; // undo

        // The last block is allowed to have less characters, but not zero
        if (message_size < 0 && message_size + limit - suffix_size > 0) {
            return 0;
        }

        return message_size;
    }
};
```
['C++']