Given an array arr[] consisting of N positive integers, the task is to find an index from the array having count of prime numbers present on its left and right are equal.
Examples:
Input: arr[] = {2, 3, 4, 7, 5, 10, 1, 8}
Output: 2
Explanation:
Consider the index 2, then the prime numbers to its left are {2, 3} and the prime numbers to its right are {7, 5}.
As, the count of prime numbers to the left and right index is 2, which is equal. Therefore, print 2.Input: arr[] = {8, 10, 2, 7, 3}
Output: 3
Naive Approach: The simplest approach to solve the given problem is to count the prime numbers to the left and right of each array element by traversing the array and print the index at which the count of prime numbers are found to be equal.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized using the Sieve of Eratosthenes and prefix sum technique to pre-store the prime numbers left and right to an array element. Follow the steps below to solve the problem:
- First, find the maximum value of the array arr[] and store it in a variable, say maxValue.
- Initialize a map < int, int>, say St, to store all the prime numbers in it.
- Iterate over the range [2, maxValue] and push all the values in St.
- Iterate over the range [2, maxValue] and perform the following operations:
- Initialize a variable j as 1 and iterate while the i*j is less than or equal to the maxValue.
- In each iteration of the above steps remove i*j from St and increment j by 1.
- Initialize two variables, say LeftCount and RightCount, to store the count of prime numbers in a prefix array and in a suffix array respectively.
- Initialize two arrays, say Prefix[] and Suffix[], to store the prefix sum array and suffix sum array of the count of prime numbers of the array arr[].
- Traverse the array arr[] and perform the following operations:
- Assign LeftCount to Prefix[i].
- If the value of arr[i] is present in St, then increment the value of LeftCount by 1.
- Iterate over the range [0, N-1] in reverse and perform the following operations:
- Assign RightCount to Suffix[i].
- If arr[i] is present in St, then increment the value of RightCount by 1.
- Iterate over the range [0, N – 1] and if the value of Prefix[i] is equal to the value of Suffix[i], then print the index i as the answer and break out of the loop.
- After completing the above steps, if none of the above cases satisfy then print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the index of the// array such that the count of prime// numbers to its either ends are sameint findIndex(int arr[], int N){ // Store the maximum value in // the array int maxValue = INT_MIN; // Traverse the array arr[] for (int i = 0; i < N; i++) { maxValue = max(maxValue, arr[i]); } // Stores all the numbers map<int, int> St; // Iterate over the range [1, Max] for (int i = 1; i <= maxValue; i++) { // Increment the value of st[i] St[i]++; } // Removes 1 from the map St if (St.find(1) != St.end()) { St.erase(1); } // Perform Sieve of Prime Numbers for (int i = 2; i <= sqrt(maxValue); i++) { int j = 2; // While i*j is less than // the maxValue while ((i * j) <= maxValue) { // If i*j is in map St if (St.find(i * j) != St.end()) { // Erase the value (i * j) St.erase(i * j); } // Increment the value of j j++; } } // Stores the count of prime from // index 0 to i int LeftCount = 0; // Stores the count of prime numbers int Prefix[N]; // Traverse the array arr[] for (int i = 0; i < N; i++) { Prefix[i] = LeftCount; // If arr[i] is present in the // map st if (St.find(arr[i]) != St.end()) { LeftCount++; } } // Stores the count of prime from // index i to N-1 int RightCount = 0; // Stores the count of prime numbers int Suffix[N]; // Iterate over the range [0, N-1] // in reverse order for (int i = N - 1; i >= 0; i--) { Suffix[i] = RightCount; // If arr[i] is in map st if (St.find(arr[i]) != St.end()) { RightCount++; } } // Iterate over the range [0, N-1] for (int i = 0; i < N; i++) { // If prefix[i] is equal // to the Suffix[i] if (Prefix[i] == Suffix[i]) { return i; } } // Return -1 if no such index // is present return -1;}// Driver Codeint main(){ int arr[] = { 2, 3, 4, 7, 5, 10, 1, 8 }; int N = sizeof(arr) / sizeof(arr[0]); cout << findIndex(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.HashMap;public class GFG { // Function to find the index of the // array such that the count of prime // numbers to its either ends are same static int findIndex(int arr[], int N) { // Store the maximum value in // the array int maxValue = Integer.MIN_VALUE; // Traverse the array arr[] for (int i = 0; i < N; i++) { maxValue = Math.max(maxValue, arr[i]); } // Stores all the numbers HashMap<Integer, Integer> St = new HashMap<>(); // Iterate over the range [1, Max] for (int i = 1; i <= maxValue; i++) { // Increment the value of st[i] St.put(i, St.getOrDefault(i, 0) + 1); } // Removes 1 from the map St if (St.containsKey(1)) { St.remove(1); } // Perform Sieve of Prime Numbers for (int i = 2; i <= Math.sqrt(maxValue); i++) { int j = 2; // While i*j is less than // the maxValue while ((i * j) <= maxValue) { // If i*j is in map St if (St.containsKey(i * j)) { // Erase the value (i * j) St.remove(i * j); } // Increment the value of j j++; } } // Stores the count of prime from // index 0 to i int LeftCount = 0; // Stores the count of prime numbers int Prefix[] = new int[N]; // Traverse the array arr[] for (int i = 0; i < N; i++) { Prefix[i] = LeftCount; // If arr[i] is present in the // map st if (St.containsKey(arr[i])) { LeftCount++; } } // Stores the count of prime from // index i to N-1 int RightCount = 0; // Stores the count of prime numbers int Suffix[] = new int[N]; // Iterate over the range [0, N-1] // in reverse order for (int i = N - 1; i >= 0; i--) { Suffix[i] = RightCount; // If arr[i] is in map st if (St.containsKey(arr[i])) { RightCount++; } } // Iterate over the range [0, N-1] for (int i = 0; i < N; i++) { // If prefix[i] is equal // to the Suffix[i] if (Prefix[i] == Suffix[i]) { return i; } } // Return -1 if no such index // is present return -1; } // Driver code public static void main(String[] args) { int arr[] = { 2, 3, 4, 7, 5, 10, 1, 8 }; int N = arr.length; System.out.println(findIndex(arr, N)); }}// This code is contributed by abhinavjain194 |
Python3
# Python 3 program for the above approachfrom collections import defaultdictimport sysimport math# Function to find the index of the# array such that the count of prime# numbers to its either ends are samedef findIndex(arr, N): # Store the maximum value in # the array maxValue = -sys.maxsize - 1 # Traverse the array arr[] for i in range(N): maxValue = max(maxValue, arr[i]) # / Stores all the numbers St = defaultdict(int) # Iterate over the range [1, Max] for i in range(1, maxValue + 1): # Increment the value of st[i] St[i] += 1 # Removes 1 from the map St if (1 in St): St.pop(1) # Perform Sieve of Prime Numbers for i in range(2, int(math.sqrt(maxValue)) + 1): j = 2 # While i*j is less than # the maxValue while ((i * j) <= maxValue): # If i*j is in map St if (i * j) in St: # Erase the value (i * j) St.pop(i * j) # Increment the value of j j += 1 # Stores the count of prime from # index 0 to i LeftCount = 0 # Stores the count of prime numbers Prefix = [0] * N # Traverse the array arr[] for i in range(N): Prefix[i] = LeftCount # If arr[i] is present in the # map st if (arr[i] in St): LeftCount += 1 # Stores the count of prime from # index i to N-1 RightCount = 0 # Stores the count of prime numbers Suffix = [0] * N # Iterate over the range [0, N-1] # in reverse order for i in range(N - 1, -1, -1): Suffix[i] = RightCount # If arr[i] is in map st if arr[i] in St: RightCount += 1 # Iterate over the range [0, N-1] for i in range(N): # If prefix[i] is equal # to the Suffix[i] if (Prefix[i] == Suffix[i]): return i # Return -1 if no such index # is present return -1# Driver Codeif __name__ == "__main__": arr = [2, 3, 4, 7, 5, 10, 1, 8] N = len(arr) print(findIndex(arr, N)) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find the index of the // array such that the count of prime // numbers to its either ends are same static int findIndex(int[] arr, int N) { // Store the maximum value in // the array int maxValue = Int32.MinValue; // Traverse the array arr[] for (int i = 0; i < N; i++) { maxValue = Math.Max(maxValue, arr[i]); } // Stores all the numbers Dictionary<int,int> St = new Dictionary<int,int>(); // Iterate over the range [1, Max] for (int i = 1; i <= maxValue; i++) { // Increment the value of st[i] St.Add(i, 1); } // Removes 1 from the map St if (St.ContainsKey(1)) { St.Remove(1); } // Perform Sieve of Prime Numbers for (int i = 2; i <= Math.Sqrt(maxValue); i++) { int j = 2; // While i*j is less than // the maxValue while ((i * j) <= maxValue) { // If i*j is in map St if (St.ContainsKey(i * j)) { // Erase the value (i * j) St.Remove(i * j); } // Increment the value of j j++; } } // Stores the count of prime from // index 0 to i int LeftCount = 0; // Stores the count of prime numbers int[] Prefix = new int[N]; // Traverse the array arr[] for (int i = 0; i < N; i++) { Prefix[i] = LeftCount; // If arr[i] is present in the // map st if (St.ContainsKey(arr[i])) { LeftCount++; } } // Stores the count of prime from // index i to N-1 int RightCount = 0; // Stores the count of prime numbers int[] Suffix = new int[N]; // Iterate over the range [0, N-1] // in reverse order for (int i = N - 1; i >= 0; i--) { Suffix[i] = RightCount; // If arr[i] is in map st if (St.ContainsKey(arr[i])) { RightCount++; } } // Iterate over the range [0, N-1] for (int i = 0; i < N; i++) { // If prefix[i] is equal // to the Suffix[i] if (Prefix[i] == Suffix[i]) { return i; } } // Return -1 if no such index // is present return -1; } // Driver code static public void Main (){ int[] arr = { 2, 3, 4, 7, 5, 10, 1, 8 }; int N = arr.Length; Console.WriteLine(findIndex(arr, N)); }}// This code is contributed by Dharanendra L V. |
Javascript
<script>// JavaScript program to count frequencies of array items// Function to find the index of the// array such that the count of prime// numbers to its either ends are samefunction findIndex( arr, N) { // Store the maximum value in // the array let maxValue = Number.MIN_VALUE;; // Traverse the array arr[] for (let i = 0; i < N; i++) { maxValue = Math.max(maxValue, arr[i]); } // Stores all the numbers var St = new Map(); // Iterate over the range [1, Max] for (let i = 1; i <= maxValue; i++) { // Increment the value of st[i] St.set(i, 1); } // Removes 1 from the map St if (St.has(1)) { St.delete(1); } // Perform Sieve of Prime Numbers for (let i = 2; i <= Math.sqrt(maxValue); i++) { let j = 2; // While i*j is less than // the maxValue while ((i * j) <= maxValue) { // If i*j is in map St if (St.has(i * j)) { // Erase the value (i * j) St.delete(i * j); } // Increment the value of j j++; } } // Stores the count of prime from // index 0 to i let LeftCount = 0; // Stores the count of prime numbers let Prefix = new Array(N); // Traverse the array arr[] for (let i = 0; i < N; i++) { Prefix[i] = LeftCount; // If arr[i] is present in the // map st if (St.has(arr[i])) { LeftCount++; } } // Stores the count of prime from // index i to N-1 let RightCount = 0; // Stores the count of prime numbers let Suffix = new Array(N); // Iterate over the range [0, N-1] // in reverse order for (let i = N - 1; i >= 0; i--) { Suffix[i] = RightCount; // If arr[i] is in map st if (St.has(arr[i])) { RightCount++; } } // Iterate over the range [0, N-1] for (let i = 0; i < N; i++) { // If prefix[i] is equal // to the Suffix[i] if (Prefix[i] == Suffix[i]) { return i; } } // Return -1 if no such index // is present return -1; }// Driver Codelet arr = [ 2, 3, 4, 7, 5, 10, 1, 8 ];let N = arr.length;document.write(findIndex(arr, N));// This code is contributed by jana_sayantan.</script> |
Output:
2
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
