Hello Programmers/Coders, Today we are going to share solutions of Programming problems of HackerRank, Algorithm Solutions of Problem Solving Section in Java. At Each Problem with Successful submission with all Test Cases Passed, you will get an score or marks. And after solving maximum problems, you will be getting stars. This will highlight your profile to the recruiters.
In this post, you will find the solution for Cutting Boards in Java-HackerRank Problem. We are providing the correct and tested solutions of coding problems present on HackerRank. If you are not able to solve any problem, then you can take help from our Blog/website.
Use “Ctrl+F” To Find Any Questions Answer. & For Mobile User, You Just Need To Click On Three dots In Your Browser & You Will Get A “Find” Option There. Use These Option to Get Any Random Questions Answer.
Introduction To Algorithm
The word Algorithm means “a process or set of rules to be followed in calculations or other problem-solving operations”. Therefore Algorithm refers to a set of rules/instructions that step-by-step define how a work is to be executed upon in order to get the expected results.
Advantages of Algorithms:
- It is easy to understand.
- Algorithm is a step-wise representation of a solution to a given problem.
- In Algorithm the problem is broken down into smaller pieces or steps hence, it is easier for the programmer to convert it into an actual program.
Link for the Problem – Cutting Boards – Hacker Rank Solution
Cutting Boards – Hacker Rank Solution
Problem:
Alice gives Bob a board composed of wooden squares and asks him to find the minimum cost of breaking the board back down into its individual squares. To break the board down, Bob must make cuts along its horizontal and vertical lines.
To reduce the board to squares, Bob makes horizontal and vertical cuts across the entire board. Each cut has a given cost, or for each cut along a row or column across one board, so the cost of a cut must be multiplied by the number of segments it crosses. The cost of cutting the whole board down into squares is the sum of the costs of each successive cut.
Can you help Bob find the minimum cost? The number may be large, so print the value modulo .
For example, you start with a board. There are two cuts to be made at a cost of for the horizontal and for the vertical. Your first cut is across piece, the whole board. You choose to make the horizontal cut between rows and for a cost of . The second cuts are vertical through the two smaller boards created in step between columns and . Their cost is . The total cost is and .
Function Description
Complete the boardCutting function in the editor below. It should return an integer.
boardCutting has the following parameter(s):
- cost_x: an array of integers, the costs of vertical cuts
- cost_y: an array of integers, the costs of horizontal cuts
Input Format
The first line contains an integer , the number of queries.
The following sets of lines are as follows:
- The first line has two positive space-separated integers and , the number of rows and columns in the board.
- The second line contains space-separated integers cost_y[i], the cost of a horizontal cut between rows and of one board.
- The third line contains space-separated integers cost_x[j], the cost of a vertical cut between columns and of one board.
Constraints
Output Format
For each of the queries, find the minimum cost () of cutting the board into squares and print the value of .
Sample Input 0
1 2 2 2 1
Sample Output 0
4
Explanation 0
We have a board, with cut costs and . Our first cut is horizontal between and , because that is the line with the highest cost (). Our second cut is vertical, at . Our first cut has a of because we are making a cut with cost across segment, the uncut board. The second cut also has a of but we are making a cut of cost across segments. Our answer is .
Sample Input 1
1 6 4 2 1 3 1 4 4 1 2
Sample Output 1
42
Explanation 1
Cutting Boards – Hacker Rank Solution
import java.util.*;
public class Solution {
static int N;
static int[] array;
static long INF = Long.MAX_VALUE;
static long mod = 1000000007;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
while(T-- != 0) {
int m = in.nextInt();
int n = in.nextInt();
int[] y = new int[m];
int[] x = new int[n];
for(int i=1; i<m; i++) y[i] = in.nextInt();
for(int i=1; i<n; i++) x[i] = in.nextInt();
Arrays.sort(y);
Arrays.sort(x);
int i = 1;
int j = 1;
long count = 0;
while(i < n || j < m) {
long valX = -1;
long valY = -1;
if(i < n) valX = x[n-i];
if(j < m) valY = y[m-j];
if(valX > valY) {
count = (count + j*valX)%mod;
i++;
} else {
count = (count + i*valY)%mod;
j++;
}
}
System.out.println(count);
}
}
}
