• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

July 10, 2014 by Dhaval Dave

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles.

You have a rectangular chocolate bar that consists of width x height square tiles. You can split it into two rectangular pieces by creating a single vertical or horizontal break along tile edges. For example, a 2×2 chocolate bar can be divided into two 2×1 pieces, but it cannot be divided into two pieces, where one of them is 1×1. You can repeat the split operation as many times as you want, each time splitting a single rectangular piece into two rectangular pieces.
Your goal is to create at least one piece which consists of exactly nTiles tiles. Return the minimal number of split operations necessary to reach this goal. If it is impossible, return -1.

Complete the function getMinSplit, which takes in 3 integers as parameters. The first parameter is width of the chocolate, the second is height of the chocolate and third is nTiles, the number of tiles required.

Constraints
– width will be between 1 and 109, inclusive.
– hight will be between 1 and 109, inclusive.
– nTiles will be between 1 and 109, inclusive.

Example 1 Example 2 Example 3 Example 4 Example 5
5  12 2 17 226800000
4  10 2 19 10000000
12 120 1 111 938071715
Returns: 1 Returns: -1 Returns: 2 Returns: -1 Returns: 1
ANSWER
Logic :
First Try to understand that
Answers can be only
-1 ( not possible )
1 (in only one cut)
2 (in two cut – One Horizontally and One Vertically )
Why max 2  ? Think Its very easy. (as we have only 2D)
for 3D cube Max can be 3. :P Now you got ?
Now
With Following Algorithm code is very easy every one can write ..
W = No Width
H = No Height

nT = nTiles given..

Thanks to Dhaval for suggesting this approach and code

#include <iostream>
#include <stdio.h>
 
inline int minimum (int a, int b) { return a < b ? a : b; }
int fact[100]={0};
void getFactors(int n){
	int i,j=0;
	for (i=2;i<n;i++){
		 if(n%i==0) {
			fact[j]=i;
			j++;
		 }
	}//for
	printf("factors");
	i=0;
	while(fact[i]>0){
		 printf(" %d ",fact[i]);
		 i++;
	}
}//getFactor
int getMinTiles( int width , int height, int nTiles)
{
	int w=width;
	int h=height;
	int n=nTiles;
	int i,j,l,fact1,fact2;
	int min=10; //min any number greater thn 2 


	if( w*h <= n ) return -1; 
	// w*h total number of tiles are more or equal to required, return -1

	getFactors(n);
	//store all factors of a nTiles except 1 and nTiles.
	i=l=0;
	while(fact[i]>0){
		 i++;
	}//while
	l=i;
	printf("nLength - %d ",l);
	//l = length(fact);

	//for each pair of factors
	for (i=0,j=l ; i <=j ; i++,j--)
	{
		fact1=fact[i];
		fact2=fact[j];

		if ( fact1 == w && fact2 < h ) {min = 1;}
		else if ( fact2 == h && fact1 < w )  {min = 1;}

		// eg : fact1=4,fact2=3 ; h=4 ,w=5 , n=12;
		// When row or col number are matching with width or column , with only one cut we can produce desired result.
		// if another fact is smaller than column or width (opposite)

		else if ( (fact1 < w && fact1 < h) ||  (fact2 < w && fact2 < h) )  
		{ min = minimum (min, 2); }
		// both factors are very small then height and width then 2 cut are required one horizontally and one vertically) 

		else { min = 0;}

	}//for 

	return min;

}//Function
 
int main() {
	 int cut;
	 cut = getMinTiles( 5, 4, 18);
	 printf("nNumber of cut required %d ",cut);
	 return 0;
}

You can check it at http://ideone.com/tvR7yx

Similar Articles

Filed Under: Array, Flipkart Interview Questions, Hacker Earth Questions, Interview Questions, problem Tagged With: Array, Mathematical

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Find next greater number with same set of digits

TicTacToe Game As Asked in Flipkart

Fibonacci Hashing & Fastest Hashtable

HackeEarth Flipkart’s Drone

Generate largest number arranging a no. of given non negative integer numbers

25 horses 5 tracks Find 3 fastest puzzle

Code Chef PRGIFT Solution

How strtok() Works

Adobe Interview Questions 8 month Exp

strtok()

Python Array String

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

Find min element in Sorted Rotated Array (Without Duplicates)

Find and print longest consecutive number sequence in a given sequence in O(n)

Print vertical sum of all the axis in the given binary tree

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

Generic Object Oriented Stack with Template

Wrong Directions given find minimum moves so that he can reach to the destination

Memory Efficient LinkedList

Advanced SQL Injection

C++ OOPs Part1

Level order traversal in Spiral form

Trie Dictionary

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

SAP Off Campus Hiring_ March 2015 Sample Questions

Given a string, find the first character which is non-repetitive

C++ OOPs Part2

K’th Largest Element in BST when modification to BST is not allowed

Copyright © 2025 · Genesis Framework · WordPress · Log in