Dynamic Programming HACKER EARTH questions

Here we will see HACKER EARTH and HACKER RANK dynamic coding questions asked in various off campus recruitments.

Question: MAXIMUM PRODUCT

You are given an array A of size N

You are given Q queries of the following form

  • 1LR: Find the maximum product of “two integers” in the sub array starting from index L and ending at index R (L and R inclusive)
  • 2LR: Find the maximum product of “three integers” in the sub array starting from index L and Ending at index R (L and R inclusive).

Task:

print the required maximum product for each type of query.

Example:

Assumptions

  • T=1
  • N=5
  • Q=2
  • A={1,3,4,-2,5}
  • queries=[{1,1,3},{2,3,5}]

Approach:

  • The subarray for the first query is [1,3,4] as the query is of the first type you need to find the maximum product of two integers. The only possible products are 3(1*3), 12(3*4) and 4(1*4). Here as 12 is the maximum possible product so 12 is the output for first sub query.
  • The subquery for second query is [4,-2,5] as the query is of the second type. we need to find the maximum product of “three integers “. The only possible roduct is -40 (4*(-2)*5) so the output will be -40
image
Hacker Earth Coding Question
Hacker Earh Coding Question

Function Discription:

  • N represents the length of the array A
  • Q represents the number of queries
  • A represents the given array
  • Queries : represents the queries array , where each query contains 3 elements
    1. The first integer is either 1 or 2, where 1 is denoting query of the first type and 2 is denoting the query of second type
    2. The second integer represents the starting index L of the subarray
    3. The third intger represents the ending index of the subarray.

Example2:

Input:

N=5

Q=3

A={2,4,-2,-2,3,7}

Queries=[{1,4,6},{2,3,5},{1,2,3}]

Output:

21

12

-8

Approach: It remains same as that of the previous example.

Alogorithm to solve

  1. Initially take all inputs from user like value of N,Q, array A and Queries array.
  2. Use 2 for loops for iterating through elements of 2D aray
  3. First check if the first value in first sub query is 1 or not. If it is 1 then,
  4. create an ARRAYLIST <Integer> of type integers starting from index mentioned in problem and ending at specified index
  5. then sort the arraylist in “Decending order
  6. Then print the product of first two elements as answer.
  7. If the first element in sub query is 2 then,
  8. create an ARRAYLIST of integer types starting from index mentioned in problem and ending at specified index
  9. then sort the arraylist in “Decending order
  10. Then print the product of first three elements as answer.

JAVA CODE

package arrayproblems;
import java.util.*;
class Problem23 {
	public static void main(String[] args) {
		
		
		// Code by VRASHIKESH PATIL 
		
		int N=5;
		int Q=3;
		int[] array1= {2,4,-2,-2,3,7};
		int[][]	array2= {{1,4,6},{2,3,5},{1,2,3}};
		
		for(int i=0;i<array2.length;i++) {
			
			for(int j=0;j<array2[i].length;j++) {
				
				if(array2[i][j]==1) {
					ArrayList<Integer> array3=new ArrayList<Integer>();
					
					
					for(int k=array2[i][j+1]-1;k<array2[i][j+2];k++) {
						
						array3.add(array1[k]);
					}
					
					Collections.sort(array3,Collections.reverseOrder());
					System.out.println(array3.get(0)*array3.get(1));
					break;
				}
				else if(array2[i][j]==2) {
					ArrayList<Integer> array3=new ArrayList<Integer>();
					for(int k=array2[i][j+1]-1;k<array2[i][j+2];k++) {
						array3.add(array1[k]);
						
					}
					Collections.sort(array3,Collections.reverseOrder());
					System.out.println(array3.get(0)*array3.get(1)*array3.get(2));
					break;
				}	
			}
		}
	}	
}

Watch Step by Step Explanation for Above Code on our Channel

Similar Off Campus Coding Problems

APPSIAN off Campus Coding Question

Maximum Work Hacker Earth Problem solved

Count Buildings Hacker Earth coding question with solution

SHL off campus coding questions

Beginner’s friendly top 5 array questions in java

4 thoughts on “Dynamic Programming HACKER EARTH questions”

  1. Pingback: What is Jagged Array In Java - Is It Actually

  2. Pingback: Off Campus Coding Question on Arrays - Is It Actually

  3. Pingback: Finding all substrings of given string in JAVA - Is It Actually

  4. The way you write make it truly trouble-free to read. And the theme you use, wow. It really is a really good combination. And I am wondering what is the name of the theme you use?

Leave a Comment

Your email address will not be published. Required fields are marked *