Reducing Dishes: Monica has coocked N dishes and collected the data on the level of satisfaction for all the dishes from a guest. The guest returns an array, where the ith element of the array is the liking level of the ith dish, also, the time taken to cook the ith dish is i.
Like-to-time coefficient of a dish is calculated by multiplying the time taken to cook food with it’s liking level. i.e i*input2[i]. Total like-to-time coefficient is calculated by summing up all individual coefficients of dishes.
You want the total like-to-time coefficient to be maximum, you can also remove some dishes, in which a new coefficient is calculated using the left dishes.
Find the maximum sum of all possible like-to-time coefficients.
Input Scpecification:
input1: N, number of dishes
input2: Array representing the liking value of each dish.
Output Specification:
Return maximum like-to-time coefficient possible
Examples:
Example1:
input1: 3
input2: {-1,3,4}
Output: 17
Explanation:
She should not cancel cooking the first dish, since total coefficient without cancelling equals 1(-1) + 2(3) + 3(4) = 17
If she would have cancelled cooking for the first dish, the like-to-time coefficient would be 1(3) + 2(4) = 11
Hence, she should cook all 3 dishes from maximum like-to-time coefficient possible.


Example2:
input1: 5
input2: {-1,-9,0,5,-7}
Output: 14
Explanation:
monica should cancel dishes with like value -9 and -7, then she would be left with the first, third and fourth dishes.
so, the total like-to-time coefficient would be 1(-1) + 2(0)+3(5) = 14
Example3:
input1:6
input2: {-10,-7,-2,-1,0,5,10}
output: 71
Explanation: monica should cancel dish with satisfaction value -10 and the -7(1) + -2(2) + -1(3)+0(4)+ 5(5) +10(6)= 71
Algorithm to solve
Before we start solving the problem first understand the basics of problem
what exactly expected from programmer that is from us
–> Make the like-to-time coefficient as much as possible
–> when negative numbers come in cumulative sum they will reduce the overall sum so try to remove those
–> but one thing is we should not remove all negative numbers as index values is important to increase the overall sum,
–> so after carefull observation we can see that if the negative number is greater than or equal to positive highest number then we should remove that negative number because it will decreasethe overall cumulative sum.
–> at the end all the remaining values will be indexed from left to right again and finally cumulative sum will be calculated.
- First step is to take the value of N, that is number of dishes
- Then in an array take all the satisfaction values for dishes which also indicates the time taken to prepare the dish.
- Now we need to perform remove and add operations, but they cannot be performed on array so, convert given array to array list. This can be done with simple for loop.
- Once we get an array list then sort the array list in ascending order using inbuilt methods present in collections class.
- Now take an variable (in Below code taken as max1 ) whcih will hold the maximum value present in array list.
- Now write a for loop to iterate on array list elements, inside for loop write an if statement with two conditions
- First condition is the current number should be negative, that is compare with zero if it is less than zero then its a negative number.
- The second condition says that the “Absolute value” of negative number should be greater than or equal to highest value in array list (that is max1 value )
- If above two conditions are satisfied then remove the current element from array list (that is removing negative number).
- Now at the end we will be left with few elements, using for loop find the cumulative sum and print is.
- That’s it you just solved one coding quuestion
JAVA Code
package arrayPrograms; import java.util.*; class Problem18 { public static void main(String[] args) { //--- Coded By VRASHIKESH PATIL -----// int[] array1= {-1,3,4}; int max=0; ArrayList<Integer> array2= new ArrayList<Integer>(); // converting array to array list for(int i=0;i<array1.length;i++) { array2.add(array1[i]); } // sorting the Array list in ascending order Collections.sort(array2); // given maximum value in array list int max1=array2.get(array2.size()-1); // checking the conditions as mentioned in above algorithm for(int i=0;i<array2.size();i++) { if(array2.get(i)<0 && (Math.abs(array2.get(i))>=max1)) { array2.remove(i); i=-1; } } // finding cumulative sum for(int i=1;i<=array2.size();i++) { max=max+(i*array2.get(i-1)); } // printing the final answer System.out.println(max); } }
Watch Complete Explanation for above Code here
Similar off campus coding question with solution
Count number of palindrome words in given sentance
Saddle points in 2D array off campus problem solved
Pingback: TCS Off Campus coding question solved - Is It Actually