Check if the Elements of an Array are Consecutive

Difficulty Level Easy
Frequently asked in Google Uber
ArrayViews 5650

Problem Statement

Given an array, Check if the elements of an array are consecutive. Here, consecutive elements mean, when we take all the elements in the array they need to form a consecutive sequence.

Example

Input

arr[]={65,68,66,64,67}

Output

array contains consecutive elements

here, all the elements in the array are consecutive as they are in increasing order ie, 64,65,66,67,68

Approach 1: Using Minimum and Maximum Element

Algorithm

1. First, find the minimum and maximum element in the array, Assign two variables min and max to the maximum and minimum integer values respectively.
Till less than the size of the array, pick each element in the array
a. If the element is greater than the max element, assign the max element to the picked element
b. If the element is less than the min element, assign min element to the picked element.
2. If the number of elements between max and min including themselves equals the size of the array then proceed.
Till less than the size of the array, pick each element in the array
a. If the element is repeated, then print that all elements are not consecutive and stop.
b. If the  Loop didn’t break, then print all are consecutive elements

Implementation

C++ Program for Check if the Elements of an Array are Consecutive

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    int min = INT_MAX , max = INT_MIN ;
  for(int i = 0 ; i < N; i++) //find minimum and maximum element
  {
    if(arr[i] > max)
      max = arr[i];
    if(arr[i] < min)
      min = arr[i];
  }
  if(max-min+1==N) // if the number of elements between max and min including themselves equals size of array then proceed
  {
    bool visited_nodes[N]={0};
    
    for(int i=0;i<N;i ++)
      {
        if(visited_nodes[arr[i] -  min] == 1) //it means the element is repeated so we cant get consecutive elements
          {
           cout << " Not all consecutive elements \n" ;
           return 0;  
          }  
        else
          visited_nodes[arr[i] - min] = 1;
      }
    cout << "Consecutive element set\n";
    return 0;
  }
  
  cout << " Not all consecutive elements \n" ;
  
  return 0;
}

Java Program for Check if the Elements of an Array are Consecutive

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int min = 10000000 , max = -10000000 ;
        for(int i=0;i<n;i++) //find minimum and maximum element
        {
          if(a[i] > max)
            max = a[i];
          if(a[i] < min)
            min = a[i];
        }
        if(max-min+1==n) // if the number of elements between max and min including themselves equals size of array then proceed
        {
          int visited_nodes[] = new int [n];
          for(int i=0;i<n;i++)
          {
              visited_nodes[i]=0;
          }
          for(int i=0;i<n;i ++)
          {
              if(visited_nodes[a[i] -  min] == 1) //it means the element is repeated so we cant get consecutive elements
              {
                 System.out.println("Not all consecutive elements");
                 i=n;  
              }  
              else
                visited_nodes[a[i] - min] = 1;
          }
          System.out.println("Consecutive element set");
        }
        else
        System.out.println(" Not all consecutive elements");
    }
}
5
3 5 2 4 6
Consecutive element set

Complexity Analysis for Check if the Elements of an Array are Consecutive

Time Complexity

O(n) where n is the number of elements present in the given array. Here we find the minimum and maximum element of the array in one traversal. And then check for contiguous sequence.

Space Complexity

O(1) because we don’t use any auxiliary space here. The above algorithm leads us to constant space complexity.

Approach 2: Using Sorting

Algorithm

1. Sort the elements in the array
2. Till the end of the sorted array, do linear scan
a. If the difference between the current element and the next element is anything other than     1, then print all elements are not consecutive
else,
b. If all differences are 1, then print all elements are consecutive.

Implementation

C++ Program for Check if the Elements of an Array are Consecutive

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+N);
    for(int i=0 ; i < N - 1; i++)
    if(arr[i+1] > arr[i] + 1)
    {
        cout << "Not all consecutive elements\n";
        return 0;
    }
    cout<<"Consecutive element set\n";
    return 0;
}

Java Program for Check if the Elements of an Array are Consecutive

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a);
        int temp=0;
        for(int i=0;i<n-1;i++)
        if(a[i+1]>a[i]+1)
        {
            System.out.println(" Not all consecutive elements");
            temp=1;
            i=n;
        }
        if(temp==0)
        System.out.println("Consecutive element set");
    }
}
6
1 2 3 5 6 7
Not all consecutive elements  

Complexity Analysis for Check if the Elements of an Array are Consecutive

Time Complexity

O(nlogn) where n is the number of elements present in the given array. Here we use the inbuild sort() function which has O(nlogn) time complexity.

Space Complexity

O(1) because we don’t use any auxiliary space here. The above algorithm leads us to constant space complexity.

References

Translate »