Given an array of n integers(duplicates allowed). Print “Yes” if it is a set of contiguous integers else print “No”.
Examples:
Input : arr[] = {5, 2, 3, 6, 4, 4, 6, 6}
Output : Yes
The elements form a contiguous set of integers
which is {2, 3, 4, 5, 6}.
Input : arr[] = {10, 14, 10, 12, 12, 13, 15}
Output : No
Source: Amazon interview Experience | Set 416.
We have discussed different solutions for distinct elements in below post.
Check if array elements are consecutive
A simple solution is to first sort the array. Then traverse the array to check if all consecutive elements differ at most by one.
C
// Sorting based C++ implementation // to check whether the array // contains a set of contiguous // integers #include <bits/stdc++.h> using namespace std; // function to check whether // the array contains a set // of contiguous integers bool areElementsContiguous(int arr[], int n) { // Sort the array sort(arr, arr+n); // After sorting, check if // current element is either // same as previous or is // one more. for (int i = 1; i < n; i++) if (arr[i] - arr[i-1] > 1) return false; return true; } // Driver program to test above int main() { int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 }; int n = sizeof(arr) / sizeof(arr[0]); if (areElementsContiguous(arr, n)) cout << "Yes"; else cout << "No"; return 0; } |
Java
// Sorting based Java implementation // to check whether the array // contains a set of contiguous // integers import java.util.*; class GFG { // function to check whether // the array contains a set // of contiguous integers static boolean areElementsContiguous(int arr[], int n) { // Sort the array Arrays.sort(arr); // After sorting, check if // current element is either // same as previous or is // one more. for (int i = 1; i < n; i++) if (arr[i] - arr[i-1] > 1) return false; return true; } /* Driver program to test above function */ public static void main(String[] args) { int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 }; int n = arr.length; if (areElementsContiguous(arr, n)) System.out.println("Yes"); else System.out.println("No"); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# Sorting based Python implementation # to check whether the array # contains a set of contiguous integers def areElementsContiguous(arr, n): # Sort the array arr.sort() # After sorting, check if # current element is either # same as previous or is # one more. for i in range(1,n): if (arr[i] - arr[i-1] > 1) : return 0 return 1 # Driver code arr = [ 5, 2, 3, 6, 4, 4, 6, 6 ] n = len(arr) if areElementsContiguous(arr, n): print("Yes") else: print("No") # This code is contributed by 'Ansu Kumari'. |
C#
// Sorting based C# implementation // to check whether the array // contains a set of contiguous // integers using System; class GFG { // function to check whether // the array contains a set // of contiguous integers static bool areElementsContiguous(int []arr, int n) { // Sort the array Array.Sort(arr); // After sorting, check if // current element is either // same as previous or is // one more. for (int i = 1; i < n; i++) if (arr[i] - arr[i - 1] > 1) return false; return true; } // Driver program public static void Main() { int []arr = { 5, 2, 3, 6, 4, 4, 6, 6 }; int n = arr.Length; if (areElementsContiguous(arr, n)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code is contributed by Vt_m. |
PHP
1)
return false;
return true;
}
// Driver Code
$arr = array( 5, 2, 3, 6,
4, 4, 6, 6 );
$n = sizeof($arr);
if (areElementsContiguous($arr, $n))
echo “Yes”;
else
echo “No”;
// This code is contributed by ajit
?>
Output:
Yes
Time Complexity : O(n Log n)
Efficient solution using visited array
1) Find minimum and maximum elements.
2) Create a visited array of size max – min + 1. Initialize this array as false.
3) Traverse the given array and mark visited[arr[i] – min] as true for every element arr[i].
4) Traverse visited array and return true if all values are true. Else return false.
C++
// C++ implementation to // check whether the array // contains a set of // contiguous integers #include <bits/stdc++.h> using namespace std; // function to check // whether the array // contains a set of // contiguous integers bool areElementsContiguous(int arr[], int n) { // Find maximum and // minimum elements. int max = *max_element(arr, arr + n); int min = *min_element(arr, arr + n); int m = max - min + 1; // There should be at least // m elements in array to // make them contiguous. if (m > n) return false; // Create a visited array // and initialize false. bool visited[m]; memset(visited, false, sizeof(visited)); // Mark elements as true. for (int i=0; i<n; i++) visited[arr[i] - min] = true; // If any element is not // marked, all elements // are not contiguous. for (int i=0; i<m; i++) if (visited[i] == false) return false; return true; } // Driver program int main() { int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 }; int n = sizeof(arr) / sizeof(arr[0]); if (areElementsContiguous(arr, n)) cout << "Yes"; else cout << "No"; return 0; } |
Java
// Java implementation to // check whether the array // contains a set of // contiguous integers import java.util.*; class GFG { // function to check // whether the array // contains a set of // contiguous integers static boolean areElementsContiguous(int arr[], int n) { // Find maximum and // minimum elements. int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } int m = max - min + 1; // There should be at least // m elements in aaray to // make them contiguous. if (m > n) return false; // Create a visited array // and initialize false. boolean visited[] = new boolean[n]; // Mark elements as true. for (int i = 0; i < n; i++) visited[arr[i] - min] = true; // If any element is not // marked, all elements // are not contiguous. for (int i = 0; i < m; i++) if (visited[i] == false) return false; return true; } /* Driver program */ public static void main(String[] args) { int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 }; int n = arr.length; if (areElementsContiguous(arr, n)) System.out.println("Yes"); else System.out.println("No"); } } |
Python3
# Python3 implementation to # check whether the array # contains a set of # contiguous integers # function to check # whether the array # contains a set of # contiguous integers def areElementsContiguous(arr, n): # Find maximum and # minimum elements. max1 = max(arr) min1 = min(arr) m = max1 - min1 + 1 # There should be at least # m elements in array to # make them contiguous. if (m > n): return False # Create a visited array # and initialize fals visited = [0] * m # Mark elements as true. for i in range(0,n) : visited[arr[i] - min1] = True # If any element is not # marked, all elements # are not contiguous. for i in range(0, m): if (visited[i] == False): return False return True # Driver program arr = [5, 2, 3, 6, 4, 4, 6, 6 ] n = len(arr) if (areElementsContiguous(arr, n)): print("Yes") else: print("No") # This code is contributed by Smitha Dinesh Semwal |
C#
// C# implementation to check whether // the array contains a set of // contiguous integers using System; class GFG { // function to check whether the // array contains a set of // contiguous integers static bool areElementsContiguous( int []arr, int n) { // Find maximum and // minimum elements. int max = int.MinValue; int min = int.MaxValue; for(int i = 0; i < n; i++) { max = Math.Max(max, arr[i]); min = Math.Min(min, arr[i]); } int m = max - min + 1; // There should be at least // m elements in aaray to // make them contiguous. if (m > n) return false; // Create a visited array // and initialize false. bool []visited = new bool[n]; // Mark elements as true. for (int i = 0; i < n; i++) visited[arr[i] - min] = true; // If any element is not // marked, all elements // are not contiguous. for (int i = 0; i < m; i++) if (visited[i] == false) return false; return true; } /* Driver program */ public static void Main() { int []arr = { 5, 2, 3, 6, 4, 4, 6, 6 }; int n = arr.Length; if (areElementsContiguous(arr, n)) Console.Write("Yes"); else Console.Write("No"); } } // This code is contributed by nitin mittal. |
Output:
Yes
Time Complexity : O(n)
Efficient solution using hash table
Insert all the elements in the hash table. Now pick the first element and keep on incrementing in its value by 1 till you find a value not present in the hash table. Again pick the first element and keep on decrementing in its value by 1 till you find a value not present in the hash table. Get the count of elements (obtained by this process) which are present in the hash table. If the count equals hash size print “Yes” else “No”.
C++
// C++ implementation to check whether the array // contains a set of contiguous integers #include <bits/stdc++.h> using namespace std; // Function to check whether the array contains // a set of contiguous integers bool areElementsContiguous(int arr[], int n) { // Storing elements of 'arr[]' in a hash // table 'us' unordered_set<int> us; for (int i = 0; i < n; i++) us.insert(arr[i]); // as arr[0] is present in 'us' int count = 1; // starting with previous smaller element // of arr[0] int curr_ele = arr[0] - 1; // if 'curr_ele' is present in 'us' while (us.find(curr_ele) != us.end()) { // increment count count++; // update 'curr_ele" curr_ele--; } // starting with next greater element // of arr[0] curr_ele = arr[0] + 1; // if 'curr_ele' is present in 'us' while (us.find(curr_ele) != us.end()) { // increment count count++; // update 'curr_ele" curr_ele++; } // returns true if array contains a set of // contiguous integers else returns false return (count == (int)(us.size())); } // Driver program to test above int main() { int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 }; int n = sizeof(arr) / sizeof(arr[0]); if (areElementsContiguous(arr, n)) cout << "Yes"; else cout << "No"; return 0; } |
Java
// Java implementation to check whether the array // contains a set of contiguous integers import java.io.*; import java.util.*; class GFG { // Function to check whether the array // contains a set of contiguous integers static Boolean areElementsContiguous(int arr[], int n) { // Storing elements of 'arr[]' in // a hash table 'us' HashSet<Integer> us = new HashSet<Integer>(); for (int i = 0; i < n; i++) us.add(arr[i]); // As arr[0] is present in 'us' int count = 1; // Starting with previous smaller // element of arr[0] int curr_ele = arr[0] - 1; // If 'curr_ele' is present in 'us' while (us.contains(curr_ele) == true) { // increment count count++; // update 'curr_ele" curr_ele--; } // Starting with next greater // element of arr[0] curr_ele = arr[0] + 1; // If 'curr_ele' is present in 'us' while (us.contains(curr_ele) == true) { // increment count count++; // update 'curr_ele" curr_ele++; } // Returns true if array contains a set of // contiguous integers else returns false return (count == (us.size())); } // Driver Code public static void main(String[] args) { int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 }; int n = arr.length; if (areElementsContiguous(arr, n)) System.out.println("Yes"); else System.out.println("No"); } } // This code is contributed by 'Gitanjali'. |
Python
# Python implementation to check whether the array # contains a set of contiguous integers # Function to check whether the array # contains a set of contiguous integers def areElementsContiguous(arr): # Storing elements of 'arr[]' in a hash table 'us' us = set() for i in arr: us.add(i) # As arr[0] is present in 'us' count = 1 # Starting with previous smaller element of arr[0] curr_ele = arr[0] - 1 # If 'curr_ele' is present in 'us' while curr_ele in us: # Increment count count += 1 # Update 'curr_ele" curr_ele -= 1 # Starting with next greater element of arr[0] curr_ele = arr[0] + 1 # If 'curr_ele' is present in 'us' while curr_ele in us: # Increment count count += 1 # Update 'curr_ele" curr_ele += 1 # Returns true if array contains a set of # contiguous integers else returns false return (count == len(us)) # Driver code arr = [ 5, 2, 3, 6, 4, 4, 6, 6 ] if areElementsContiguous(arr): print("Yes") else: print("No") # This code is contributed by 'Ansu Kumari' |
C#
using System; using System.Collections.Generic; // c# implementation to check whether the array // contains a set of contiguous integers public class GFG { // Function to check whether the array // contains a set of contiguous integers public static bool? areElementsContiguous(int[] arr, int n) { // Storing elements of 'arr[]' in // a hash table 'us' HashSet<int> us = new HashSet<int>(); for (int i = 0; i < n; i++) { us.Add(arr[i]); } // As arr[0] is present in 'us' int count = 1; // Starting with previous smaller // element of arr[0] int curr_ele = arr[0] - 1; // If 'curr_ele' is present in 'us' while (us.Contains(curr_ele) == true) { // increment count count++; // update 'curr_ele" curr_ele--; } // Starting with next greater // element of arr[0] curr_ele = arr[0] + 1; // If 'curr_ele' is present in 'us' while (us.Contains(curr_ele) == true) { // increment count count++; // update 'curr_ele" curr_ele++; } // Returns true if array contains a set of // contiguous integers else returns false return (count == (us.Count)); } // Driver Code public static void Main(string[] args) { int[] arr = new int[] {5, 2, 3, 6, 4, 4, 6, 6}; int n = arr.Length; if (areElementsContiguous(arr, n).Value) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } } // This code is contributed by Shrikant13 |
Output :
Yes
Time Complexity: O(n).
Auxiliary Space: O(n).
This method requires only one traversal of given array. It traverses hash table after array traversal (hash table contains only distinct elements).
leave a comment
0 Comments