Java - Binary search fails. Simple brute force works like charm.
My inital thought was to find the y in . Basically how many parts. I tried binary search and almost 91/94 test cases passed then. I will my binary search code b
My inital thought was to find the y in <x/y>. Basically how many parts. I tried binary search and almost 91/94 test cases passed then. I will my binary search code below, very stright forward binary search. Later with the failed example, i realized that if we find some number is failing, doesn\'t mean all the number below it are failing which is the basis of binary search, in this question its happeing such a way, a particular number might fail but a number below it will pass, due to len of the numbers in x/y, as the y is a larger, combined with x, the total occupancy will be something like <783/1023>. this itself occupy 11 chars, if say limit is 10, it doesnt work, so our binary search might try something even larger for this problem, but thats the not case, a smaller one like 756/986 might work. Thats with binary search. I just keep all the code and delted the binary search part.\n\nRegarding how to solve it, check if a parituclar y in my code (base vairable) is allowing us to complete the divion, i start from 1 and search linearly, firrst number which works is the best division possible.\n\nExplaining paritiuclar segment of the code to understanbd, once you understand the segment, it is easy to read the code.\n\nint delimit_start = 4 + (int) Math.ceil(Math.log10(base+1));\n\ngiven base, i want to find the delimit starting size, with single number base, it will be <1/9> which is off size 5, without base it is 4, <1/>, so it should 4 + size (len) of the base, Math.log10(base) gives that, but for 10 itself, it will give 1, i add 1 to make it 11, to get 2.\n\nlen -= (Math.min(base, (9 * Math.pow(10, count))) * (limit - delimit_start));\n\nwe need to know for 0 - 9, 10 - 99, 100 - 999, how many len we are dividing successfully, which is  Math.pow(10, count) gives us it is 9, or 90, 900 etc for the group. then limit - delimit_start tells how much remaining for the string, multiplying those two will give how much string len we consued in this part of the calcalation. why math.min in Math.min(base, (9 * Math.pow(10, count)), if remaining string segment is less than 9 or 90, or 900 then we only can take base * (limit - delimit_start).\n\nreturn len <= 0;\n\nif len is covered, we are good.\n\nconstruct method is heavily inspried and kind of repeation of the possible method, just that, we skip 9, 90, 900 in the possible method, here we need to go and construct each string segment. so two loops. outside while is same as possible method, the inside for loop is to construct each string segment.\n\nI know, i didnt explain very well, i fought it hard about which part i should stress in my explation, so gave what i thought might be the burning issue in your head, if you want specific clarificaiton, please let me know in the comments, i will try my best. Thanks.\n# Code\n```\nclass Solution {\n    public String[] splitMessage(String message, int limit) {\n        for(int i=1; i<=message.length(); i++)\n            if(possible(message.length(), i, limit))\n                return construct(message, i, limit);\n\n        return new String[0];\n    }\n\n    public String[] construct(String message, int base, int limit) {\n        String[] ret = new String[base];\n\n        int delimit_start = 4 + (int) Math.ceil(Math.log10(base+1));\n\n        int ret_index = 0, i = 0, count = 0;\n\n        while(i < message.length()) {\n            for(int p = 1; p <=  9 * Math.pow(10, count) && i < message.length(); p++) {\n                \n                int offset = Math.min(message.length(), i + (limit - delimit_start));\n\n                ret[ret_index++] = message.substring(i, offset) + "<" + ret_index + "/" + base + ">";\n                i += (limit - delimit_start);\n            }\n            count++;\n            delimit_start++;\n        }\n\n        return ret;\n    }\n\n    public boolean possible(int len, int base, int limit) {\n        int delimit_start = 4 + (int) Math.ceil(Math.log10(base+1));\n        int count = 0;\n        while(len > 0 && base > 0) {\n            len -= (Math.min(base, (9 * Math.pow(10, count))) * (limit - delimit_start));\n            delimit_start++;\n            base -= (9 * Math.pow(10, count));\n            count++;\n        }\n\n        return len <= 0;\n    }\n}\n```
['Java']