Count elements in Array appearing only once and don’t have its consecutive next and previous present
Given an array arr[]. The task is to count elements in the array that appears only once and it’s consecutive next (arr[i]+1) and prev (arr[I] – 1) elements are not present in the array.
Examples
Input: arr[] = {7, 3, 1, 4, 5, 3, 4}
Output: 2
Explanation: Numbers 7 and 1 follows the given condition. Hence the answer is 2.Input: arr = {10, 6, 5, 8}
Output: 2
Naive Approach:
The naive approach to solve the problem is to use two nested loops to find for each element whether they are unique or not. If an element is unique, then again iterate entire array within the same outer loop which we used to find uniqueness, to find whether it’s consecutive next (arr[i]+1) and prev (arr[I] – 1) elements are present or not in the array. If they are not present increment the count.
Algorithm:
- Initialize count to 0.
- Traverse each element from i = 0 to n – 1
- Initialize unique to true
- Traverse each element from j = 0 to n – 1
i. If i is not equal to j and arr[i] is equal to arr[j], then set unique to false and break inner loop - If unique is true, then
i. Initialize next to false and prev to false
ii. Traverse each element from j = 0 to n – 1
a. If arr[j] is equal to arr[i] + 1, then set next to true
b. If arr[j] is equal to arr[i] – 1, then set prev to true
iii. If next is false and prev is false, then increment count
- Return count.
Below is the implementation of the approach:
C++
// C++ code for the approach #include <bits/stdc++.h> using namespace std; // Function to count unique elements // with no consecutive next and prev elements int countElements( int arr[], int n) { int count = 0; // traverse each element for ( int i = 0; i < n; i++) { bool unique = true ; for ( int j = 0; j < n; j++) { if (i != j && arr[i] == arr[j]) { unique = false ; break ; } } // check for consecutive next and prev // elements in the array if (unique) { bool next = false , prev = false ; for ( int j = 0; j < n; j++) { if (arr[j] == arr[i] + 1) next = true ; if (arr[j] == arr[i] - 1) prev = true ; } // increment count if consecutive // elements are not present if (!next && !prev) count++; } } return count; } // Driver's code int main() { // Input int arr[] = { 10, 6, 5, 8 }; int n = sizeof (arr) / sizeof (arr[0]); // Function call int count = countElements(arr, n); // Output cout << count; return 0; } |
Java
import java.util.Arrays; public class Main { // Function to count unique elements // with no consecutive next and prev elements public static int countElements( int [] arr, int n) { int count = 0 ; // Traverse each element for ( int i = 0 ; i < n; i++) { boolean unique = true ; for ( int j = 0 ; j < n; j++) { if (i != j && arr[i] == arr[j]) { unique = false ; break ; } } // Check for consecutive next and prev // elements in the array if (unique) { boolean next = false , prev = false ; for ( int j = 0 ; j < n; j++) { if (arr[j] == arr[i] + 1 ) next = true ; if (arr[j] == arr[i] - 1 ) prev = true ; } // Increment count if consecutive // elements are not present if (!next && !prev) count++; } } return count; } public static void main(String[] args) { // Input int [] arr = { 10 , 6 , 5 , 8 }; int n = arr.length; // Function call int count = countElements(arr, n); // Output System.out.println(count); } } |
Python
# Function to count unique elements # with no consecutive next and prev elements def count_elements(arr, n): count = 0 # Traverse each element for i in range (n): unique = True for j in range (n): if i ! = j and arr[i] = = arr[j]: unique = False break # Check for consecutive next and prev elements in the array if unique: next_element, prev_element = False , False for j in range (n): if arr[j] = = arr[i] + 1 : next_element = True if arr[j] = = arr[i] - 1 : prev_element = True # Increment count if consecutive elements are not present if not next_element and not prev_element: count + = 1 return count # Driver's code if __name__ = = "__main__" : # Input arr = [ 10 , 6 , 5 , 8 ] n = len (arr) # Function call count = count_elements(arr, n) # Output print (count) |
C#
using System; public class GFG { // Function to count unique elements // with no consecutive next and prev elements public static int CountElements( int [] arr, int n) { int count = 0; // traverse each element for ( int i = 0; i < n; i++) { bool unique = true ; for ( int j = 0; j < n; j++) { if (i != j && arr[i] == arr[j]) { unique = false ; break ; } } // check for consecutive next and prev // elements in the array if (unique) { bool next = false , prev = false ; for ( int j = 0; j < n; j++) { if (arr[j] == arr[i] + 1) next = true ; if (arr[j] == arr[i] - 1) prev = true ; } // increment count if consecutive // elements are not present if (!next && !prev) count++; } } return count; } public static void Main() { // Input int [] arr = { 10, 6, 5, 8 }; int n = arr.Length; // Function call int count = CountElements(arr, n); // Output Console.WriteLine(count); } } |
Javascript
// Function to count unique elements // with no consecutive next and prev elements function countElements(arr, n) { let count = 0; // Traverse each element for (let i = 0; i < n; i++) { let unique = true ; for (let j = 0; j < n; j++) { if (i !== j && arr[i] === arr[j]) { unique = false ; break ; } } // Check for consecutive next and prev elements in the array if (unique) { let next = false ; let prev = false ; for (let j = 0; j < n; j++) { if (arr[j] === arr[i] + 1) next = true ; if (arr[j] === arr[i] - 1) prev = true ; } // Increment count if consecutive elements are not present if (!next && !prev) count++; } } return count; } // Driver's code // Input const arr = [10, 6, 5, 8]; const n = arr.length; // Function call const count = countElements(arr, n); // Output console.log(count); |
2
Time Complexity: O(N*N) as two nested loops are executing both from 1 to N where N is the size of input array.
Space Complexity: O(1) as no extra space has been taken.
Approach: This problem can be solved by using HashMaps. Store the frequency of each number in hashmap and then traverse the array to check for uniqueness of the current element and occurrence of its consecutive next and previous elements.
Below is the implementation of the above approach.
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to count the number of elements // that follows the given conditions int count(vector< int >& nums) { // Take the size of array int n = nums.size(); // Hashmap to store the frequency // of all the elements map< int , int > m; for ( int i = 0; i < n; i++) { if (m.find(nums[i]) == m.end()) m.insert({ nums[i], 1 }); else m[nums[i]]++; } int c = 0; for ( auto i : m) { int p = i.first; if (m.find(p + 1) == m.end() && m.find(p - 1) == m.end() && i.second == 1) c++; } return c; } // Driver Code int main() { vector< int > arr = { 10, 6, 5, 8 }; // Function Call cout << count(arr); return 0; } |
Java
// JAVA program for above approach import java.util.*; class GFG { // Function to count the number of elements // that follows the given conditions public static int count(ArrayList<Integer> nums) { // Take the size of array int n = nums.size(); // Hashmap to store the frequency // of all the elements Map<Integer, Integer> m = new HashMap<Integer, Integer>(); for ( int i = 0 ; i < n; i++) { if (m.containsKey(nums.get(i)) == false ) m.put(nums.get(i), 1 ); else m.put(nums.get(i), m.get(nums.get(i)) + 1 ); } int c = 0 ; for (Map.Entry<Integer, Integer> i : m.entrySet()) { int p = i.getKey(); if (m.containsKey(p + 1 ) == false && m.containsKey(p - 1 ) == false && i.getValue() == 1 ) c++; } return c; } // Driver Code public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<>(Arrays.asList( 10 , 6 , 5 , 8 )); // Function Call System.out.print(count(arr)); } } // This code is contributed by Taranpreet |
Python3
# Python program for above approach # Function to count the number of elements # that follows the given conditions def count(nums): # Take the size of array n = len (nums) # Hashmap/dictionary to store the frequency # of all the elements m = {} for i in range ( 0 , n): if nums[i] not in m: m[nums[i]] = 1 else : m[nums[i]] + = 1 c = 0 for i in m: p = i if ( not m.__contains__(p + 1 ) and not m.__contains__(p - 1 ) and m[i] = = 1 ): c + = 1 return c # Driver Code arr = [ 10 , 6 , 5 , 8 ] # Function Call print (count(arr)) # This code is contributed by Palak Gupta |
C#
// C# program for above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Function to count the number of elements // that follows the given conditions static int count(ArrayList nums) { // Take the size of array int n = nums.Count; // Hashmap to store the frequency // of all the elements Dictionary< int , int > m = new Dictionary< int , int >(); for ( int i = 0; i < n; i++) { if (m.ContainsKey(( int )nums[i]) == false ) m.Add(( int )nums[i], 1); else m[( int )nums[i]] = m[( int )nums[i]] + 1; } int c = 0; foreach (KeyValuePair< int , int > i in m) { int p = i.Key; if (m.ContainsKey(p + 1) == false && m.ContainsKey(p - 1) == false && i.Value == 1) { c++; } } return c; } // Driver Code public static void Main() { ArrayList arr = new ArrayList(); arr.Add(10); arr.Add(6); arr.Add(5); arr.Add(8); // Function Call Console.Write(count(arr)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for above approach // Function to count the number of elements // that follows the given conditions const count = (nums) => { // Take the size of array let n = nums.length; // Hashmap to store the frequency // of all the elements let m = {}; for (let i = 0; i < n; i++) { if (!(nums[i] in m)) m[nums[i]] = 1; else m[nums[i]]++; } let c = 0; for (let i in m) { let p = parseInt(i); if ((!(p + 1 in m)) && (!(p - 1 in m)) && m[i] == 1) c++; } return c; } // Driver Code let arr = [10, 6, 5, 8]; // Function Call document.write(count(arr)); // This code is contributed by rakeshsahni </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)