Squarable Numbers - Coding

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++

// C++ approach for the above problem:
 
#include <iostream>
using namespace std;
 
// Function to find a number is
// Squarable or not
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;
}
 
// Drivers code
int 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 not
def 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 code
isSquarable(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 not
function 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

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)

Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Maximum cells attacked by Rook or Bishop in given Chessboard
Check if Array can be generated where no element is Geometric mean of neighbours
Minimum divisions to reduce N to 1 by following given conditions
Minimum cost to convert 1 to N by multiplying X or right rotation of digits
Find two pairs such that one's GCD is same as other's LCM and sum equal to N

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	16