HackerRank ByteLandian Tours Problem Solution

In this post, we will solve HackerRank ByteLandian Tours Problem Solution.

The country of Byteland contains N cities and N – 1 bidirectional roads between them such that there is a path between any two cities. The cities are numbered (0,…,N – 1). The people were very unhappy about the time it took to commute, especially salesmen who had to go about every city selling goods. So it was decided that new roads would be built between any two “somewhat near” cities. Any two cities in Bytleland that can be reached by traveling on exactly two old roads are known as “somewhat near” each other.

Now a salesman situated in city 0, just like any other typical salesman, has to visit all cities exactly once and return back to city 0 in the end. In how many ways can he do this?

Input Format

The first line contains the number of test cases T. T test cases follow. The first line contains N, the number of cities in Byteland. The following N – 1 lines contain the description of the roads. The ith line contains two integers ai and bi, meaning that there was originally a road connecting cities with numbers ai and bi.

Constraints

1 <= T <= 20
1 <= N <= 10000
0 <= ai,bi < N  

Output Format

Output T lines, one corresponding to each test case containing the required answer for that test case. Since the answers can be huge, output them modulo 1000000007.

Sample Input

2
3
0 1
1 2
5
0 1
1 2
2 3
2 4

Sample Output

2
4

Explanation

For the first case, a new road was build between cities 0 and 2. Now, the salesman has two tour possibilities: 0-1-2-0 or 0-2-1-0.

HackerRank ByteLandian Tours Problem Solution
HackerRank ByteLandian Tours Problem Solution

ByteLandian Tours C Solution

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
typedef struct node{
  int x;
  struct node *next;
} node;
void add_edge(int x,int y);
void clean();
int d[10000],N;
long long fac[10001];
node *list[10000]={0};

int main(){
  int T,x,y,n,c1,c2,i;
  long long ans;
  node *p;
  fac[0]=fac[1]=1;
  for(i=2;i<10001;i++)
    fac[i]=i*fac[i-1]%MOD;
  scanf("%d",&T);
  while(T--){
    ans=1;
    n=0;
    scanf("%d",&N);
    for(i=0;i<N;i++)
      d[i]=0;
    for(i=0;i<N-1;i++){
      scanf("%d%d",&x,&y);
      add_edge(x,y);
      d[x]++;
      d[y]++;
    }
    for(i=0;i<N;i++)
      if(d[i]!=1){
        n++;
        c1=c2=0;
        for(p=list[i];p;p=p->next)
          if(d[p->x]==1)
            c1++;
          else
            c2++;
        if(c2>2){
          ans=0;
          break;
        }
        else
          ans=ans*fac[c1]%MOD;
      }
    if(n>1)
      ans=2*ans%MOD;
    printf("%lld\n",ans);
    clean();
  }
  return 0;
}
void add_edge(int x,int y){
  node *p1,*p2;
  p1=(node*)malloc(sizeof(node));
  p2=(node*)malloc(sizeof(node));
  p1->x=y;
  p1->next=list[x];
  list[x]=p1;
  p2->x=x;
  p2->next=list[y];
  list[y]=p2;
  return;
}
void clean(){
  node *p1,*p2;
  int i;
  for(i=0;i<N;i++)
    if(list[i]){
      p1=list[i];
      while(p1){
        p2=p1;
        p1=p1->next;
        free(p2);
      }
      list[i]=NULL;
    }
  return;
}

ByteLandian Tours C++ Solution

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define pb push_back
typedef long long ll;

int ri()
{
  int x;
  scanf("%d", &x);
  return x;
}

const int N = 10000, MOD = 1000000007;
int fac[N];
vector<int> e[N];

int f(int n)
{
  int path = n, ans = 1;
  REP(i, n)
    if (e[i].size() == 1)
      path--;
  REP(i, n)
    if (e[i].size() > 1) {
      int leaf = 0, inner = 0;
      for (auto v: e[i])
        if (e[v].size() == 1)
          leaf++;
        else
          inner++;
      if (inner > 2)
        return 0;
      ans = ll(ans)*fac[leaf]%MOD;
    }
  return path == 1 ? ans : ans*2%MOD;
}

int main()
{
  for (int cc = ri(); cc--; ) {
    int n = ri();
    REP(i, n)
      e[i].clear();
    fac[0] = 1;
    FOR(i, 1, n)
      fac[i] = ll(fac[i-1])*i%MOD;
    REP(i, n-1) {
      int x = ri(), y = ri();
      e[x].pb(y);
      e[y].pb(x);
    }
    printf("%d\n", f(n));
  }
}

ByteLandian Tours C Sharp Solution

using System;
using System.Collections.Generic;
using System.Text;

class Solution
{
    public const int MaxN = 10000;
    public const int Modulo = 1000000007;
    public static long[] Factorial;

    public static void Init()
    {
        // Init Factorial
        Factorial = new long[MaxN+2];
        Factorial[0] = 1;
        for (int i = 1; i <= MaxN; i++)
            Factorial[i] = Factorial[i - 1] * i % Modulo;
    }

    static void Main(string[] args)
    {
        StringBuilder sb = new StringBuilder();
        Init();
        int NumTests;
        int.TryParse(Console.ReadLine(), out NumTests);
        for (int t = 0; t < NumTests; t++)
        {
            Tree tree = new Tree();
            sb.Append(tree.Solve()).AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }

        
}

class Tree
{
    int _numNodes;
    int _numLeaves;
    Node[] _nodes;
    long Result = 1;
    bool _updateResult;

    public Tree()
    {
        int.TryParse(Console.ReadLine(), out _numNodes);
        _numLeaves = 0;

        //Initializing Nodes
        _nodes = new Node[_numNodes];
        for (int n = 0; n < _numNodes; n++)
            _nodes[n] = new Node(n);
            
        //Reading Edges
        string[] input;
        int i, j;
        for (int edge = 0; edge < _numNodes - 1; edge++)
        {
            input = Console.ReadLine().Split();
            int.TryParse(input[0], out i);
            int.TryParse(input[1], out j);
            _nodes[i].Neighbors.Add(j);
            _nodes[j].Neighbors.Add(i);

        }
    }

    public long Solve()
    {
        MarkLeaves();

        foreach (Node n in _nodes)
            if (!n.IsLeaf && FindNextInCentralPath(n) > 2)
                return 0;

        if (_numLeaves == _numNodes - 1)
            return Result;

        return 2*Result % Solution.Modulo;
    }

    private void MarkLeaves()
    {
        foreach (Node n in _nodes)
            if (n.Neighbors.Count == 1)
            {
                n.IsLeaf = true;
                _numLeaves++;
            }
    }

    private int FindNextInCentralPath(Node n)
    {
        int NumLeaves = 0;
        int NumNext = 0;
        foreach (int neighbor in n.Neighbors)
            if (!_nodes[neighbor].IsLeaf)
                NumNext++;
            else
                NumLeaves++;

        Result = Result * Solution.Factorial[NumLeaves] % Solution.Modulo;
        return NumNext;
    }
}

class Node
{
    public bool IsLeaf;
    public List<int> Neighbors;

    public Node(int idx)
    {
        Neighbors = new List<int>();
    }
}

ByteLandian Tours Java Solution

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {
    private static final int MODULUS = 1000000007;

    private static class Node {
        Set<Node> neighbors = new HashSet<>();
    }

    /*
     * Complete the bytelandianTours function below.
     */
    static int bytelandianTours(int n, int[][] roads) {
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node();
        }
        for (int[] road : roads) {
            nodes[road[0]].neighbors.add(nodes[road[1]]);
            nodes[road[1]].neighbors.add(nodes[road[0]]);
        }

        long result = 1;
        int nonLeaves = 0;
        for (Node node : nodes) {
            if (node.neighbors.size() > 1) {
                nonLeaves++;
                int leaves = leafNeighbors(node);
                if (leaves + 2 < node.neighbors.size()) {
                    return 0;
                } else {
//                    System.out.println(String.format("Multiplying by %d!", node.neighbors.size() - 2));
                    for (int i = 2; i <= leaves; i++) {
                        result = (result*i) % MODULUS;
                    }
                }
            }
        }
        if (nonLeaves > 1) {
            result = (result*2) % MODULUS;
        }
        return (int) result;
    }

    private static int leafNeighbors(Node n) {
        int leaves = 0;
        for (Node other : n.neighbors) {
            if (other.neighbors.size() == 1) {
                leaves++;
            }
        }
        return leaves;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

        for (int tItr = 0; tItr < t; tItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

            int[][] roads = new int[n-1][2];

            for (int roadsRowItr = 0; roadsRowItr < n-1; roadsRowItr++) {
                String[] roadsRowItems = scanner.nextLine().split(" ");
                scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

                for (int roadsColumnItr = 0; roadsColumnItr < 2; roadsColumnItr++) {
                    int roadsItem = Integer.parseInt(roadsRowItems[roadsColumnItr]);
                    roads[roadsRowItr][roadsColumnItr] = roadsItem;
                }
            }

            int result = bytelandianTours(n, roads);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

ByteLandian Tours JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the bytelandianTours function below.
 */
const mod = 1000000007n;

function bytelandianTours(length, roads) {
    if (length < 3) return 1;
    const tree = Array.from({ length }, () => []);
    for (const [a, b] of roads) {
        tree[a].push(tree[b]);
        tree[b].push(tree[a]);
    }
    // Get the tree without the leaves
    const internals = tree.filter(a => a.length > 1);
    // Get the leaves of that internal tree
    const ends = internals.filter(a => a.filter(b => b.length > 1).length < 2);
    // If this internal tree has branches (i.e. more than two leaves), then there is no solution
    if (ends.length > 2) return 0;
    const first = ends[0];
    const last = ends[1] || first;
    return Number(internals.reduce((acc, a) => acc * factorial(a.length - (a !== first) - (a !== last)) % mod, BigInt(ends.length)));

}

function factorial(n) {
    if (!factorial[n]) factorial[n] = factorial(n - 1) * BigInt(n) % mod;
    return factorial[n];
}
factorial[0] = factorial[1] = 1n;

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const n = parseInt(readLine(), 10);

        let roads = Array(n-1);

        for (let roadsRowItr = 0; roadsRowItr < n-1; roadsRowItr++) {
            roads[roadsRowItr] = readLine().split(' ').map(roadsTemp => parseInt(roadsTemp, 10));
        }

        let result = bytelandianTours(n, roads);

        ws.write(result + "\n");
    }

    ws.end();
}

ByteLandian Tours Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'bytelandianTours' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER n
#  2. 2D_INTEGER_ARRAY roads
#

def bytelandianTours(n, roads):
    if n <= 2:
        return 1
    m = 1000000007
    nbr = list()
    for i in range(n):
        nbr.append(list())
    for a,b in roads:
        nbr[a].append(b)
        nbr[b].append(a)
    
    city = 0
    if len(nbr[0]) == 1:
        city = nbr[0][0]
    nbr[city].sort(key=lambda x: len(nbr[x]), reverse = True)
    if len(nbr[nbr[city][0]]) == 1:
        return math.factorial(len(nbr[city])) % m
    if len(nbr[city]) > 2 and len(nbr[nbr[city][2]]) > 1:
        return 0
    if len(nbr[nbr[city][1]]) > 1:
        next_route = nbr[city][1]
        nbr[next_route].remove(city)
        rslt = (2 * math.factorial(len(nbr[city]) - 2)) % m
    else:
        next_route = -1
        rslt = (2 * math.factorial(len(nbr[city]) - 1)) % m
    #print(city, nbr)
    parent = city
    city = nbr[city][0]
    nbr[city].remove(parent)
    while True:
        nbr[city].sort(key=lambda x: len(nbr[x]), reverse = True)
        #print(city, nbr)
        if len(nbr[nbr[city][0]]) == 1:
            rslt = (rslt * (math.factorial(len(nbr[city])) %m)) %m
            if next_route != -1:
                city = next_route
                next_route = -1
                continue
            else:
                break
        if len(nbr[city]) > 1 and len(nbr[nbr[city][1]]) > 1:
            return 0
        rslt = (rslt * (math.factorial(len(nbr[city])-1) %m)) %m
        
        parent = city
        city = nbr[city][0]
        nbr[city].remove(parent)
        
    return rslt
 

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        n = int(input().strip())

        roads = []

        for _ in range(n - 1):
            roads.append(list(map(int, input().rstrip().split())))

        result = bytelandianTours(n, roads)

        fptr.write(str(result) + '\n')

    fptr.close()