Program Structure

This C program identifies the longest consecutive sequence of integers within an unsorted array. It utilizes a hash set (using a simple array) to track elements and count the lengths of consecutive sequences efficiently.

Program Code

#include 
#include 

// Function to find the longest consecutive sequence in the array
int longestConsecutive(int* nums, int numsSize) {
    if (numsSize == 0) return 0;

    // Create a hash set using an array
    int *hashSet = (int *)calloc(100000, sizeof(int));
    int maxLength = 0;

    // Populate the hash set
    for (int i = 0; i < numsSize; i++) {
        hashSet[nums[i]] = 1;
    }

    // Find the longest consecutive sequence
    for (int i = 0; i < numsSize; i++) { if (hashSet[nums[i]] == 1) { int currentNum = nums[i]; int currentStreak = 1; // Count upward streak while (hashSet[currentNum + 1] == 1) { currentNum++; currentStreak++; hashSet[currentNum] = 0; // Avoid counting it again } // Count downward streak currentNum = nums[i]; while (hashSet[currentNum - 1] == 1) { currentNum--; currentStreak++; hashSet[currentNum] = 0; // Avoid counting it again } // Update the maximum length found maxLength = maxLength > currentStreak ? maxLength : currentStreak;
        }
    }

    free(hashSet);
    return maxLength;
}

// Main function to test the longestConsecutive function
int main() {
    int nums[] = {100, 4, 200, 1, 3, 2};
    int size = sizeof(nums) / sizeof(nums[0]);
    
    int result = longestConsecutive(nums, size);
    printf("The longest consecutive sequence has length: %d\n", result);
    
    return 0;
}

Explanation of the Code

• Function Definition: The longestConsecutive function takes an integer array nums and its size numsSize as arguments.
• Hash Set Creation: An array hashSet is allocated to track the presence of numbers. This helps in checking if a number exists in O(1) time.
• Populating the Hash Set: The program iterates through the input array and marks each number’s presence in the hash set.
• Finding Consecutive Sequences: For each number, the program checks for consecutive numbers both upward and downward, counting the length of the sequence.
• Memory Management: The allocated memory for the hash set is freed before the function returns.

Usage

To use this program, simply compile it using a C compiler (like gcc) and run the executable. Modify the nums array in the main function to test different sequences.