Number of ways to choose K intersecting line segments on X | Java program to find Number of ways to choose K intersecting line segments on X - axis ; Function to find ( a ^ b ) % mod in log b ; Till power becomes 0 ; If power is odd ; Multiply base ; Divide power by 1 ; Function to find nCk ; Base case ; Apply formula to find nCk ; Function to find the number of ways ; sort the given lines ; Find the number of total case ; Declare a multiset ; Loop till N ; Check if smallest element is smaller than lines [ i ] ; Erase first element ; Exclude the odd cases ; Modulus operation ; Insert into multiset ; Function to precompute factorial and inverse ; Pre - compute factorial and inverse ; Driver code ; Function to pre - compute factorial and inverse
import java . util . * ; import java . lang . * ; class GFG { static long mod = 1000000007 ; static int MAXN = 1001 ; static long factorial [ ] = new long [ MAXN ] , inverse [ ] = new long [ MAXN ] ; static long power ( long a , long b ) { long res = 1 ; while ( b > 0 ) { if ( b % 2 == 1 ) { res = ( res * a ) % mod ; } a = ( a * a ) % mod ; b >>= 1 ; } return res ; } static long nCk ( int n , int k ) { if ( k < 0 k > n ) { return 0 ; } long ans = factorial [ n ] ; ans = ( ans * inverse [ n - k ] ) % mod ; ans = ( ans * inverse [ k ] ) % mod ; return ans ; } static void numberOfWays ( ArrayList < int [ ] > lines , int K , int N ) { Collections . sort ( lines , ( a , b ) -> a [ 0 ] - b [ 0 ] ) ; long total_case = nCk ( N , K ) ; PriorityQueue < Integer > m = new PriorityQueue < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { while ( ! m . isEmpty ( ) && ( m . peek ( ) < lines . get ( i ) [ 0 ] ) ) { m . poll ( ) ; } total_case -= nCk ( m . size ( ) , K - 1 ) ; total_case += mod ; total_case %= mod ; m . add ( lines . get ( i ) [ 1 ] ) ; } System . out . println ( total_case ) ; } static void preCompute ( ) { long fact = 1 ; factorial [ 0 ] = 1 ; inverse [ 0 ] = 1 ; for ( int i = 1 ; i < MAXN ; i ++ ) { fact = ( fact * i ) % mod ; factorial [ i ] = fact ; inverse [ i ] = power ( factorial [ i ] , mod - 2 ) ; } } public static void main ( String [ ] args ) { int N = 3 , K = 2 ; ArrayList < int [ ] > lines = new ArrayList < > ( ) ; preCompute ( ) ; lines . add ( new int [ ] { 1 , 3 } ) ; lines . add ( new int [ ] { 4 , 5 } ) ; lines . add ( new int [ ] { 5 , 7 } ) ; numberOfWays ( lines , K , N ) ; } }