print range, if number is missing

user_5821591 0
Viewed 96

I have a list of number which is sorted and want to print the continuous numbers range and if any number is missing in the series, we will start a new range. Note: There are possibility that multiple numbers are missing in the series continuously. example:

Input:
list = {301, 302, 303, 304, 305, 307, 308, 310, 312, 318, 319, 322, 390}
Output: range
301 - 305 //306 is missing so it breaks and new range starts
307 - 308 //309 is missing so breaks
310  // 311 is missing so breaks
312  // 313, 314, 315, 316, 317 are missing break (1 or more number can be missed)
318 - 319
322
390

My Logic:

int count = list.get(0);
        String output = list.get(0) + "-";
        for(int n: list){
            if(count++ != n){
                output = output+(count-2);
                System.out.println(output);
                output = n+"-";
                count++;
            }
        }

It's failing, if there are more then 2 numbers is missing in between.

data-structures list arrays algorithm java
4 Answers

I'd use two ints to track the beginning and end of each range. Going over the list, as long as the next number is the following number of the end, it becomes the new end. If it isn't, you have a new range at hand:

public static void main(String[] args) {
    int[] list = {301, 302, 303, 304, 305, 307, 308, 310, 312, 318, 319, 322, 390};

    int start = list[0];
    int end = list[1];
    for (int i = 2; i < list.length; ++i) {
        if (end + 1 == list[i]) {
            end++;
        } else {
            printRange(start, end);
            start = list[i];
            end = list[i];
        }
    }
    printRange(start, end);
}

private static void printRange(int start, int end) {
    if (start != end) {
        System.out.println(start + " - " + end);
    }
    else {
        System.out.println(start);
    }
}
user_24227760

You can avoid using count and make only comparison with the last value. Pseudocode:

start = 0
for (i=1; i<=n; i++) {
   if ((i==n) || (list[i]!=list[i-1]+1)) {
       output interval  list[start] - list[i-1] 
                           //omit the second if i-1==start   
       start = i  
   }
}
user_8444160

Here is simple logic in python -

list = [301, 302, 303, 304, 305, 307, 308, 310, 312, 318, 319, 322, 390]

def printRange(list):
    n = len(list)
    i = 0
    while i < n:
        flag = False
        j = i
        k = 0
        # Assuming the sequence is, difference between each number is 1
        while j + 1 < n and list[j] + 1 == list[j + 1]:
            j += 1
            k += 1
            flag = True
        if flag:
            print('{} - {}'.format(list[i], list[j]))
            i += k + 1
        else:
            print(list[i])
            i += 1

printRange(list)
user_120384280

We use double pointers to determine whether the sequence is continuous.

    public static void main(String[] args) {
        int[] arr = {301, 302, 303, 304, 305, 307, 308, 310, 312, 318, 319, 322, 390};
        printRange(arr);
    }
    
    private static void printRange(int[] arr) {
        int pre = arr[0];
        int start = arr[0];
        for (int i = 1; i < arr.length; i++) {
            while (i < arr.length - 1 && arr[i] == pre + 1) {
                pre = arr[i];
                i++;
            }
            
            // deal with last number
            if (i == arr.length - 1) {
                if (arr[i] == pre + 1) {
                    System.out.println(start + " - " + arr[i]);
                } else {
                    System.out.println(start);
                    System.out.println(arr[i]);
                }
                break;
            }
            
            if (pre != start) {
                System.out.println(start + " - " + pre);
            } else {
                System.out.println(start);
            }
            pre = arr[i];
            start = arr[i];
        }
    }
user_144337950
Related