Check if an array is formed by consecutive integers

Problem

Given an unsorted array of numbers, check if the array consists of consecutive numbers only.

Sample Input

[1, 2, 3, 4]

Sample Output

YES

Approach 1

You can sort the array and check if all adjacent elements have absolute difference as 1. If any pair with a difference other than 1 is found, return False. This approach takes O(NlogN) time (because of sorting).

Approach 2

We only need to check two conditions.

Condition 1 : maximum element -  minimum element + 1 = size of array

Condition 2 : There should be no duplicate elements in the array

This approach takes O(N) time and O(N) auxiliary space for creating extra data structures for checking duplicates. Let’s implement this approach

C++ Programming

#include<bits/stdc++.h>
using namespace std;
class Solution{
  int arr[5] = {1, 3, 4, 2};
  int n = sizeof(arr)/sizeof(arr[0]);
  unordered_map<int,int>vis;        // map to check if number is visited;
  int diff;
  bool dup = false;
  public:
  void solve(){
     // find difference b/w max and min element
     diff = *max_element(arr, arr+n)-*min_element(arr, arr+n)+1;    
     for(int i=0;i<n;i++){
         if(vis[arr[i]]==-1){      // if duplicate found
             dup =  true;
             break;
         }
         vis[arr[i]]=-1;
     }
     if(!dup && diff==n) cout<<"YES";    //if both conditions satisfy
     else cout<<"NO";
  }
};
int main(){
    Solution sol;
    sol.solve();
}

Output

YES

Python Programming

def solve(arr, n):
   if ( n < 1 ):
       return False  
   Min = min(arr)  
   Max = max(arr)
   if (Max - Min + 1 == n):
       vis = [False for i in range(n)]
       for i in range(n):
           if (vis[arr[i] - Min] != False):
               return False
           vis[arr[i] - Min] = True
       return True
arr = [1, 3, 4, 2]
n = len(arr)
if(solve(arr, n) == True):
   print("YES")
else:
   print("NO")

Output

YES

Java Programming

class Solution
{
	boolean solve(int arr[], int n)
	{
		if (n < 1)
			return false;

		int min = getMin(arr, n);

		int max = getMax(arr, n);

		if (max - min + 1 == n)
		{

			boolean vis[] = new boolean[n];
			int i;
			for (i = 0; i < n; i++)
			{
				if (vis[arr[i] - min] != false)
					return false;

				vis[arr[i] - min] = true;
			}
			
			return true;
		}
		return false; 
	}

	int getMin(int arr[], int n)
	{
		
int min = arr[0];
		for (int i = 1; i < n; i++)
		{
			if (arr[i] < min)
				min = arr[i];
		}
		return min;
	}

	int getMax(int arr[], int n)
	{
		int max = arr[0];
		for (int i = 1; i < n; i++) { if (arr[i] > max)
				max = arr[i];
		}
		return max;
	}

	public static void main(String[] args)
	{
		Solution consecutive = new Solution();
		int arr[] = {1, 3, 4, 2};
		int n = arr.length;
		if (consecutive.solve(arr, n) == true)
			System.out.println("YES");
		else
			System.out.println("NO");
	}
}

Output

YES

People are also reading:

• Find Factorial of Number using Recursion
• Multiply Two Matrices
• Shuffle a Deck of Cards
• Convert Celsius to Fahrenheit
• Swap Two Variables
• Solve Quadratic Equation
• Calculate the Area of a Triangle
• Python Regex
• Rectangle & Pyramids Pattern in C++
• Design Love Calculator