Squarable Numbers

Given a positive integer N, the task is to check if N is a Squarable Number or not.

An integer “N” is said to be Squarable, if we can divide a square into N non-overlapping Squares (not necessarily of same size).

Examples:

Input: N = 1
Output: “YES, 1 is a squarable Number”
Explanation: Any Square satisfies this case.

1 is a Squarable Number 

Input: N=4
Output: “YES, 4 is a Squarable Number”
Explanation: A Square can be Divided into 4 Squares.

4 is a Squarable Number

Input: N=5
Output: “NO, 5 is not a Squarable Number”
Explanation: Any Square cannot be Divided into 5 Squares.

Input: N=6 
Output: “YES, 6 is a Squarable Number”
Explanation: A Square can be divided into 6 Squares.

6 is a Squarable Number

Approach: On the basis of below mentioned observations, it is possible to figure out that a number is squarable or not:

Observation:

The Trick to catch here is that every positive Integer N >= 6, will surely be Squarable.

  • This can be proved by Inductive Hypothesis. Let’s see how. 
  • Before proceeding to Proof By Induction, let us see how numbers 7 and 8 are Squarable (Number 6 is Squarable which we have already seen in Examples above). Numbers 6, 7 and 8 will become the base Cases for Proving By Induction.

Number 7 is Squarable in Following way:

7 is a Squarable Number

Number 8 is Squarable in Following way:

8 is a Squarable Number

Base Cases:

We have already seen that N = 6, 7, 8 are Squarable and Hence our Base Case is Proved.

Proof By Induction:

Let us Assume that the Numbers “K”, “K – 1” and “K – 2” are squarable where K >= 8. Now, Let us see how “K + 1” will also be squarable by Induction.

We Know,

 (K – 2) + 3 = (K + 1)

Therefore, If it is possible to form 3 more squares in “(K – 2)” which is a squarable Number, then we can say “K + 1” is also squarable. Forming 3 more squares in a square is easy. This can be achieved just by Dividing the Square into 4 small Squares from centre. 

Example Below:

Forming 3 Extra Squares in any Given Square

One Square is Divided into 4 Squares, thus 3 new squares are formed. Hence, conclusively, it is proved that if “K – 2” is Squarable, then “K+1” is also Squarable.

Inductive Hypothesis:

Therefore, by Induction, we can say that our 3 base Cases (N = 6, 7, 8) are sufficient to prove the hypothesis, because for Proving any Number “X” Squarable, we will be having a Number “X – 3” which is Squarable, and inductively, “X” will also be Squarable (as 3 Squares can be Easily Formed in “X-3” to form “X” Squares).

Finally, we have 6, 7, 8 as Squarable numbers, which means

9 is Also Squarable (as 6 is Squarable, 6+3=9)
10 is Also Squarable (as 7 is Squarable, 7+3=10)
11 is Also Squarable (as 8 is Squarable, 8+3=11)
12 is Also Squarable (as 9 is Squarable, 9+3=12)……and so on

Hence, every N >= 6 is proved Squarable.

Below is the implementation for the above approach:

C++

  

#include <iostream>

using namespace std;

  

void isSquarable(int N)

{

    if (N < 6) {

        if (N == 1 || N == 4)

            cout << "YES, " << N

          << " is a Squarable Number"

                 << endl;

        else

            cout << "NO, " << N 

          << " is not a "

                 << "Squarable Number" << endl;

    }

    else

        cout << "YES, " << N

      << " is a Squarable Number"

             << endl;

}

  

int main()

{

  

    int N;

  

    isSquarable(1);

    isSquarable(4);

    isSquarable(5);

    isSquarable(6);

    isSquarable(100);

  

    return 0;

}
Output

YES, 1 is a Squarable Number
YES, 4 is a Squarable Number
NO, 5 is not a Squarable Number
YES, 6 is a Squarable Number
YES, 100 is a Squarable Number

Time Complexity: O(1)
Auxiliary Space: O(1)

By Julio MarchiPosted on