Reducing Dishes coding Complete solution

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.

**Reducing Dishes Problem with solution**

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

Watch Now

Similar off campus coding question with solution

Count number of palindrome words in given sentance

Saddle points in 2D array off campus problem solved

Hacker Earth Coding Question with Solution

Hacker Rank Off Campus Coding Question Solved