Last Updated: 13 Oct, 2020
Consecutive elements
Moderate
Asked in companies
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.
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
Approaches
- 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.
- Sort the array in increasing order.
- Get the minimum element (arr[0]) and the maximum element (arr[N-1]) of the array.
- Check if (max-min+1) is equal to N or not, if it is not equal then return false.
- Traverse the array and check if the current element is 1 less than the next element or not, if it is not then the array is not consecutive, thus return false.
- Finally, If we have reached the end of the array that means all elements between the minimum element and the maximum element is present thus return true.
- 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.
- Create a visited array that will store true at index i if (arr[i]-min) is present.
- Traverse the array and check if visited[arr[i]-min] is true or false, if it is true that means there is the repetition of element arr[i], hence return false.
- Otherwise, mark visited[arr[i]-min] false.
- Finally, if we have reached the end of the array that means all elements between the minimum element and the maximum element is present thus return true.
- 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 each element, check arr[i]-min is negative or not.
- If it is negative then check if arr[-arr[i]-min] is negative then it means that current element is already present, so return false.
- Otherwise, mark arr[-arr[i]-min] negative.
- Else check, if arr[arr[i]-min] is negative then it means that current element is already present, so return false.
- Otherwise, mark arr[arr[i]-min] negative.
- Finally, if we have reached the end of the array that means all elements between the minimum element and the maximum element is present thus return true.
- 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.
- Create a variable arraySum of long type to store the sum of elements of the array and subtracting min from all the elements.
- Traverse the array and update arraySum by arr[i]-min.
- Now, calculate the sum of the first N-1 natural numbers using formula.
- If both sums are equal then return true, otherwise, return false.
Similar problems