Table of contents

Introduction

Problem Statement

2.1.

Sample Examples

Approach

Optimum Approach

4.1.

Implementation in Java

4.2.

Implementation in C++

4.3.

Complexity Analysis

Frequently Asked Questions

5.1.

Give an algorithm for preorder traversal in a Binary Tree.

5.2.

Which data structure do we use for DFS?

5.3.

When do we use DFS in Trees?

5.4.

How do we perform DFS in a disconnected graph?

Conclusion

Last Updated: Mar 27, 2024

Medium

Construct Binary Palindrome by Repeated Appending and Trimming

Author Rupal Saluja

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

In this blog, we will grab hold of a simple problem in which we used the properties of Depth First Search (DFS Algorithm). The problem aims to construct a palindrome of a given size using a binary number mentioned as input. The binary number repeats itself as often as it requires to make a palindrome out of it.

Through this problem, we will understand how to approach any such problem. We will briefly learn about Depth First Search (DFS), examine the problem statement, the sample examples will help you clear the concepts, the algorithm will facilitate you with simplified solutions, and implementation in programming languages will let you understand every step in detail.

What is DFS?

DFS stands for Depth First Search. By its name, it is implied that this search starts with the root node and traverses the tree in depth until we find a leaf node. A leaf node is a node that has no children. The search will then start backtracking. The DFS technique traverses or explores data structures such as trees and graphs. The procedure for traversal is a little different for both data structures. We will use an example each for a better understanding of how traversals are performed.

Binary Tree Traversal

There are three types of DFS Traversals for any Binary Tree: preorder, inorder, and postorder. The tree below has been used for all three to help you learn better. There are no cycles in a tree, so it becomes easy to find traversals in cases of trees. Learn more about Binary Tree Traversal.

Preorder: 5 12 18 4 13 7 60
Inorder: 4 18 13 12 5 7 60
Postorder: 4 13 18 12 60 7 5

Graph Traversal

Graph Traversals are not as easy as Tree Traversals. This is because there are cycles in a graph. Let us understand DFS Traversal in a graph using an example.

Input:

N=4 (Nodes), E=7 (Edges)
1->2, 1->4, 4->3, 4->2, 3->1, 3->2, 2->3

Output:

DFS from vertex 1: 1->2->3->4

DFS from vertex 2: 2->3->1->4

DFS from vertex 3: 3->1->4->3

DFS from vertex 4: 4->3->1->2

For a detailed understanding of traversals in the graph, refer to this link.

Problem Statement

Firstly, we will have a look at what exactly the problem says.

We are given two inputs, the length of the palindrome we have to construct and the length of a binary number using which we will construct a palindrome. We need to output the constructed binary palindrome using both lengths.

We can use operations such as appending and trimming repeatedly to get the desired results. Here, we have assumed that the length of a palindrome is always greater than the length of the binary number, and both the lengths are never zero. There are no exceptions to this problem.

The necessary conditions that come with the problem are that the palindrome must always begin with 1 and contains the maximum number of zeros

To understand the problem statement better, let us see some examples.

Sample Examples

🥝 Example 1:

Input: palindrome_len = 6

Input: binary_len = 3

Output: 101101

Explanation

As seen in the example, we have taken two inputs. One input for the length of palindrome we want to construct is 6, and another for the binary number to be used for palindrome construction, that is, 3. We can observe that both the inputs are not equal to zero, so no exception occurs. Also, we get the output as per the algorithm of the program.

The binary length is 3 and the first binary number of length 3 is 100. The palindrome length is 6, so no trimming is required. If we append 100 twice, we get 100100, that is not a palindrome. The next binary number of length 3 is 101. If we append 101 twice, we get 101101. Yes, that is a palindrome and hence, the output.

🥝 Example 2:

Input: palindrome_len = 5

Input: binary_len = 1

Output: 11111

Explanation

As seen in the example, we have taken two inputs. One input for the length of palindrome we want to construct is 5, and another for the binary number to be used for palindrome construction, that is, 1. We can observe that both the inputs are not equal to zero, so no exception occurs. But, the length of the binary number we can use is 1. So, we will default use only the binary number ‘1’ for the palindrome construction. We get the output as per the algorithm of the program.

The binary length is 1 and the default binary number of length 1 set by the necessary condition is 1. The palindrome length is 5, so no trimming is required. So, 1 will be appended as many times as required. We get 11111, which is a palindrome and hence, the output.

🥝 Example 3:

Input: palindrome_len = 7

Input: binary_len = 2

Output: 1010101

Explanation

As seen in the example, we have taken two inputs. One input for the length of palindrome we want to construct is 7, and another for the binary number to be used for palindrome construction, that is, 2. We can observe that both the inputs are not equal to zero, so no exception occurs. The length of the binary number we can use is 2. So, we will consecutively use a combination of two binary numbers, ‘0’ and ‘1’, for the palindrome construction. Also, we get the output as per the algorithm of the program.

The binary length is 2 and the first binary number of length 2 is 10. The palindrome length is 7, so no trimming is required initially. If we append four times, we get 10101010, which is not a palindrome. The number is trimmed by one place. Next up, we get 1010101. Yes, that is a palindrome and hence, the output.

🥝 Example 4:

Input: palindrome_len = 3

Input: binary_len = 0

Output: Exception occurs

Explanation

As seen in the example, we have taken two inputs. One input for the length of palindrome we want to construct, 3, and another for the binary number to be used for palindrome construction, that is, 0. We can observe that one of the inputs equals zero, so an exception occurs. Also, we will not get the output as per the program’s algorithm. This same exception would have occurred if the length of the palindrome had been equal to zero.

Approach

The naive idea would be to hit and try every palindrome of a given size, beginning with 1, to construct a binary palindrome of a given length. But, this approach has exponential time complexity, which is not acceptable.

Optimum Approach

The optimum approach is to initialize the digits of palindrome length with indices so that they can be connected to form a palindrome. An array is used to store all the indices so we can use them conveniently. You can use the property of palindrome, which says kth and (n – k – 1)th variable should be the same. This way, the value of the first index will match the last, the value of the second index will be the same as the second last, and so on. The construction of the palindrome performed using this approach gives linear time complexity.

Implementation in Java

import java.util.*;
class Main
{
    //driver function
    public static void main(String[] args)
    {
        int palindrome_len = 10, binary_len = 4;
        print(palindrome_len, binary_len);
    }
    //function to implement depth-first search
    static void depthfirstsearch(int root, int op[], Vector<Integer> connect[])
    {
        op[root] = 1;
        for (int i = 0; i < connect[root].size(); i++)
        {
            if (op[connect[root].get(i)] != 1)
                depthfirstsearch(connect[root].get(i), op, connect);
        }
    }
    //function to print the output binary palindrome
    static void print(int palindrome_len, int binary_len)
    {
        int []a = new int[palindrome_len];
        int []op = new int[palindrome_len];
        Vector<Integer> []connect = new Vector[binary_len];
        for (int i = 0; i < binary_len; i++)
            connect[i] = new Vector<Integer>();
        for (int i = 0; i < palindrome_len; i++)
            a[i] = i % binary_len;
        for (int i = 0; i < palindrome_len / 2; i++)
        {
            connect[a[i]].add(a[palindrome_len - i - 1]);
            connect[a[palindrome_len - i - 1]].add(a[i]);
        }
        depthfirstsearch(0, op, connect);
        for (int i = 0; i < palindrome_len; i++)
            System.out.print(op[a[i]]);
    }
}

Output:

1100110011

Implementation in C++

#include <iostream>
#include <vector>
using namespace std;
//function to implement depth-first search
void depthfirstsearch(int root, int op[], vector<int> connect[])
{
    op[root] = 1;
    for (int i = 0; i < connect[root].size(); i++) {
        if (!op[connect[root][i]])
            depthfirstsearch(connect[root][i], op, connect);
    }
}
//function to print the output binary palindrome
void print(int palindrome_len, int binary_len)
{
    int a[palindrome_len], op[palindrome_len] = { 0 };
    vector<int> connect[binary_len];
    for (int i = 0; i < palindrome_len; i++)
        a[i] = i % binary_len;
    for (int i = 0; i < palindrome_len / 2; i++) {
        connect[a[i]].push_back(a[palindrome_len - i - 1]);
        connect[a[palindrome_len - i - 1]].push_back(a[i]);
    }
    depthfirstsearch(0, op, connect);
 
    for (int i = 0; i < palindrome_len; i++)
        cout << op[a[i]];
}
//driver function
int main()
{
    int palindrome_len = 15, binary_len = 6;
    print(palindrome_len, binary_len);
    return 0;
}

Output:

101000101000101

Complexity Analysis

🌺 Time Complexity:

Here, in the implementation above, only one loop has been used. Therefore, the time complexity, in this case, will be O(n).

🌺 Space Complexity:

Since the space scales 1:1 with changes to the size of n, that is, n increases by 1 every time a new iteration is performed. Therefore, the space complexity would be O(n).

Check out this problem - Check If A String Is Palindrome

You can also read about Palindrome Number in Python here.

Frequently Asked Questions

Give an algorithm for preorder traversal in a Binary Tree.

The algorithm for preorder traversal in a Binary Tree is given below.

Print the node's data.

Move to the node's left side (traverse left subtree).

Move to the node's right side (traverse right subtree).

Which data structure do we use for DFS?

We use the stack data structure to store nodes at different levels while performing Depth First Search implementation.

When do we use DFS in Trees?

The number and placement of solutions completely depend on the tree’s topology we are using DFS for. DFS is better when the target is away from the start.

How do we perform DFS in a disconnected graph?

We know that in a disconnected graph, all its vertices may not be accessed from every vertex. So, firstly, we will perform DFS for nodes that are accessible. Then, we will perform DFS for all unvisited nodes to complete. In this way, we perform DFS for those graphs.

Conclusion

In a nutshell, we looked at the problem statement, had a look at every possible condition that could occur, understood the approach, went through the Algorithm, saw the implementations, tested the code against sample input, and did time and space complexities’ analysis.

We hope the above discussion helped you understand and solve the problem better, and now it is your turn to code the problem in your way.

For enthusiasts who want to solve more such questions, refer to the list below.

Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can focus on interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help other ninjas grow.

Happy Coding!