3
\$\begingroup\$

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 .. )?

\$\endgroup\$
5
  • \$\begingroup\$ Do they need to be strings? Can they be converted to long? What's the maximum value? \$\endgroup\$ Commented Sep 24, 2019 at 16:22
  • 1
    \$\begingroup\$ Seems that your code assumes that they'll fit into an integer, which is even smaller than a long. \$\endgroup\$ Commented Sep 24, 2019 at 16:23
  • \$\begingroup\$ @Reinderien Sorry. Integer.parseInt was a typo. Should be Long.parseLong. I'll edit my post. I need the result as List<String> but it is absolutly fine to use other types somewhere in between for the values. \$\endgroup\$ Commented Sep 24, 2019 at 16:36
  • 1
    \$\begingroup\$ I don't understand the problem statement. For the first example, wouldn't a single prefix of 1 cover all of the numbers in the range? \$\endgroup\$ Commented Sep 24, 2019 at 16:39
  • 1
    \$\begingroup\$ My guess is that, rather than Generate the shortest list possible with prefixes that include the whole range, based on the example, the problem should state Generate the shortest list possible with prefixes that include ONLY the whole range and nothing outside of it. \$\endgroup\$ Commented Sep 24, 2019 at 17:04

2 Answers 2

Reset to default
1
\$\begingroup\$

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; }
\$\endgroup\$
1
  • \$\begingroup\$ Thank you so much for taking the time to thoroughly identify all flaws in my code. Thanks also for the hints and clear explanations. I have learned a lot. \$\endgroup\$ Commented Sep 25, 2019 at 7:46
1
\$\begingroup\$

@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.

\$\endgroup\$
2
  • \$\begingroup\$ I agree ..... :) \$\endgroup\$ Commented Sep 24, 2019 at 21:12
  • \$\begingroup\$ Thanks for mentioning that. I'll keep it in mind. \$\endgroup\$ Commented Sep 25, 2019 at 7:47

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.