Squarable Numbers | By The Digital Insider

on

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 8is 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 squarablewhere 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, thus3 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)


    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)




#Code, #Mathematical, #SchoolProgramming, #SquareRectangle
Published on The Digital Insider at https://bit.ly/3wZzPA9.

Comments

Post a Comment

Comments are moderated.