Summary Ranges - C Solution

1. Introduction

This post addresses a problem known as "Summary Ranges" in the context of C programming. The task is to condense a sorted array of unique integers into the smallest possible list of ranges. This problem is a great exercise in array manipulation, string formatting, and efficiently summarizing data.

Problem

Given a sorted array of unique integers, the goal is to return the smallest sorted list of ranges that cover all the numbers in the array exactly. Each range [a,b] should be represented as "a->b" if a != b, or "a" if a == b.

2. Solution Steps

1. Initialize a dynamic array or a list to store the resulting range strings.

2. Traverse the sorted array and identify the start and end of each range.

3. For each range, format the range string according to the problem statement.

4. Append each formatted range string to the result list.

5. Return the list of range strings.

3. Code Program

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Helper function to format a range string
char* formatRange(int start, int end) {
    char* range = (char*)malloc(50 * sizeof(char));
    if (start == end) {
        sprintf(range, "%d", start);
    } else {
        sprintf(range, "%d->%d", start, end);
    }
    return range;
}

// Function to find summary ranges
char** summaryRanges(int* nums, int numsSize, int* returnSize) {
    if (numsSize == 0) {
        *returnSize = 0;
        return NULL;
    }

    char** ranges = (char**)malloc(numsSize * sizeof(char*));
    *returnSize = 0;
    int start = nums[0], end = nums[0];

    for (int i = 1; i < numsSize; i++) {
        if (nums[i] == nums[i - 1] + 1) {
            end = nums[i];
        } else {
            ranges[*returnSize] = formatRange(start, end);
            (*returnSize)++;
            start = end = nums[i];
        }
    }
    ranges[*returnSize] = formatRange(start, end);
    (*returnSize)++;

    return ranges;
}

// Main function to test the summaryRanges function
int main() {
    int nums[] = {0, 1, 2, 4, 5, 7};
    int size, *returnSize = &size;
    char** result = summaryRanges(nums, 6, returnSize);

    printf("Summary Ranges: ");
    for (int i = 0; i < *returnSize; i++) {
        printf("%s ", result[i]);
        free(result[i]); // Free each range string
    }
    free(result); // Free the result array

    return 0;
}

Output:

Summary Ranges: 0->2 4->5 7

Explanation:

1. formatRange generates a string for a given range.

2. summaryRanges identifies start and end of each range and uses formatRange to create range strings.

3. Store each range string in a dynamically allocated array.

4. The main function tests summaryRanges with a sample array and prints the output.

5. Memory allocated for range strings and the result array is freed.