# divide a range of numbers into groups of 10, 100, 1000, 10000 and so on

Posted on

Problem

Given a start and end of a range as string, for example:

``````String start = "1230000";
String end   = "1285999";
``````

Generate the shortest list possible with prefixes that include the whole range,
so that for any number from the given range there is a list elemnet which can be used as a prefix. For above example the list would contain:

`````` 123,124,125,126,127,1280,1281,1282,1283,1284,1285
``````

Explanation

The length of the strings may vary (6 – 12) but `start.length()` and `end.length()` are always equal.
The above range can be manually divided into the sub ranges:

``````    //1230000 - 1239999
//1240000 - 1249999
//1250000 - 1259999
//1260000 - 1269999
//1270000 - 1279999
//1280000 - 1289999 this range is not completly included so make the ranges smaller with a factor 10
//1280000 - 1280999
//1281000 - 1281999
//1282000 - 1282999
//1283000 - 1283999
//1284000 - 1284999
//1285000 - 1285999
``````

By storing the common substring of each start and end number of the subranges one can easliy validiate that any given number from the range starts with 123,124,125,126,127,1280,1281,1282,1283,1284 or 1285.

Here is a very naive but working solution to print the prefixes:

``````public static void main(String[] args) {
String start = "1230000";
String end   = "1285999";

while(start.charAt(start.length()-1) == '0' && end.charAt(start.length()-1) == '9'){
start = start.substring(0,start.length()-1);
end = end.substring(0,end.length()-1);
}

long st = Long.parseLong(start);
long en = Long.parseLong(end);
for(long i = st; i <= en; ){
if(i % 1000 == 0 && i + 999 <= en){
System.out.println(i/1000);
i = i + 1000;
}
else if(i % 100 == 0 && i + 99 <= en){
System.out.println(i/100);
i = i + 100;
}
else if(i % 10 == 0 && i + 9 <= en){
System.out.println(i/10);
i = i + 10;
}
else {
System.out.println(i);
i = i + 1;
}
}
}
``````

For some not so nice ranges like the above I have to extend my for loop:

``````public static void main(String[] args) {
String start = "1279995";
String end   = "1285999";

while(start.charAt(start.length()-1) == '0' && end.charAt(start.length()-1) == '9'){
start = start.substring(0,start.length()-1);
end = end.substring(0,end.length()-1);
}

long st = Long.parseLong(start);
long en = Long.parseLong(end);
for(long i = st; i <= en; ){
if(i % 1000000 == 0 && i + 999999 <= en){
System.out.println(i/1000000);
i = i + 1000000;
}
else if(i % 100000 == 0 && i + 99999 <= en){
System.out.println(i/100000);
i = i + 100000;
}
else if(i % 10000 == 0 && i + 9999 <= en){
System.out.println(i/10000);
i = i + 10000;
}
else if(i % 1000 == 0 && i + 999 <= en){
System.out.println(i/1000);
i = i + 1000;
}
else if(i % 100 == 0 && i + 99 <= en){
System.out.println(i/100);
i = i + 100;
}
else if(i % 10 == 0 && i + 9 <= en){
System.out.println(i/10);
i = i + 10;
}
else {
System.out.println(i);
i = i + 1;
}
}
}
``````

Which I found not very nice. Any ideas how to optimise my approach or do some one have another approach (I am open to everything, Regex, streams, recursion .. )?

Solution

Even the “extended version” does not handle the cases where `start` and `end` have more than 6 trailing zeros in common. Instead of hard-coding those ranges and a long `if/else if/...` statement you can determine the largest fitting range dynamically in a loop:

``````for (long i = st; i <= en; ) {
// Determine `range` as largest power of 10 with `i % range == 0`
// and `i + range - 1 <= en`:
int range = 1;
while (range <= i && i % range == 0 && i + range - 1 <= en) {
range *= 10;
}
range /= 10;

System.out.println(i / range);
i += range;
}
``````

Removing common zeros/nines is more efficiently done in integer arithmetic instead of string manipulation:

``````while (st % 10 == 0 && en % 10 == 9) {
st /= 10;
en /= 10;
}
``````

I would move the computation from `main()` into a separate function and separate it from the I/O. That increases the clarity of the program and allows to add test cases more easily. In a comment you said that you need the result as `List<String>`:

``````public static List<String> computePrefixes(long start, long end) {
List<String> prefixes = new ArrayList<String>();

while (start % 10 == 0 && end % 10 == 9) {
start /= 10;
end /= 10;
}

for (long i = start; i <= end; ) {
// Determine `range` as largest power of 10 with `i % range == 0`
// and `i + range - 1 <= en`:
int range = 1;
while (range <= i && i % range == 0 && i + range - 1 <= end) {
range *= 10;
}
range /= 10;

i += range;
}

return prefixes;
}

public static void main(String[] args) {
String start = "1230000";
String end   = "1285999";

long st = Long.parseLong(start);
long en = Long.parseLong(end);
List<String> prefixes = computePrefixes(st, en);
System.out.println(prefixes);
}
``````

You may also want to check the validity of the parameters (`1 <= start <= end`).

Finally note that there is still a problem with numbers close to `Long.MAX_VALUE` because the calculations can overflow. If that is an issue then the range calculations and comparisons have to be done more carefully:

``````public static List<String> computePrefixes(long start, long end) {
List<String> prefixes = new ArrayList<String>();

while (start % 10 == 0 && end % 10 == 9) {
start /= 10;
end /= 10;
}

for (long i = start; ; ) {
// Determine `range` as largest power of 10 with `i % range == 0`
// and `i + range - 1 <= end`:
int range = 1;
while (range <= Long.MAX_VALUE / 10 && range <= i && i % range == 0 && range - 1 <= end - i) {
range *= 10;
}
range /= 10;

if (i == end) {
break;
}
i += range;
}

return prefixes;
}
``````

@MartinR’s answer is good, but I disagree on the choice of returning a list of strings. They should be maintained as `long` until the output stage. The return type can be made

``````public static List<Long>
``````

which, if you set `prefixes` to be a `List<Long>`, requires that the call to `String.valueOf` be removed.

In your `main` method, the rest of the code does not need to change. The advantage of leaving this as `Long` is that if you ever need to do further processing, it’s much easier.