no binary search, calculate the number of messages directly
Approach\nCan we use 9 messages to split the original message? If we cannot, can use 99 messages to split the original message?...\nWe only has to try up to 999
# Approach\nCan we use 9 messages to split the original message? If we cannot, can use 99 messages to split the original message?...\nWe only has to try up to 99999 as there\'re only 10000 chars max so max number of messages is 10000. That\'s what function findMessageCountSize() does, which returns the number of digits of the message count.\n\nAfter we get the number of digits, we call findMessageCount() to find out how many exact messages we need. eg. If we find we need 3 digts for the message count, then we calculate how many chars we can send in the first 99 messages. Then the number of rest messages which index has 3 digits can be calculated. That\'s what findMessageCount() does.\n\n\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<string> splitMessage(string message, int limit) {\n        int len = findMessageCountSize(message.size(), limit);\n        vector<string> res;\n        if (len == -1) {\n            return res;\n        }\n        int count = findMessageCount(message.size(), limit, len);\n        int start = 0;\n        int messageCount = 1;\n        string suffix = "/"+to_string(count)+">";\n        while (start < message.size()) {\n            string msgSuffix = "<"+to_string(messageCount)+suffix;\n            int length = limit - msgSuffix.size();\n            res.push_back(message.substr(start, length)+msgSuffix);\n            start += length;\n            ++messageCount;\n        }\n        return res;        \n    }\n\n    int findMessageCountSize(int mesLen, int limit) {\n        for (int i = 1; i <=5; ++i) {\n            int cost = 0;\n            for (int j = 0; j < i; ++j) {\n                cost += pow(10, j)*9*(i+4+j);\n            }\n            int count = ceil((mesLen+cost)/double(limit));\n            if (count <= pow(10, i)-1) {\n                return i;\n            }\n        }\n        return -1;\n    }\n    int findMessageCount(int mesLen, int limit, int countLen) {\n        int chars = 0;\n        for (int i = 1; i < countLen; ++i) {\n            chars += pow(10, i-1)*9*(limit-(countLen+i+3));\n        }\n        int count = ceil((mesLen - chars) / (limit - (3.0+countLen+countLen)));\n        return pow(10, countLen-1) + count - 1;\n    }\n};\n```
['C++']