Problem

Submissions

Hints & solutions

Discuss

Consecutive elements

Moderate

0/80

Average time to solve is 15m

11 upvotes

Asked in companies

Problem statement

You are given an array arr of N non-negative integers, you need to return true if the array elements consist of consecutive numbers otherwise return false.

For Example: If the given array is [4,3,5] then you should return true as all the array elements are in consecutive order.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 
Then the T test cases follow.

The first line of each test case contains an integer 'N', representing the length of the array.

The next line contains 'N' single space-separated integers representing elements of the array.

Output Format :

For each test case, print “True” or “False” in a separate line.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
0 <= arr[i] <= 10^9

Time Limit: 1 sec

Sample Input 1:

1
4
1 2 4 6

Sample Output 1:

False

Explanation for Input 1:

As 3 and 5 are not in the array. Thus, this makes the array non-consecutive.

Sample Input 2:

1
3
7 9 8

Sample Output 2:

True

Hint 1

Hint 2

Hint 3

Hint 4

Hint 5

Think of searching all the numbers between the maximum element and the minimum element present in the array.

Approaches (5)

Approach 1

Approach 2

Approach 3

Approach 4

Approach 5

Brute Force

Get the minimum and maximum element of the array.
Check if (max-min+1) is equal to N or not, if it is not equal then return false.
For every element between the minimum and maximum number, check whether it is present in the array or not by using linear search.
If it is present, then continue, otherwise return false.
Finally, If we have reached the maximum element that means all elements between the minimum element and the maximum element is present thus return true.

Time Complexity

O(Max * N), where N is the length of the array and Max is the maximum element of the array.

In the worst case, we will be searching for each number between the minimum and maximum element that will take O(Max) time. Thus total time would be O(N * Max).

Space Complexity

O(1),

In the worst case, only a constant extra space is required.

(100% EXP penalty)

Consecutive elements

Console