Q1. in first question we can find sum of array and check is sum<=M then return 0 else we will push all eleme`nt into maxHeap and make all element as low as possible
can you provide code i was thinking of recursion like this but it will give tle
import java.util.*;
public class a1marbleandstu {
public static int find(int arr[], int ind, int m, int dp[]){
if(ind>=arr.length){
return 0;
}
if(m==0){
return (int)1e9;
if(dp[ind]!=-1){
return dp[ind];
int a = (int)1e9;
for(int i=0; i<=m; i++){
a = Math.min(a, (int)Math.pow(Math.abs(arr[ind]-i),2 ) + find(arr,ind+1, m-i, dp));
return a;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t>0){
int m = sc.nextInt();
int n = sc.nextInt();
int arr[] = new int[n];
int dp[] = new int[n+1];
Arrays.fill(dp, -1);
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
System.out.println(find(arr, 0, m, dp));
t--;
Q2. Graph problem : It canbe simply solved using dfs in which we will calculate size of each separate component and can update the minsiz and maxsiz.
Login before adding your answer.
can you provide code i was thinking of recursion like this but it will give tle
import java.util.*;
public class a1marbleandstu {
public static int find(int arr[], int ind, int m, int dp[]){
if(ind>=arr.length){
return 0;
}
if(m==0){
return (int)1e9;
}
if(dp[ind]!=-1){
return dp[ind];
}
int a = (int)1e9;
for(int i=0; i<=m; i++){
a = Math.min(a, (int)Math.pow(Math.abs(arr[ind]-i),2 ) + find(arr,ind+1, m-i, dp));
}
return a;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t>0){
int m = sc.nextInt();
int n = sc.nextInt();
int arr[] = new int[n];
int dp[] = new int[n+1];
Arrays.fill(dp, -1);
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
System.out.println(find(arr, 0, m, dp));
t--;
}
}
}