The Divide and Conquer algorithm (or DAC) solves a huge task or a problem by breaking it into smaller sub-tasks or sub-problems; after solving, we combine all the sub-tasks in a specific manner we get the result for the big task.

Let's see a problem whose solution is based on this algorithm. (Also see Data Strucutres)

Problem Statement

Consider a board of size n*n, where n = 2^k and k>=1. One cell of size 1x1 is missing from the board. The task is to fill the board using L-shaped tiles. An L-shaped tile is like this:

It is a 2x2 board with one 1x1 cell missing.

Input format:

In the input, you will be given the value of n and a 2D array, "board." In the array board, the missing cell has the value -1, and all the other cells have a value of 0.

Output format:

You have to fill the board's cells with numbers such that three cells with the same number are part of one L-shaped tile.

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Solution Approach

This problem is solved using the Divide and conquer approach. The idea is that we can fill a 2x2 board with one missing cell easily. We can place a tile over it because it is an L-shaped board only. Thus, the problem for the 2x2 board is solved. (Refer to the image below)

In the above figure, the black cell is the missing cell, and we fill the rest of the cell using an L-shaped tile, and we're done.

How do we solve the original problem for an nxn size board?

Since n is a power of 2, i.e., n = 2^k (where, k>=1), if we keep dividing the board into smaller boards of half the size of the original board, after some divisions, we can convert the original board into 2^(2k-2) boards of size 2x2.

For example, we divide the below 8x8 board into 16 2x2 boards.

If you notice, this is nothing but Divide and conquer approach. Here, we have a base case (2x2 board by 1 L-shaped tile) whose answer we know, and dividing the original bigger case into smaller cases can help us reach the base case.

One point to focus on is that:

When we divide an nxn board into boards of size (n/2)x(n/2) size, we will get four boards of (n/2)x(n/2) size. But, will these boards be identical?

The answer is no. Because one of the boards will have a missing cell and the others won't have. Since we want four identical boards, we also have to remove one cell from the other three boards. We can do this by placing an L-shaped tile at the centre of the original nxn board such that it doesn't cover the quadrant that contains the missing cell (refer to the image below). Now, all the four boards of size (n/2)x(n/2) will have one missing cell (a cell that doesn't need to be filled).

In this case, we can see that all the four sub-boards have one cell, which we don't need to fill. Thus, all 4 boards are now identical.

By dividing the (n/2)x(n/2) cells further several times similarly, we will get 2x2 boards. Thus, we will be able to solve the whole problem. After filling, the 8x8 board will look like this:

The black cell is the missing cell in the above figure, and the rest of them are filled using L-shaped tiles.

The steps of implementation are:

Input the value of n and the board.

Call the recursive function "func", which fills the board. In the function "func":

Declare variables that will store the row number and column number of the missing cell

Write the base case. The base case is that if n==2, we place an L in the 2x2 board, such that it covers all the three cells which are not filled. We will fill the board with a new tile, thus increasing the tile number by 1. Fill all the tiles other than the missing tile.

Else, find the missing cell's row and column. The cell whose value is -1 is the missing cell.

Now, since we've found the missing cell, we need to fill the other three sub-board quadrants which don't have the missing cell using an L. For doing this, we have another "fill" function.

If the missing tile is in the 1st quadrant, call the fill function for the second, third, and fourth quadrants. This "fill" function fills the corners of the three quadrants using an L. Thus, increase the tile number each time we call it.

If the missing tile is in the third quadrant, call the fill function for the second, first, and fourth quadrants.

If the missing tile is in the second quadrant, call the fill function for the first, third, and fourth quadrants.

If the missing tile is in the fourth quadrant, call the fill function for the second, third, and first quadrants.

Now that we have four sub-boards, call the function "func" for the four sub-boards.

Print the board in the end.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
int tile_number = 0;
// Function to fill the corners of the three sub-boards
// which don't contain the missing cell
void fill(int x1, int y1, int x2, int y2, int x3, int y3, vector<vector<int>> &board)
{
tile_number++;
board[x1][y1] = tile_number;
board[x2][y2] = tile_number;
board[x3][y3] = tile_number;
}
// Function for filling the board
void func(int n, int r, int c, vector<vector<int>> &board)
{
// Declares variables which will store the
// row number and column number of the missing cell
int missing_cell_row, missing_cell_col;
// Base case
// If the board size is 2
if (n == 2)
{
// We will fill the board with a new tile,
// thus increase the tile number by 1
tile_number++;
// Fill all the tiles other than the missing tile
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (board[r + i][c + j] == 0)
{
board[r + i][c + j] = tile_number;
}
}
}
return;
}
else
{
// Find the missing cell's row and column
for (int i = r; i < r + n; i++)
{
for (int j = c; j < c + n; j++)
{
if (board[i][j] != 0)
// The cell whose value is
// not 0 is the missing cell
missing_cell_row = i,
missing_cell_col = j;
}
}
}
// If missing tile is in the 1st quadrant
if (missing_cell_row < r + n / 2 && missing_cell_col < c + n / 2)
{
fill(r + n / 2, c + (n / 2) - 1, r + n / 2, c + n / 2, r + n / 2 - 1, c + n / 2, board);
}
// If missing tile is in the 3rd quadrant
else
if (missing_cell_row >= r + n / 2 && missing_cell_col < c + n / 2)
{
fill(r + (n / 2) - 1, c + (n / 2), r + (n / 2), c + n / 2, r + (n / 2) - 1, c + (n / 2) - 1, board);
}
// If missing tile is in the 2nd quadrant
else if (missing_cell_row < r + n / 2 && missing_cell_col >= c + n / 2)
{
fill(r + n / 2, c + (n / 2) - 1, r + n / 2, c + n / 2, r + n / 2 - 1, c + n / 2 - 1, board);
}
// If missing Tile is in 4th quadrant
else if (missing_cell_row >= r + n / 2 && missing_cell_col >= c + n / 2)
{
fill(r + (n / 2) - 1, c + (n / 2), r + (n / 2), c + (n / 2) - 1, r + (n / 2) - 1, c + (n / 2) - 1, board);
}
// call the recursive function for the 4 sub-boards
func(n / 2, r, c + n / 2, board);
func(n / 2, r, c, board);
func(n / 2, r + n / 2, c, board);
func(n / 2, r + n / 2, c + n / 2, board);
return;
}
int main()
{
int n = 4;
vector<vector<int>> board = {
{0, 0, 0, 0},
{0, - 1, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}};
func(n, 0, 0, board);
// Call the function to fill the board
// Print the filled board in the end
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << board[i][j] << " ";
}
cout << endl;
}
return 0;
}

Input

4
0 0 0 0
0 -1 0 0
0 0 0 0
0 0 0 0

Output

3 3 2 2
3 -1 1 2
4 1 1 5
4 4 5 5

Implementation in Java

import java.util.*;
import java.lang.*;
import java.io.*;
class Solution{
public static int tile_number = 0;
// Function to fill the corners of the three sub-boards
//which don't contain the missing cell
public static void fill(int x1, int y1, int x2, int y2, int x3, int y3, ArrayList<ArrayList<Integer>> board){
tile_number++;
board.get(x1).set(y1, tile_number);
board.get(x2).set(y2, tile_number);
board.get(x3).set(y3, tile_number);
}
// Function for filling the board
public static void func(int n, int r, int c, ArrayList<ArrayList<Integer>> board, int missing_cell_row, int missing_cell_col){
//Base case
// If the board size is 2
if(n==2){
// We will fill the board with a new tile,
// thus increase the tile number by 1
tile_number++;
// Fill all the tiles other than the missing tile
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board.get(r + i).get(c + j) == 0) {
board.get(r + i).set(c + j, tile_number);
}
}
}
return;
}
// If missing tile is in the 1st quadrant
if (missing_cell_row < r + n / 2 && missing_cell_col < c + n / 2){
fill(r + n / 2, c + (n / 2) - 1, r + n / 2, c + n / 2, r + n / 2 - 1, c + n / 2,board);
}
// If missing tile is in the 3rd quadrant
else if (missing_cell_row >= r + n / 2 && missing_cell_col < c + n / 2){
fill(r + (n / 2) - 1, c + (n / 2), r + (n / 2), c + n / 2, r + (n / 2) - 1, c + (n / 2) - 1,board);
}
// If missing tile is in the 2nd quadrant
else if (missing_cell_row < r + n / 2 && missing_cell_col >= c + n / 2){
fill(r + n / 2, c + (n / 2) - 1, r + n / 2, c + n / 2, r + n / 2 - 1, c + n / 2 - 1,board);
}
// If missing Tile is in 4th quadrant
else if (missing_cell_row >= r + n / 2 && missing_cell_col >= c + n / 2){
fill(r + (n / 2) - 1, c + (n / 2), r + (n / 2), c + (n / 2) - 1, r + (n / 2) - 1, c + (n / 2) - 1,board);
}
// call the recursive function for the 4 sub-boards
func(n/2, r, c + n / 2,board, missing_cell_row, missing_cell_col);
func(n/2, r, c,board, missing_cell_row, missing_cell_col);
func(n/2, r + n / 2, c,board, missing_cell_row, missing_cell_col);
func(n/2, r + n / 2, c + n / 2,board, missing_cell_row, missing_cell_col);
return;
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int n=4;
ArrayList<ArrayList<Integer>> board = new ArrayList<ArrayList<Integer>>();
board.add(new ArrayList<Integer>(Arrays.asList(0, 0, 0, 0)));
board.add(new ArrayList<Integer>(Arrays.asList(0, -1, 0, 0)));
board.add(new ArrayList<Integer>(Arrays.asList(0, 0, 0, 0)));
board.add(new ArrayList<Integer>(Arrays.asList(0, 0, 0, 0)));
func(n,0,0,board, 1, 1); // Call the function to fill the board
// Print the filled board in the end
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
System.out.print(board.get(i).get(j)+" ");
}
System.out.println();
}
}
}

Input

4
0 0 0 0
0 -1 0 0
0 0 0 0
0 0 0 0

Output

3 3 2 2
3 -1 1 2
4 1 1 5
4 4 5 5

Implementation in Python

tile_number = int(0)
# Function to fill the corners of the three sub-boards
# which don't contain the missing cell
def fill(x1, y1, x2, y2, x3, y3, board):
global tile_number
tile_number+=1
board[int(x1)][int(y1)] = tile_number
board[int(x2)][int(y2)] = tile_number
board[int(x3)][int(y3)] = tile_number
# Function for filling the board
def func(n, r, c, board):
n = int(n)
r = int(r)
c = int(c)
# Declares variables which will store the
# row number and column number of the missing cell
missing_cell_row,missing_cell_col = 0, 0
# Base case
# If the board size is 2
if(n==2):
global tile_number
# We will fill the board with a new tile,
# thus increase the tile number by 1
tile_number+=1
# Fill all the tiles other than the missing tile
for i in range(n):
for j in range(n):
if (board[int(r + i)][int(c + j)] == 0):
board[int(r + i)][int(c + j)] = tile_number
return
else:
# Find the missing cell's row and column
for i in range(r, r+n):
for j in range(c, c+n):
if (board[i][j] is not 0): #The cell whose value is
# not 0 is the missing cell
missing_cell_row, missing_cell_col = i, j
# If missing tile is in the 1st quadrant
if (missing_cell_row < r + n / 2 and missing_cell_col < c + n / 2):
fill(r + n / 2, c + (n / 2) - 1, r + n / 2, c + n / 2, r + n / 2 - 1, c + n / 2,board)
# If missing tile is in the 3rd quadrant
elif (missing_cell_row >= r + n / 2 and missing_cell_col < c + n / 2):
fill(r + (n / 2) - 1, c + (n / 2), r + (n / 2), c + n / 2, r + (n / 2) - 1, c + (n / 2) - 1,board)
# If missing tile is in the 2nd quadrant
elif (missing_cell_row < r + n / 2 and missing_cell_col >= c + n / 2):
fill(r + n / 2, c + (n / 2) - 1, r + n / 2, c + n / 2, r + n / 2 - 1, c + n / 2 - 1,board)
# If missing Tile is in 4th quadrant
elif (missing_cell_row >= r + n / 2 and missing_cell_col >= c + n / 2):
fill(r + (n / 2) - 1, c + (n / 2), r + (n / 2), c + (n / 2) - 1, r + (n / 2) - 1, c + (n / 2) - 1,board)
# call the recursive function for the 4 sub-boards
func(n/2, r, c + n / 2,board)
func(n/2, r, c,board)
func(n/2, r + n / 2, c,board)
func(n/2, r + n / 2, c + n / 2,board)
n = int(4)
board = [[0, 0, 0, 0],
[0, -1, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
func(n,int(0),int(0),board) #Call the function to fill the board
# Prthe filled board in the end
for i in range(n):
for j in range(n):
print(str(int(board[i][j])), end = " ")
print()

Input

4
0 0 0 0
0 -1 0 0
0 0 0 0
0 0 0 0

Output

3 3 2 2
3 -1 1 2
4 1 1 5
4 4 5 5

Complexity Analysis

Time complexity:

O(n^2), where n is the size of the board

Reason: The recurrence relation in this solution is T(n) = 4T(n/2) + C. Thus, using the master method, the time complexity will be O(n^2).

Space complexity:

O(n^2), where n is the size of the board

Reason: We have not taken any extra space in the solution. The only space taken is by the recursion stack. Since the number of 2x2 boards will be 2^(2k-2) where n = 2^{k}, the space taken by the recursion stack will be 2^(2k-2), which can be written as n^2.

The Divide and Conquer algorithm (or DAC) is an algorithm that solves a very big task or a problem by breaking it into smaller sub-tasks or sub-problems; after solving, we combine all the sub-tasks in a specific manner so that we get the result for the big task.

What is the difference between Divide and Conquer and Dynamic Programming (DP)?

The DAC algorithm and DP (or Memoization) divide a big task into smaller sub-tasks. But the major difference between these two is that the DP algorithm saves the result of the sub-problems to be utilized in the future, but in the case of DAC, the sub-tasks are further solved recursively and are not saved for future reference.

What are the disadvantages of the divide and conquer algorithm?

Some disadvantages of the Divide and conquer algorithm are:

Most of the algorithms that use the DAC approach are implemented using recursion, making them costly in memory management.

Stack space for recursive calling increases the space complexity.

The DAC approach is challenging to implement when the sub-problems are not similar.