Given an array which is unsorted, check whether the elements are consecutive or not.
E.g. : 1 2 3 4 returns True, 1 3 4 5 returns False

Question

Given an array which is unsorted, check whether the elements are consecutive or not.

E.g. : 1 2 3 4 returns True, 1 3 4 5 returns False

Accepted Answer

- Used O(nLog(n)) sorting with merge sort

- Traverse through the arrey, if a[i]+1 != a[i+1] return False

- Else return true

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1),

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

Time Complexity: O(1)Explanation:

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).

Accepted Answer

Sorting

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.

Space Complexity: O(1)Explanation:

O(1),

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

Time Complexity: O(1)Explanation:

O(N * LogN), where N is the length of the array.

In the worst case, we will be sorting the array which takes O(N*logN) time and iterating array elements can take O(N). Thus time complexity will be O(N*logN + N) = O(N*logN).

Accepted Answer

Using Visited Array

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.

Space Complexity: O(1)Explanation:

O(N), where N is the length of the array.

In the worst case, we will be using extra space to keep a visited array of length N.

Time Complexity: O(1)Explanation:

O(N), where N is the length of the array.

In the worst case, we are running 2 loops to find the minimum and maximum elements and a single loop to mark false in the visited array. That would take (3 * N) running time.

Accepted Answer

In Place Algorithm

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.

Space Complexity: O(1)Explanation:

O(1),

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

Time Complexity: O(1)Explanation:

O(N), where N is the length of the array.

In the worst case, we are running only 3 single loops to iterate over the given array. That would take (3 * N) running time.

Accepted Answer

Sum of N Natural Numbers

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.

Space Complexity: O(1)Explanation:

O(1),

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

Time Complexity: O(1)Explanation:

O(N), where N is the length of the array.

In the worst case, we are running only 3 single loops to calculate the sum of the array. That would take (3 * N) running time.

Accepted Answer

#include

using namespace std;

int main()

{

int n;

cin>>n;

int arr[n];

for(int i=0;i

{

cin>>arr[i];

}

sort(arr,arr+n);

for(int i=0;i+1

{

if(arr[i]+1!=arr[i+1])

{

cout<<"false";

return 0;

}

cout<<"true";

return 1;

}

Top NatWest Group Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern