Checking if any Square (With One Colored Cell) can be Divided into Two Equal Parts in Java

Given a square of size n. Within the square n, there are n² little squares of size 1 unit each, each of which is colored. Our goal is to divide the square n into two equal halves. The cutting line should have no points in common with the colored cell, and the resulting two sections should be equal up to rotation. Print "YES" if it is possible to cut the square under these conditions. Else, print it as "NO."

Note: The value of n should be an even positive value at all times.

Example 1:

Input:

int num = 4, x = 1, y = 1

Output:

Yes, square can be divided into two equal parts.

Explanation:

The painted square in the above example has a coordinate of 1 x 1. As a result, we must divide the larger square into two sections so there is no common point with the colored cell. The bold line in the above image divides the square into two equal pieces.

Naïve Approach:

Algorithm:

The following is a step-by-step algorithm for solving this problem:

Step – 1: Set the size of the square as well as the position of the coloured square to zero.

Step – 2: We can only divide a square into two equal parts if the cutting line passes through the center of our larger square.

Step – 3: If the painted square is related to the centre of the larger square in any way, cutting the larger square into two equal halves is impossible.

Step – 4: To check, divide the larger square's size in half and see if any of the dimensions of a colored square is connected to it.

Implementation:

FileName: SquareColor.java

import java.io.*;

import java.util.*;

public class SquareColor

{

    // method to determine whether it is possible to divide

    // the square into two equal portions

    static void squarehalf(int num, int x, int y)

    {

            int half = num / 2;

            // It is not possible if the painted square is related

            // to the center of the square in any way.

            if ((half == x || half == x - 1) && (half == y || half == y - 1))

                        System.out.println( "No, Square can be divided into two equal parts.");

            // Otherwise, certainly, it is possible.

            else

                        System.out.println( "Yes, Square can be divided into two equal parts.");

    }

    public static void main (String[] args)

    {

        int num = 4;

        int x = 1;

        int y = 1;

         squarehalf(num, x, y);

      }

}

Output:

Yes, square can be divided into two equal parts.

Complexity Analysis:

The time complexity for the above program is O(1) as it performs constant operations, and the space complexity is given by O(1), which is also constant.