Minimum window size containing atleast P primes in every window of given range | Python3 implementation to find the minimum window size in the range such that each window of that size contains atleast P primes ; Function to check that a number is a prime or not in O ( sqrt ( N ) ) ; Loop to check if any number number is divisible by any other number or not ; Function to check whether window size satisfies condition or not ; Loop to check each window of size have atleast P primes ; Checking condition using prefix sum ; Function to find the minimum window size possible for the given range in X and Y ; Prefix array ; Mark those numbers which are primes as 1 ; Convert to prefix sum ; Applying binary search over window size ; Check whether mid satisfies the condition or not ; If satisfies search in first half ; Else search in second half ; Driver Code
from math import sqrt NEW_LINE def isPrime ( N ) : NEW_LINE INDENT if ( N < 2 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( N < 4 ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( ( N & 1 ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( N % 3 == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT curr = 5 NEW_LINE s = sqrt ( N ) NEW_LINE while ( curr <= s ) : NEW_LINE INDENT if ( N % curr == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT curr += 2 NEW_LINE if ( N % curr == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT curr += 4 NEW_LINE DEDENT return True NEW_LINE DEDENT def check ( s , p , prefix_sum , n ) : NEW_LINE INDENT satisfies = True NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( i + s - 1 >= n ) : NEW_LINE INDENT break NEW_LINE DEDENT if ( i - 1 >= 0 ) : NEW_LINE INDENT x = prefix_sum [ i - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT x = 0 NEW_LINE DEDENT if ( prefix_sum [ i + s - 1 ] - x < p ) : NEW_LINE INDENT satisfies = False NEW_LINE DEDENT DEDENT return satisfies NEW_LINE DEDENT def minimumWindowSize ( x , y , p ) : NEW_LINE INDENT prefix_sum = [ 0 ] * ( y - x + 1 ) NEW_LINE for i in range ( x , y + 1 ) : NEW_LINE INDENT if ( isPrime ( i ) ) : NEW_LINE INDENT prefix_sum [ i - x ] = 1 NEW_LINE DEDENT DEDENT for i in range ( 1 , y - x + 1 ) : NEW_LINE INDENT prefix_sum [ i ] += prefix_sum [ i - 1 ] NEW_LINE DEDENT low = 1 NEW_LINE high = y - x + 1 NEW_LINE while ( high - low > 1 ) : NEW_LINE INDENT mid = ( low + high ) // 2 NEW_LINE if ( check ( mid , p , prefix_sum , y - x + 1 ) ) : NEW_LINE INDENT high = mid NEW_LINE DEDENT else : NEW_LINE INDENT low = mid NEW_LINE DEDENT DEDENT if ( check ( low , p , prefix_sum , y - x + 1 ) ) : NEW_LINE INDENT return low NEW_LINE DEDENT return high NEW_LINE DEDENT x = 12 NEW_LINE y = 42 NEW_LINE p = 3 NEW_LINE print ( minimumWindowSize ( x , y , p ) ) NEW_LINE