RUN


Given:  An array of integers, we have to find the maximum length such that the elements are consecutive integers (the consecutive numbers can be in any order).

EXAMPLES:

Input : xyz[] = {5, 54, 3, 45, 6, 92, 4};

Output : 4 

 The maximum consecutive elements are 3, 4, 5, 6. 

Code:

#include <bits/stdc++.h>

int findlongsub(int array[], int no_of_elements)

{

	std::unordered_set<int> uno_set;	//taking a set of input

	for (int i = 0; i < no_of_elements; i++)

		uno_set.insert(array[i]);

	int answer = 0;

	for (int i = 0; i < no_of_elements; i++)

	{

		// to check for required elements in starting of set

		if (uno_set.find(array[i] - 1) == uno_set.end())

		{

			// Checking for all the consecutive elements in set 

			int j = array[i];

			// increment the value of array element and again search for the consecutive elements 

			while (uno_set.find(j) != uno_set.end())

				j++;

			answer = std::max(answer, j - array[i]);
		}
	}

	return answer;

}

// Main code 

int main()

{

	int array[] = { 5, 54, 3, 45, 6, 92, 4 };

	//here 3,4,5,6 are the longest subsequence

	int no_of_elements = sizeof(array) / sizeof(int);

	std::cout << findlongsub(array, no_of_elements) << std::endl;

	return 0;

}

Time complexity : O(n)

Report Error/ Suggestion

Related Posts:




CopyRight © 2020

CopyRight © 2020