Codigo - 2016, CDGO1601 - Editorial

PROBLEM LINK :

Contest
Practice

Editorialist: Atul Gupta

DIFFICULTY:

Cakewalk.

PREREQUISITES:

Basic Knowledge.

PROBLEM:

Given a rectangle L x B, take out largest possible square. Repeat this process n times check if this is possible or not.

QUICK EXPLANATION:

  1. Take the the sides of rectangle.
  2. Largest possible square will be of smaller of the two side.
  3. New rectangle will be of side (larger-smaller) x (smaller).

EXPLANATION:

First thing to observe is that largest possible square will be of length smaller side. For eg. if cake is of dimension 5 X 3, then we can take out square of 1 x 1, 2 x 2 and 3 x 3 but we cannot take out square of 4 x 4 because for being square maximum allowed side is 3.

So, to repeat this process we can define a function and call it recursively n time. The function will contain three parameters both the sides L,B and repetition left. Pseudo code is as follows.


func (l,b,n) {
 if(l==0 || b==0 || n==0) {
  return l*b
 }
 newL=max(l,b)-min(l,b)
 newB=min(l,b)
 return func(newL,newB,n-1)
}

Now for Base Case, either l or b should be zero since it cannot be divided further. Or repetition left is zero. See if any of the side is zero ans will be zero and if n is zero ans will be area of rectangle left, hence we can check if any cake is remaining or not.

For implementation of this code kindly check author’s solution.

Another solution to this will be Iterative approach, this is left as an exercise for user :slight_smile:
Have Fun
Keep Coding.

AUTHOR’S SOLUTIONS:

Author’s Solution

1 Like

This is my iterative approach in python… :slight_smile:
Had a great experience participating in the contest. Looking forward to Codigo’s next round… :slight_smile:

2 Likes

Good job… keep it up.

//