HackerEarth Fredo and his Birthday Gift problem solution YASH PAL, 31 July 202417 February 2026 In this HackerEarth Fredo and his Birthday Gift problem solution It was Fredo’s birthday yesterday. He got a simple graph of N vertices and M edges as one of the birthday gifts. He has been bragging about his gift to all his friends. One of his friends asked him to do the following task on the graph: For each of the vertices in the graph, find the maximum length simple path ending at that vertex.Being unable to solve it himself, he asks you for help. Help Fredo!Note: Length of a simple path= number of edges in the path.A simple path is a path in a graph which does not have repeating vertices. HackerEarth Fredo and his Birthday Gift problem solution.#include<bits/stdc++.h>#define nmax 15using namespace std;int ans[nmax];void find_hamiltonian_paths(int adj[nmax][nmax],int n){ bool dp[nmax][1<<nmax]={0}; int i,j,k; for(i=0;i<n;i++) { dp[i][1<<i]=1; ans[i]=0; } int limit=1<<n; for(i=0;i<limit;i++) { int count=0,temp=i; while(temp) { temp&=temp-1; count++; } for(j=0;j<n;j++) { if(i & (1<<j)) { for(k=0;k<n;k++) if(k!=j && adj[k][j] && (i & (1<<k)) && dp[k][i^(1<<j)]) { dp[j][i]=1;break; } if(dp[j][i]) ans[j]=max(ans[j],count-1); } } } for(i=0;i<n;i++) printf("%d ",ans[i]); printf("n");}int main(){ int t; scanf("%d",&t); while(t--) { int n,m,i,adj[nmax][nmax]={0}; scanf("%d%d",&n,&m); for(i=0;i<m;i++) { int x,y; scanf("%d%d",&x,&y); adj[x-1][y-1]=adj[y-1][x-1]=1; } find_hamiltonian_paths(adj,n); } return 0;} Second solution#include <bits/stdc++.h>using namespace std;#define mod 1000000007#define ll long long int#define pb push_back#define mk make_pairll power(ll a, ll b) {ll x = 1, y = a; while(b > 0) { if(b%2 == 1) { x=(x*y); if(x>mod) x%=mod; } y = (y*y); if(y>mod) y%=mod; b /= 2; } return x;}int adj[15][15];int dp[15][1<<15];int n;int func(int mask, int total) { if(total == (1 << mask)) { return 0; } if(dp[mask][total] != -1) { return dp[mask][total]; } int s = 0,i; for(i = 0; i < n; i++) { if(i != mask && total&(1<<i) && adj[i][mask] != -1) { s = max(s,func(i,total&~(1<<mask))+1); } } return dp[mask][total] = s;}int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t,m,i,j,u,v; cin>>t; while(t--) { cin>>n>>m; memset(dp,-1,sizeof dp); memset(adj,-1,sizeof adj); while(m--) { cin>>u>>v; u--; v--; adj[u][v] = adj[v][u] = 1; } int x = (1<<n)-1; for(i = 0; i < n; i++) { cout<<func(i,x)<<" "; } cout<<endl; } return 0;} coding problems solutions HackerEarth HackerEarth