Queries to count groups of N students possible having sum of ratings within given range | Java program for the above approach ; Function to count number of ways to get given sum groups ; Initialise dp array ; Mark all 1 st row values as 1 since the mat [ 0 ] [ i ] is all possible sums in first row ; Fix the ith row ; Fix the sum ; Iterate through all values of ith row ; If sum can be obtained ; Find the prefix sum of last row ; Traverse each query ; No of ways to form groups ; Driver Code ; Given N batches and K students ; Given ratings ; Given Queries ; Function Call
import java . util . * ; public class Main { public static void numWays ( int [ ] [ ] ratings , int queries [ ] [ ] , int n , int k ) { int dp [ ] [ ] = new int [ n ] [ 10000 + 2 ] ; for ( int i = 0 ; i < k ; i ++ ) dp [ 0 ] [ ratings [ 0 ] [ i ] ] += 1 ; for ( int i = 1 ; i < n ; i ++ ) { for ( int sum = 0 ; sum <= 10000 ; sum ++ ) { for ( int j = 0 ; j < k ; j ++ ) { if ( sum >= ratings [ i ] [ j ] ) dp [ i ] [ sum ] += dp [ i - 1 ] [ sum - ratings [ i ] [ j ] ] ; } } } for ( int sum = 1 ; sum <= 10000 ; sum ++ ) { dp [ n - 1 ] [ sum ] += dp [ n - 1 ] [ sum - 1 ] ; } for ( int q = 0 ; q < queries . length ; q ++ ) { int a = queries [ q ] [ 0 ] ; int b = queries [ q ] [ 1 ] ; System . out . print ( dp [ n - 1 ] [ b ] - dp [ n - 1 ] [ a - 1 ] + " ▁ " ) ; } } public static void main ( String args [ ] ) { int N = 2 , K = 3 ; int ratings [ ] [ ] = { { 1 , 2 , 3 } , { 4 , 5 , 6 } } ; int queries [ ] [ ] = { { 6 , 6 } , { 1 , 6 } } ; numWays ( ratings , queries , N , K ) ; } }