Given an array arr[] of n elements and a number K. The task is to determine if it is possible to reach the end of the array by doing the below operations:
Traverse the given array and,
- If any element is found to be non-prime then decrement the value of K by 1.
- If any element is prime then refill the value of K to its initial value.
If it is possible to reach the end of array with (K > 0), then print YES otherwise print NO.
Examples:
Input : K = 2, arr[]={ 6, 3, 4, 5, 6};
Output : Yes
Explanation :
1- arr[0] is not prime, so K = K-1 = 1
2- arr[1] is prime so K will be refilled to its
initial value. Therefore, K = 2.
3- arr[2] is not prime.
Therefore, K = 2-1 = 1
4- arr[3] is prime so K will be refilled to its
initial value. Therefore, K = 2.
5- arr[4] is not prime.
Therefore, K = 2-1 = 1
6- Since the end of the array is reached with K>=0
So output is YES
Input : k=3, arr[]={ 1, 2, 10, 4, 6, 8};
Output : No
Recommended: Please solve it on “PRACTICE “first, before moving on to the solution.
Simple Approach:
- Traverse each element of the array and Check if the value of the current element is prime or not.
- If it is Prime then refill the power of K else decrements by 1.
- If it is possible to reach the end of the array with (K > 0) then print “YES” otherwise “NO”.
Below is the implementation of the above approach:
C++
// C++ program to check if it is possible// to reach the end of the array#include <iostream>using namespace std;// Function To check number is prime or notbool is_Prime( int num ) { // because 1 is not prime if(num == 1) return false; for(int i=2 ; i*i <= num ; i++ ) { if( num % i == 0 ) return false; } return true; }// Function to check whether it is possible// to reach the end of the array or not bool isReachable( int arr[] , int n , int k){ // store initial value of K int x = k ; for(int i=0 ; i < n ; i++ ) { // Call is_prime function to // check if a number is prime. if( is_Prime(arr[i]) ) { // Refill K to initial value k = x; } else { // Decrement k by 1 k-- ; } if( k <= 0 && i < (n-1) && (!is_Prime(arr[i+1])) ) return false ; } return true ;}// Driver Codeint main(){ int arr[] = { 6, 3, 4, 5, 6}; int n = sizeof(arr)/sizeof(arr[0]) ; int k = 2 ; isReachable( arr , n , k ) ? cout << "Yes" << endl : cout << "No" << endl ; return 0 ;} |
Java
// Java program to check if // it is possible to reach// the end of the arrayimport java.io.*;import java.util.*;import java.lang.*;class GFG{ // Function To check // number is prime or notstatic boolean is_Prime(int num) { // because 1 is not prime if(num == 1) return false; for(int i = 2 ; i * i <= num ; i++ ) { if(num % i == 0) return false; } return true; }// Function to check whether // it is possible to reach// the end of the array or not static boolean isReachable(int arr[] , int n , int k){ // store initial value of K int x = k ; for(int i = 0 ; i < n ; i++ ) { // Call is_prime function to // check if a number is prime. if(is_Prime(arr[i])) { // Refill K to // initial value k = x; } else { // Decrement k by 1 k-- ; } if(k <= 0 && i < (n - 1) && (is_Prime(arr[i + 1]) != true)) return false ; } return true ;}// Driver Codepublic static void main(String args[]){ int arr[] = new int[]{ 6, 3, 4, 5, 6}; int n = arr.length; int k = 2 ; if(isReachable(arr, n, k) == true) System.out.print("Yes" + "\n"); else System.out.print("No" + "\n"); } } |
Python3
# Python 3 program to check if it is # possible to reach the end of the arrayfrom math import sqrt# Function To check number is prime or notdef is_Prime(num): # because 1 is not prime if(num == 1): return False k = int(sqrt(num)) + 1 for i in range(2, k, 1): if(num % i == 0): return False return True# Function to check whether it is possible# to reach the end of the array or not def isReachable(arr, n , k): # store initial value of K x = k for i in range(0, n, 1): # Call is_prime function to # check if a number is prime. if( is_Prime(arr[i])): # Refill K to initial value k = x else: # Decrement k by 1 k -= 1 if(k <= 0 and i < (n - 1) and (is_Prime(arr[i + 1])) == False): return False return True# Driver Codeif __name__ == '__main__': arr = [6, 3, 4, 5, 6] n = len(arr) k = 2 if (isReachable( arr , n , k )): print("Yes") else: print("No")# This code is contributed by# Sahil_Shelangia |
C#
// C# program to check if // it is possible to reach// the end of the arrayusing System;class GFG{ // Function To check // number is prime or notstatic bool is_Prime(int num) { // because 1 is not prime if(num == 1) return false; for(int i = 2 ; i * i <= num ; i++ ) { if(num % i == 0) return false; } return true; }// Function to check whether // it is possible to reach// the end of the array or not static bool isReachable(int []arr , int n , int k){ // store initial // value of K int x = k ; for(int i = 0 ; i < n ; i++ ) { // Call is_prime function // to check if a number // is prime. if(is_Prime(arr[i])) { // Refill K to // initial value k = x; } else { // Decrement k by 1 k-- ; } if(k <= 0 && i < (n - 1) && (is_Prime(arr[i + 1]) != true)) return false ; } return true ;}// Driver Codepublic static void Main(){ int []arr = new int[]{ 6, 3, 4, 5, 6}; int n = arr.Length; int k = 2 ; if(isReachable(arr, n, k) == true) Console.WriteLine("Yes" + "\n"); else Console.WriteLine("No" + "\n"); } }// This code is contributed by vt_m |
PHP
<?php// PHP program to check if it is possible// to reach the end of the array// Function To check number // is prime or notfunction is_Prime($num ) { // because 1 is not prime if($num == 1) return false; for($i = 2 ; ($i * $i) <= $num ; $i++ ) { if($num % $i == 0) return false; } return true; }// Function to check whether it is possible// to reach the end of the array or not function isReachable($arr , $n , $k){ // store initial value of K $x = $k ; for($i = 0 ; $i < $n ; $i++) { // Call is_prime function to // check if a number is prime. if(is_Prime($arr[$i])) { // Refill K to initial value $k = $x; } else { // Decrement k by 1 $k-- ; } if($k <= 0 && $i < ($n - 1) && (!is_Prime($arr[$i + 1]))) return false ; } return true ;}// Driver Code$arr = array(6, 3, 4, 5, 6);$n = sizeof($arr);$k = 2;if(isReachable( $arr , $n , $k )) echo "Yes";else echo "No" ; // This code is contributed // by Sach_Code?> |
Javascript
<script>// Javascript program to check if// it is possible to reach// the end of the array// Function To check// number is prime or notfunction is_Prime(num){ // Because 1 is not prime if(num == 1) return false; for(let i = 2; i * i <= num; i++) { if(num % i == 0) return false; } return true;}// Function to check whether// it is possible to reach// the end of the array or notfunction isReachable(arr, n, k){ // Store initial // value of K let x = k ; for(let i = 0 ; i < n ; i++ ) { // Call is_prime function // to check if a number // is prime. if (is_Prime(arr[i])) { // Refill K to // initial value k = x; } else { // Decrement k by 1 k-- ; } if (k <= 0 && i < (n - 1) && (is_Prime(arr[i + 1]) != true)) return false; } return true;}// Driver codelet arr = [ 6, 3, 4, 5, 6 ];let n = arr.length;let k = 2 ;if (isReachable(arr, n, k) == true) document.write("Yes" + "</br>");else document.write("No" + "</br>"); // This code is contributed by decode2207</script> |
Output
Yes
Time complexity: O(N(sqrt N))
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using the Sieve of Eratosthenes to check if a number is prime or not.
Below is the implementation of the efficient approach:
C++
// C++ program to check if it is possible// to reach the end of the array#include <iostream>#define MAX 1000000using namespace std;// Function for Sieve of Eratosthenesvoid SieveOfEratosthenes( int sieve[], int max ) { for(int i=0; i<max; i++) sieve[i] = 1; for(int i=2 ; i*i <= max ; i++ ) { if( sieve[i] == 1 ) { for( int j=i*2 ; j <= max ; j+=i ) sieve[ j ] = 0; } }}// Function to check if it is possible to// reach end of the array bool isReachable( int arr[] , int n , int sieve[] , int k){ // store initial value of K int x = k; for(int i=0 ; i < n ; i++ ) { if( sieve[arr[i]] ) { // Refill K to initial value k = x; } else { // Decrement k by 1 k -= 1; } if((k <= 0) && (i < (n-1)) && (sieve[arr[i+1]] == 0)) { return false ; } } return true ;}// Driver Codeint main(){ int arr[] = {6, 3, 4, 5, 6}; int sieve[MAX]; int n = sizeof(arr)/sizeof(arr[0]) ; int k = 2; SieveOfEratosthenes(sieve, MAX) ; isReachable( arr , n , sieve , k ) ? cout << "Yes" << endl : cout << "No" << endl ; return 0 ;} |
Java
// Java program to check if it is possible// to reach the end of the arrayclass GFG { static int MAX = 1000000; // Function for Sieve of Eratosthenes static void SieveOfEratosthenes(int sieve[], int max) { for (int i = 0; i < max; i++) { sieve[i] = 1; } for (int i = 2; i * i < max; i++) { if (sieve[i] == 1) { for (int j = i * 2; j < max; j += i) { sieve[j] = 0; } } } } // Function to check if it is possible to // reach end of the array static boolean isReachable(int arr[], int n, int sieve[], int k) { // store initial value of K int x = k; for (int i = 0; i < n; i++) { if (sieve[arr[i]] == 1) { // Refill K to initial value k = x; } else { // Decrement k by 1 k -= 1; } if ((k <= 0) && (i < (n - 1)) && (sieve[arr[i + 1]] == 0)) { return false; } } return true; } // Driver Code public static void main(String[] args) { int arr[] = {6, 3, 4, 5, 6}; int[] sieve = new int[MAX]; int n = arr.length; int k = 2; SieveOfEratosthenes(sieve, MAX); if (isReachable(arr, n, sieve, k)) { System.out.println("Yes"); } else { System.out.println("No"); } }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 program to check if it is# possible to reach the end of the # array import math # Function for Sieve of Eratosthenes def SieveOfEratosthenes(sieve, max): for i in range(0, max): sieve[i] = 1 sqt = int(math.sqrt(max)) for i in range(2, sqt): if (sieve[i] == 1): for j in range(i * 2, max, i): sieve[j] = 0# Function to check if it is possible to # reach end of the array def isReachable(arr, n, sieve, k): # store initial value of K x = k for i in range(0, n): if (sieve[arr[i]] != 0): # Refill K to initial value k = x else: # Decrement k by 1 k -= 1 if ((k <= 0) and (i < (n - 1)) and (sieve[arr[i + 1]] == 0)): return 0 return 1# Driver Code arr = [ 6, 3, 4, 5, 6 ] sieve = [0 for x in range(1000000)] n = len(arr) k = 2SieveOfEratosthenes(sieve, 1000000)ch = isReachable(arr, n, sieve, k)if (ch): print("Yes") else: print("No") # This code is contributed by Stream_Cipher |
C#
// C# program to check if it is possible// to reach the end of the arrayusing System;class GFG{ static int MAX = 1000000; // Function for Sieve of Eratosthenes static void SieveOfEratosthenes(int []sieve, int max) { for (int i = 0; i < max; i++) { sieve[i] = 1; } for (int i = 2; i * i < max; i++) { if (sieve[i] == 1) { for (int j = i * 2; j < max; j += i) { sieve[j] = 0; } } } } // Function to check if it is possible to // reach end of the array static bool isReachable(int []arr, int n, int []sieve, int k) { // store initial value of K int x = k; for (int i = 0; i < n; i++) { if (sieve[arr[i]] == 1) { // Refill K to initial value k = x; } else { // Decrement k by 1 k -= 1; } if ((k <= 0) && (i < (n - 1)) && (sieve[arr[i + 1]] == 0)) { return false; } } return true; } // Driver Code static public void Main () { int []arr = {6, 3, 4, 5, 6}; int[] sieve = new int[MAX]; int n = arr.Length; int k = 2; SieveOfEratosthenes(sieve, MAX); if (isReachable(arr, n, sieve, k)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }}/* This code contributed by ajit. */ |
Javascript
<script> // Javascript program to check if it is possible // to reach the end of the array let MAX = 1000000; // Function for Sieve of Eratosthenes function SieveOfEratosthenes(sieve, max) { for (let i = 0; i < max; i++) { sieve[i] = 1; } for (let i = 2; i * i < max; i++) { if (sieve[i] == 1) { for (let j = i * 2; j < max; j += i) { sieve[j] = 0; } } } } // Function to check if it is possible to // reach end of the array function isReachable(arr, n, sieve, k) { // store initial value of K let x = k; for (let i = 0; i < n; i++) { if (sieve[arr[i]] == 1) { // Refill K to initial value k = x; } else { // Decrement k by 1 k -= 1; } if ((k <= 0) && (i < (n - 1)) && (sieve[arr[i + 1]] == 0)) { return false; } } return true; } let arr = [6, 3, 4, 5, 6]; let sieve = new Array(MAX); let n = arr.length; let k = 2; SieveOfEratosthenes(sieve, MAX); if (isReachable(arr, n, sieve, k)) { document.write("Yes"); } else { document.write("No"); }</script> |
Output
Yes
Time complexity: O(MAX * log(log(MAX)))
Auxiliary Space: O(MAX)
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!
