Algorithm


Problem Name: Mathematics - Restaurant

Problem Link: https://www.hackerrank.com/challenges/restaurant/problem?isFullScreen=true

In this HackerRank in Mathematics - Restaurant solutions,

Martha is interviewing at Subway. One of the rounds of the interview requires her to cut a bread of size l * b 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 T.T lines follow. Each line contains two space separated integers l and b which denote length and breadth of the bread.

Constraints

  • 1 <= T <= 1000
  • 1 <= l,b <= 1000

Output Format

T 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 1st testcase has a bread whose original dimensions are 2 * 2 , the bread is uncut and is a square. Hence the answer is 1.
The 2nd testcase has a bread of size 6 * 9 . We can cut it into 54 squares of size 1 * 1 , 6 of size 3 * 3 . For other sizes we will have leftovers. Hence, the number of squares of maximum size that can be cut is 6.

 

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int gcd ( int a, int b )
{
  int c;
  while ( a != 0 ) {
     c = a; a = b%a;  b = c;
  }
  return b;
}

int main(){
    int testcases;
    scanf("%d", &testcases);
    int i;
    for(i = 0; i  <  testcases; i++){
        int l;
        int b;
        scanf("%d %d", &l, &b);
        printf("%d\n", (l/gcd(l,b)*b/gcd(l,b)));
    }
    return 0;
}

Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector < string> split(const string &);

/*
 * Complete the 'restaurant' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER l
 *  2. INTEGER b
 */

int gcd(int a, int b)
{
    if(a == 0)
      return b;
    else
      return gcd(b % a, a);  
}
int restaurant(int l, int b) {
    int area = l * b;
    int bread = area / (gcd(l, b) * gcd(l, b));
    return bread;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string t_temp;
    getline(cin, t_temp);

    int t = stoi(ltrim(rtrim(t_temp)));

    for (int t_itr = 0; t_itr < t; t_itr++) {
        string first_multiple_input_temp;
        getline(cin, first_multiple_input_temp>;

        vector < string> first_multiple_input = split(rtrim(first_multiple_input_temp));

        int l = stoi(first_multiple_input[0]);

        int b = stoi(first_multiple_input[1]);

        int result = restaurant(l, b);

        fout << result << "\n";
    }

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun < int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun < int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector < string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'restaurant' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER l
     *  2. INTEGER b
     */

    public static int restaurant(int l, int b) {
        for(int i=2;i < =Math.min(l,b);i++){
            if(l==1||b==1)break;
            if(l%i==0&&b%i==0){
                l/=i; b/=i;
                i--;
            }
        }
        return l*b;
    }

}

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

        int t = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, t).forEach(tItr -> {
            try {
                String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

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

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

                int result = Result.restaurant(l, b);

                bufferedWriter.write(String.valueOf(result));
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Python Programming

Code - Python Programming


#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'restaurant' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER l
#  2. INTEGER b
#

def restaurant(l, b):
    # Write your code here
    tot = l * b
    m = min(l, b)
    pl = []
    i = 1
    mid = m // i
    while mid > 1:
        if m % mid == 0:
            pl.append(mid)
        i += 1
        while mid == m // i:
            i += 1
        mid = m // i
    for i in pl:
        if l % i == 0 and b % i == 0:
            x = i ** 2
            if tot % x == 0:
                return tot // x
    return tot

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        first_multiple_input = input().rstrip().split()

        l = int(first_multiple_input[0])

        b = int(first_multiple_input[1])

        result = restaurant(l, b)

        fptr.write(str(result) + '\n')

    fptr.close()

Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Best Divisor solution in Hackerrank - Hacerrank solution C++, java, Python
Next
[Solved] Reverse Game solution in Hackerrank - Hacerrank solution C, C++, C#, java, js, Python