Trees with Constraints

HardPython

Problem

Given tree node values only in range 1 to N, find the number of trees possible with constraints on adjacent node values (e.g. must not be divisible by each other).

Asked in the coding round stage. SCE HackerEarth coding round.

Implement count_trees(n, k). Count every undirected tree whose k distinct node values are selected from 1..n. An edge is valid only when neither endpoint divides the other. Return the total count.

Constraints

1 <= k <= n <= 12
Node values are distinct integers in the range 1..n
An edge is valid only when neither endpoint divides the other
Trees are undirected and counted by their selected values and edge sets

Function Signature

def count_trees(n, k):

CodePython 3

You need to log in / sign up to run or submit.Ln 2

Run your code to see test output here.