Friends Pairing Problem | Java soln using mathematical approach ; Returns count of ways n people can remain single or paired up . ; pow of 1 will always be one ; Driver code
import java . util . * ; class GFG { static Vector < Integer > fact ; static void preComputeFact ( int n ) { for ( int i = 1 ; i <= n ; i ++ ) fact . add ( fact . elementAt ( i - 1 ) * i ) ; } static int countFriendsPairings ( int n ) { int ones = n , twos = 1 , ans = 0 ; while ( ones >= 0 ) { ans += fact . elementAt ( n ) / ( twos * fact . elementAt ( ones ) * fact . elementAt ( ( n - ones ) / 2 ) ) ; ones -= 2 ; twos *= 2 ; } return ans ; } public static void main ( String [ ] args ) { fact = new Vector < > ( ) ; fact . add ( 1 ) ; preComputeFact ( 100 ) ; int n = 4 ; System . out . print ( countFriendsPairings ( n ) + "NEW_LINE"); } }