HackerRank Solutions by Rishabh

Restaurant

Problem at https://www.hackerrank.com/challenges/restaurant/problem

Martha is interviewing at Subway. One of the rounds of the interview requires her to cut a bread of size into smaller identical pieces such that each piece is a square having maximum possible side length with no left over piece of bread.

Input Format

The first line contains an integer . lines follow. Each line contains two space separated integers and which denote length and breadth of the bread.

Constraints

Output Format

lines, each containing an integer that denotes the number of squares of maximum size, when the bread is cut as per the given condition.

Sample Input 0

2
2 2
6 9

Sample Output 0

1
6

Explanation 0

The 1^st testcase has a bread whose original dimensions are , the bread is uncut and is a square. Hence the answer is 1.
The 2^nd testcase has a bread of size . We can cut it into 54 squares of size , 6 of size . For other sizes we will have leftovers. Hence, the number of squares of maximum size that can be cut is 6.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    /*
     * Complete the restaurant function below.
     */
    static int restaurant(int l, int b) {
        List<Integer> factors = factorsOf(l);
        int op = 1;
        for(int i:factors) {
            if(b%i==0) {
                op=i;
            }
        }
        return (l*b)/(op*op);
    }
    private static List<Integer> factorsOf(int l) {
        // TODO Auto-generated method stub
        List<Integer> op = new ArrayList<Integer>();
        op.add(1);
        for(int i=2;i<=l/2;i++) {
            if(l%i==0) {
                op.add(i);
            }
        }
        op.add(l);
        return op;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

        for (int tItr = 0; tItr < t; tItr++) {
            String[] lb = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

            int l = Integer.parseInt(lb[0]);

            int b = Integer.parseInt(lb[1]);

            int result = restaurant(l, b);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Sparse Arrays

There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results.

Example

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the matchingStrings function below.
    static int[] matchingStrings(String[] strings, String[] queries) {
        int[] op = new int[queries.length];
        for(int j=0;j<queries.length;j++) {
            int count = 0;
            for(String s:strings) {
                if(queries[j].equals(s)) {
                    count++;
                }
            }
            op[j]=count;
        }
        return op;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int stringsCount = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        String[] strings = new String[stringsCount];

        for (int i = 0; i < stringsCount; i++) {
            String stringsItem = scanner.nextLine();
            strings[i] = stringsItem;
        }

        int queriesCount = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        String[] queries = new String[queriesCount];

        for (int i = 0; i < queriesCount; i++) {
            String queriesItem = scanner.nextLine();
            queries[i] = queriesItem;
        }

        int[] res = matchingStrings(strings, queries);

        for (int i = 0; i < res.length; i++) {
            bufferedWriter.write(String.valueOf(res[i]));

            if (i != res.length - 1) {
                bufferedWriter.write("\n");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Array Manipulation

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.

Example

Queries are interpreted as follows:

Add the values of between the indices and inclusive:

index->	 1 2 3  4  5 6 7 8 9 10
	[0,0,0, 0, 0,0,0,0,0, 0]
	[3,3,3, 3, 3,0,0,0,0, 0]
	[3,3,3,10,10,7,7,7,0, 0]
	[3,3,3,10,10,8,8,8,1, 0]

The largest value is after all operations are performed.

Function Description

Complete the function arrayManipulation in the editor below.

arrayManipulation has the following parameters:

int n – the number of elements in the array
int queries[q][3] – a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.

Returns

int – the maximum value in the resultant array

Input Format

The first line contains two space-separated integers n and m , the size of the array and the number of operations.
Each of the next lines contains three space-separated integers a, b and k , the left index, right index and summand.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
import java.util.Map.Entry;

public class Solution {

    // Complete the arrayManipulation function below.
    static long arrayManipulation(int n, int[][] queries) {
        long op=0;
        Map<Long,Long> map = new HashMap<>();
        for(int i=0;i<queries.length;i++) {
            long a=queries[i][0];
            long b=queries[i][1];
            long k=queries[i][2];
            map.put(a, ((map.containsKey(a)?map.get(a):0)+k));
            map.put(b+1, ((map.containsKey(b+1)?map.get(b+1):0)-k));
        }
        long incremented=0;
        for(long i=0;i<n;i++) {
            incremented += (map.containsKey(i + 1) ? map.get(i + 1) : 0);
            op = Math.max(op, incremented);
        }
        return op;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nm = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nm[0]);

        int m = Integer.parseInt(nm[1]);

        int[][] queries = new int[m][3];

        for (int i = 0; i < m; i++) {
            String[] queriesRowItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int j = 0; j < 3; j++) {
                int queriesItem = Integer.parseInt(queriesRowItems[j]);
                queries[i][j] = queriesItem;
            }
        }

        long result = arrayManipulation(n, queries);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Balanced Brackets

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].

Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

By this logic, we say a sequence of brackets is balanced if the following conditions are met:

It contains no unmatched brackets.
The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

Given a strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, return YES. Otherwise, return NO.

Function Description

Complete the function isBalanced in the editor below. It must return a string: YES if the sequence is balanced or NO if it is not.

isBalanced has the following parameter(s):

s: a string of brackets

Input Format

The first line contains a single integer , the number of strings.
Each of the next lines contains a single string , a sequence of brackets.

Solution In Java:

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the isBalanced function below.
    static String isBalanced(String s) {
        String output ="NO";
        Stack<Character> balancer = new Stack<Character>();
        for(int i=0;i<s.length();i++) {
            if(s.charAt(i)=='(' || s.charAt(i)=='{' || s.charAt(i)=='[') {
                balancer.push(s.charAt(i));
            }else {
                char closed = s.charAt(i);
                if(!balancer.isEmpty()) {
                    char opened = balancer.pop();
                    boolean matched = matchChars(closed,opened);
                    if(!matched) {
                        return "NO";
                    }
                }else {
                    return "NO";
                }
            }
        }
        if(balancer.isEmpty()) {
            output = "YES";
        }
        return output;
    }
     private static boolean matchChars(char closed, char opened) {
        if(closed == ')' && opened == '(') {
            return true;
        }else if(closed == '}' && opened == '{') {
            return true;
        }else if(closed == ']' && opened == '[') {
            return true;
        }
        return false;
    }
    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            String s = scanner.nextLine();

            String result = isBalanced(s);

            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}