Question: Goldman Sachs OA | MANIT Bhopal | Summer Analyst | 2023 | Marble and Students | Hackathon Friends
0
Entering edit mode

0
Entering edit mode

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

ADD COMMENTlink 15 months ago Systumm • 200
Entering edit mode
0
as number of marbles is upto 10^10, can you please elaborate how to avoid tle while reducing elements
ADD REPLYlink 15 months ago
pj_24
• 10
Entering edit mode
0

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--;

}

}

}

 

ADD REPLYlink 15 months ago
Ritik Raj Yadav
• 0
0
Entering edit mode

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.

ADD COMMENTlink 15 months ago Harsh • 0

Login before adding your answer.

Similar Posts
Loading Similar Posts