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;
prefixes.add(String.valueOf(i / range));
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;
prefixes.add(String.valueOf(i / range));
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.