In the article, we are going to discuss one of the popular questions that is check if array contains contiguous integers with repeated elements allowed.

Problem Statement

Suppose you have been given an array of n integers with duplicates allowed. You need to check whether the given array is a collection of contiguous numbers, if it is then print "Yes" else "No".

Example

Input

arr[] = {5, 3, 6, 4, 4, 6}

Output

Yes

Contiguous set of integers: {3, 4, 5, 6}

Brute Force Approach

Firstly, we will sort the given array.

Now, we will traverse the array and check that every consecutive number will differ by at most by one.

Algorithm using the hash table

Add each component to the hash table.

Select the first element now, and keep increasing its value by 1 until you discover a value that isn't listed in the hash table.

Pick the first element once more, then keep lowering its value by 1 until you discover one that isn't in the hash table.

Count all the elements in the hash table you created using this method.

Print "Yes" if the count equals the hash size. Otherwise, "No."

C++ Code

/* C++ program to check if array contains contiguous integers with duplicates allowed */
#include <bits/stdc++.h>
using namespace std;
/* function to check the required condition */
bool areElementsContiguous(int arr[], int n) {
/* Storing elements of array in a hash table "hash" */
unordered_set<int> hash;
for (int i = 0; i < n; i++)
hash.insert(arr[i]);
/* as arr[0] is present in 'hash' */
int count = 1;
int element = arr[0] - 1;
/* check "element" is present in 'hash' */
while (hash.find(element) != hash.end()) {
/* increment count */
count++;
/* decrement element */
element--;
}
element = arr[0] + 1;
/* check "element" is present in 'hash' */
while (hash.find(element) != hash.end()) {
/* increment count */
count++;
/* increment element */
element++;
}
/* return true if required condition satisfies else false */
return (count == (int)(hash.size()));
}
/* Main program */
int main()
{
/* Input array */
int arr[] = { 5, 3, 6, 4, 4, 6 };
/* Size of an input array */
int n = sizeof(arr) / sizeof(arr[0]);
/* Printing required output */
if (areElementsContiguous(arr, n))
cout << "Yes";
else
cout << "No";
return 0;
}

You can also try this code with Online C++ Compiler

/* Java program to check if the array contains contiguous integers */
import java.io.*;
import java.util.*;
class Main {
/* function to check the required condition */
static Boolean areElementsContiguous(int arr[], int n) {
/* Storing elements of array in a hash table "hash" */
HashSet<Integer> hash = new HashSet<Integer>();
for (int i = 0; i < n; i++)
hash.add(arr[i]);
/* as arr[0] is present in 'hash' */
int count = 1;
int element = arr[0] - 1;
/* check "element" is present in 'hash' */
while (hash.contains(element) == true) {
/* increment count */
count++;
/* decrement element */
element--;
}
element = arr[0] + 1;
/* check "element" is present in 'hash' */
while (hash.contains(element) == true) {
/* increment count */
count++;
/* increment element */
element++;
}
/* return true if required condition satisfies else false */
return (count == (hash.size()));
}
/* Main program */
public static void main(String[] args)
{
/* Input array */
int arr[] = { 5, 3, 6, 4, 4, 6 };
/* Size of an input array */
int n = arr.length;
/* Printing required output */
if (areElementsContiguous(arr, n))
System.out.println("Yes");
else
System.out.println("No");
}
}

You can also try this code with Online Java Compiler

A hash table associates various keys with various values. Hash table implements the map, the serializable, and cloneable interfaces and inherits the dictionary type.

What are the hash table's three fundamental operations?

The fundamental principle operations of a hash table are: search which searches for an element in the hash table, Insert which adds a new element to the hash table, and Delete which removes an element from the hash table.

What is the load factor of a hash table?

Load factor can be defined as (m/n), where m is the preferred number of entries that can be added before the size of the underlying data structure needs to be increased and n is the overall size of the hash table.

How come hash tables are quick?

The linear time complexity of O(n) is required when searching through an array-like data structure that is the search time grows linearly in proportion to the size of the data structure. Simply, searching through an array is slower than using a hash table.

What is the time complexity of a hash table?

No matter how many entries are in the table, hash tables typically offer constant-time O(1) lookup. The majority of hash table schemes have an O(n) worst-case lookup time.