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 onHence, every N >= 6 is proved Squarable.
Below is the implementation for the above approach:
C++
// C++ approach for the above problem:#include <iostream>using namespace std;// Function to find a number is// Squarable or notvoid 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;}// Drivers codeint main(){ int N; isSquarable(1); isSquarable(4); isSquarable(5); isSquarable(6); isSquarable(100); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { // Java approach for the above problem: // Function to find a number is // Squarable or not static void isSquarable(int N) { if (N < 6) { if (N == 1 || N == 4) System.out.println("YES, " + N + " is a Squarable Number"); else System.out.println("NO, " + N +" is not a " + "Squarable Number"); } else System.out.println("YES, " + N + " is a Squarable Number"); } // Driver Code public static void main(String args[]) { int N; isSquarable(1); isSquarable(4); isSquarable(5); isSquarable(6); isSquarable(100); }}// This code is contributed by shinjanpatra |
Python3
# Python approach for the above problem:# Function to find a number is# Squarable or notdef isSquarable(N): if (N < 6): if (N == 1 or N == 4): print(f"YES {N} is a Squarable Number"); else: print(f"NO {N} is not a Squarable Number"); else: print(f"YES {N} is a Squarable Number");# Drivers codeisSquarable(1);isSquarable(4);isSquarable(5);isSquarable(6);isSquarable(100); # This code is contributed by Saurabh Jaiswal |
C#
// C# program to check if N is a Squarable Number or not.using System;public class GFG{ // Function to find a number is // Squarable or not static void isSquarable(int N) { if (N < 6) { if (N == 1 || N == 4) Console.Write("YES, " + N + " is a Squarable Number\n"); else Console.Write("NO, " + N +" is not a " + "Squarable Number\n"); } else Console.Write("YES, " + N + " is a Squarable Number\n"); } // Driver Code static public void Main (){ isSquarable(1); isSquarable(4); isSquarable(5); isSquarable(6); isSquarable(100); }}// This code is contributed by shruti456rawal |
Javascript
// JavaScript approach for the above problem:// Function to find a number is// Squarable or notfunction isSquarable(N){ if (N < 6) { if (N == 1 || N == 4) console.log("YES, "+N+" is a Squarable Number"); else console.log("NO, "+N+" is not a Squarable Number"); } else console.log("YES, "+N+" is a Squarable Number");}// Drivers code isSquarable(1); isSquarable(4); isSquarable(5); isSquarable(6); isSquarable(100); // This code is contributed by Ishan Khandelwal |
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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
