Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
INPUT 
2.2.
OUTPUT
2.3.
Explanation
2.4.
INPUT 
2.5.
OUTPUT
2.6.
Explanation
3.
Approach
3.1.
Algorithm
3.2.
Program
3.3.
INPUT
3.4.
OUTPUT
3.5.
Time Complexity
3.6.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Find palindromic path of given length K in a complete Binary Weighted Graph

Author Anant Dhakad
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

This article will look at a problem involving graphs and palindromes. Graph-based questions are the most popular in coding interviews and programming competitions. 

We will take up a coding challenge that requires a better understanding of the problem statement. Such problems are very interesting. You need to have greater observatory skills to identify the trick to solve the problem.

Problem Statement

Ninja has been given a complete directed graph with binary edge weights (i.e., have either ‘0’ or ‘1’ as edge weight). The complete graph has N vertices.

Your task is to find a palindromic path of length K. Print “YES” and the desired path if it exists, otherwise print “NO”.

INPUT 

N = 3 and K = 4

Edges = [((1, 2), '1'), ((1, 3), '1'), ((2, 1), '1'), ((2, 3), '1'), ((3, 1), '0'), ((3, 2), '0')]

OUTPUT

Yes

2 1 2 1 2

Explanation

Here we can easily find a palindromic path (given 1->2 and 2->1 has the same edge weight). So a possible path could be 2->1->2->1->2 (edges weight form palindrome ‘1111’).

INPUT 

N = 2 and K = 6

edges[] = [((1, 2), ‘1’), ((2, 1), ‘0’)]

OUTPUT

No

Explanation

There is no possible palindromic path in this graph.

Get the tech career you deserve, faster!
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

Approach

We can solve this problem by considering different cases (for even and odd K) and then finding answers for individual cases. 

Observe here that there always exists a palindromic path when K is odd. Consider two nodes i, j such that i->j has weight 1 and j->i have weight 0. Then we can always construct a palindromic path of any odd length ( i->j->i->j . . .).

In the case of K being even, there may be two situations. First that there exists a pair of nodes i and j such that the edge weight of i->j is equal to j->i. Then we can construct an even length palindromic path by rotating around i and j (i->j->i->j->i…).

Otherwise, if there exists a triplet of nodes i, j, and k such that the edge weight of i->j is equal to j->k. Then we can place these three nodes in the center of two odd-length paths to construct an even-length palindromic path. 

Algorithm

1. Odd K:

a. Print the path by choosing any two nodes repeatedly.

2. Even K:

a. If there exists a pair of nodes i, j such that weight of i->j == j->i, then print i and j repeatedly. 

b. Otherwise if there exists a triplet of nodes (i, j, and k) such that i->j == j->k, then print the path accordingly.

Program

// C++ implementation for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
/* Utility function for printing left part of the palindrome (if it exist) */
void printLeftPath(int i, int j, int K){
    int idx1 = i, idx2 = j;
 
    if(K&1){
        // if K is odd
        // j->i->j->i->j->k->j->k->j
        swap(idx1, idx2);
    }
    // if K is even
    // i->j->i->j->k->j->k
 
    for(int p=0; p<K; p++){
        cout << (p&1 ? idx2 : idx1) << " ";
    }
}
 
/* Utility function for printing right part of the palindrome (if it exist) */
void printRightPath(int j, int k, int K){
    for(int p=0; p<K; p++){
        cout << (p&1 ? k : j) << " ";
    }
    cout<<endl;
}
 
 
/**
 * @brief This function prints the final path (if exist).
 *
 * @param i node
 * @param j node
 * @param k node
 * @param K number of edges in palindromic path.
 */
void printPath(int i, int j, int k, int K){
    cout << "YES" << endl;
    K -= 2;
    K /= 2;
    printLeftPath(i, j, K);
    cout << i << " " << j << " " << k << " ";
    printRightPath(j, k, K);
}
 
/**
 * @brief Function to check
 * that if there is a palindromic path in a binary graph.
 */
void findPalindromicPath(){
    int n;cin>>n; // number of nodes.
    int K;cin>>K; // number of edges in palindromic path.
 
    // Adjacency list of given graph.
    vector<vector<int>> adj(n+1, vector<int>(n+1, -1));
 
    // number of edges will n*(n-1), because given graph
    // will be a complete graph.
    int e = n*(n-1);
 
    // Taking graph input.
    for(int i=0; i<e; i++){
        int u,v,w;
        // nodes are numbered starting from '1'.
        cin >> u >> v >> w;
        adj[u][v] = w;
    }
 
    /**
     * If 'K' is odd, print the path
     * simply by choosing nodes 1 and n repeatedly.
     */
    if(K&1){
        cout << "YES" << endl;
        for(int i=0; i<=K; i++)cout << (i&1 ? n : 1) << " ";
        cout<<endl;
        return;
    }
 
    /**
     * If 'K' is even, we first check if there an edge
     * such that weight of i->j and j->i is equal.
     */
    int idx1 = -1, idx2 = -1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i == j)continue;
 
            if(adj[i][j] == adj[j][i]){
                idx1=i, idx2=j;
                break;
            }
        }
    }
    if(idx1 != -1){
        cout << "YES" << endl;
        for(int i=0; i<=K; i++)cout << (i&1 ? idx1 : idx2) << " ";
        cout<<endl;
        return;
    }
 
    /**
     * If no such edge exists, we try to find
     * three nodes (i, j, k) such that
     * weight of i->j and j->k is equal.
     */
 
    vector<int>edgew0[n+1]; // To store edges with weight '0' .
    vector<int>edgew1[n+1]; // To store edges with weight '1' .
 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i == j)continue;
 
            if(adj[i][j] == 1)edgew1[i].push_back(j);
            else edgew0[i].push_back(j);
        }
    }
 
    /**
     * Check if there exist edges i->j & j->k
     * having weight 1
     */
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i == j)continue;
 
            if(adj[i][j] == 1 && edgew1[j].size()){
                int k = edgew1[j][0];
                if(k != i && k != j){
                    printPath(i, j, k, K);
                    return;
                }
            }
        }
    }
 
    /**
     * Check if there exist edges i->j & j->k
     * having weight 0
     */
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i == j)continue;
 
            if(adj[i][j] == 0 && edgew0[j].size()){
                int k = edgew0[j][0];
                if(k != i && k != j){
                    printPath(i, j, k, K);
                    return;
                }
            }
        }
    }
 
    cout << "NO" << endl;
}
 
int main(){
    int tt;cin >> tt;
    while(tt--){
        // nodes are numbered starting from '1'.
        findPalindromicPath();
    }
    return 0;
}

INPUT

2
3 4
1 2 1
1 3 1
2 1 1
2 3 1
3 1 0
3 2 0
2 6
1 2 1
2 1 0

OUTPUT

YES
1 2 1 2 1
NO

Time Complexity

The time complexity of the above program is O(N^2)

Space Complexity

The auxiliary space complexity of the program is O(N^2)

You can also read about Palindrome Number in Python here.

FAQs

1. What are the applications of DFS?

Applications of DFS include cycle detection, topological ordering, finding strongly connected components of a graph, etc.

 

2. How to convert a string into an integer using the C++ STL function What are the applications of BFS?

Applications of BFS include finding the shortest path and minimum spanning tree for the unweighted graphs. It is also used for finding all nodes within one connected component. 

 

3. How to check whether a given string is a palindrome?

We can check if a given string is a palindrome by using the STL reverse function. 

string str = 'naman';
 
string str1 = str;
reverse(str1.begin(), str1.end());
 
if(str == str1)
    cout << "YES" << endl;
else
    cout << "NO" << endl;

 

4. How to find all permutations of an array using C++ STL?

We can find all permutations of a string by using STL next_permutation function.

sort(v.begin(), v.end());
 
do{
    cout << str << endl;
    for(auto x: v)cout << x << “ “;
    cout << endl;
} while(next_permutation(v.begin(), v.end()));

Key Takeaways

Cheers if you reached here!! 

In this blog, we discussed a problem involving palindrome and graphs, Longest Palindromic Subsequence is another problem that you can check out. Graph problems are prevalent in interviews, but they are hard to implement.

Also read, Permutation of string

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!

Previous article
Pair of positions in matrix which are not accessible
Next article
Find the Roots of a Tree that gives Minimum Height
Live masterclass