In this blog post, we learn how to write a C program to find the length of the longest consecutive elements sequence from a given unsorted array of integers? So here we will write the C program to find the longest consecutive elements sequence in an unsorted array. We will also see how to display the sequence of consecutive elements in a sorted array using C programming.
Example,
//Given an input array
Input: arr[] = {2,5,7,7,8,8,9,4,10,12,3,6};
Output: 9
Explanation: The subsequence 2, 3, 4, 5, 6, 7, 8, 9, 10 is the longest subsequence of consecutive elements Logic to find the length of the longest consecutive elements sequence
Note: Array should not be empty.
So let’s see the Logic to find the first and last position of the element in a sorted array. Suppose arr is a given sorted integer array of size N (arr[N] ), the task is to write the C program to find the length of the longest consecutive elements sequence from a given unsorted array of integers.
1. Create two intermediate variables length and longestConsecutiveSeq.
2. Initialize the length and longestConsecutiveSeq variables with 1.
3. Now sort the unsorted array using the qsort. If you want you can create your own function for sorting the array elements.
4. Now iterate the sorted array elements from the beginning to end and skip the equal consecutive numbers.
5. If the current element is equal to the previous element+1 then increase the length else set the length to 1.
if (arr[i] + 1 == arr[i + 1])
{
length++;
}
else
{
length = 1;
}
If you want to learn more about the C language, you can check this course, Free Trial Available.
C Program to find length of longest consecutive elements sequence from given unsorted array of integers
#include <stdio.h>
#include <stdlib.h>
//Calculate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
//call back function
int compare(const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int findLongestConseqSeq(int arr[], const int n)
{
int length = 1;
int longestConsecutiveSeq = 1;
int i =0;
//sort arr elements using qsort inbuilt function
qsort( arr,n, sizeof(int), compare);
for ( i = 0; i < n - 1; i++)
{
if(arr[i] == arr[i+1])
{
continue;
}
else if (arr[i] + 1 == arr[i + 1])
{
length++;
}
else
{
length = 1;
}
longestConsecutiveSeq = (longestConsecutiveSeq > length)? longestConsecutiveSeq: length;
}
return longestConsecutiveSeq;
}
int main()
{
int arr[] = {2,5,7,7,8,8,9,4,10,12,3,6};
const int N = ARRAY_SIZE(arr);
const int longestConsecutiveSeq = findLongestConseqSeq(arr, N);
printf("Longest Consecutive Sequence >> %d\n\n",longestConsecutiveSeq);
return 0;
}
Recommended Articles for you:
- Best gift for programmers.
- Best electronic kits for programmers.
- C Program to find first and last position of element in sorted array
- Write C program to find the missing number in a given integer array of 1 to n
- C program to find the most popular element in an array
- Find the largest and smallest element in an array using C programming.
- C program to find even occurring elements in an array of limited range
- Find sum of all sub-array of a given array.
- C program to segregate even and odd numbers
- Find an element in array such that sum of left array is equal to sum of right array.
- C Program to find the count of even and odd elements in the array.
- Write C program to find the sum of array elements.
- C program to find odd occurring elements in an array of limited range
- Find the sum of array elements using recursion
- C Program to reverse the elements of an array
- C Program to find the maximum and minimum element in the array
- Calculate size of an array in without using sizeof in C
- How to create a dynamic array in C?
- How to access 2d array in C?
- Dangling, Void, Null and Wild Pointers
3 comments