Java | Binary Search
Intuition\nOnce the number of parts is decided, the problem can be solved easily.\nTo determine the number of parts, first decide the length this number has, an
# Intuition\nOnce the number of parts is decided, the problem can be solved easily.\nTo determine the number of parts, first decide the length this number has, and run binary search over all numbers of this length to find the minimum number.\n\n# Complexity\n- Time complexity:\n$$O(n)$$, given $$1 <= \\text{message.length} <= 10^{4}$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\n    public String[] splitMessage(String message, int limit) {\n        \n        int n = message.length();\n        int l = 1, r = 9;\n\n        while( !isValid(n, limit, r) ) r = r*10 + 9;\n        l = (int)Math.pow( 10, (int)Math.log10(r) );\n\n        while( l<r ){\n            int mid = (l+r)/2;\n            if( isValid(n, limit, mid) ) r=mid;\n            else l = mid+1;\n        }\n        if(l>n) return new String[0];\n\n        String[] res = new String[l];\n        int i=1;\n        int curr = 0;\n        int nsfx = (int)Math.log10(l)+1 + 3;\n        while(i<=l) {\n            int totsfx = nsfx + (int)Math.log10(i)+1;\n            int nmsg = limit - totsfx;\n            String s = message.substring( curr, Math.min(curr+nmsg, n) );\n            res[i-1] = s+"<"+String.valueOf(i)+"/"+String.valueOf(l)+">";\n            curr += nmsg;\n            i++;\n        }\n        return res;\n\n    }\n\n    private boolean isValid( int len, int limit, int num ) {\n        int totsuffix = ((int)Math.log10(num)+1 + 3) * num;\n        int curr = num;\n        for(int nd=4; nd>=1; nd--) {\n            int ln = (int)Math.pow(10, nd-1);\n            if( curr>=ln ) {\n                totsuffix += nd*(curr-ln+1);\n                curr = ln-1;\n            }\n        }\n\n        int nmsg = limit*num - totsuffix;\n        return nmsg >= len;\n    }\n\n}\n```
['Java']