Organic Tree
Given the value of k and n (the number of nodes of type A) in the tree, compute the total number of nodes of type B present in the tree. Each node of type A is required to have exactly k edges, while each node of type B should have only one edge.
Note: A tree with m nodes has m – 1 edges and no cycle.
Examples:
Input: n = 2, k = 4
Output: 6
Explanation: The tree is given below where 3 B’s are connected to each A, which are connected to each other.
Input: n = 3, k = 5
Output: 11
Explanation: One of the valid trees is given below.
Approach: We can solve this problem using below Idea.
This problem can be solved by observation and maths. We can see that B is always going to be a leaf node and A will be our internal nodes . No of B nodes will not depend upon the structure of Tree. It will always equal to n*(k-2) + 2 .
Steps to solve this problem:
- Intialise a cnt = 0 which will be number of B types node.
- As there are n, A types nodes:
- cnt= n * k.
- Subtract A nodes from cnt.
- Return cnt, which will be B nodes.
Below is the implementation of the above approach:
C++
// C++ Implementation #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to count nodes of type B long long countB( int n, int k) { // Intialise a sum = 0 long long sum = 0; // Count number of node B possible sum = n * 1ll * k; // Reduce A type nodes sum -= n; sum -= n - 2; // Return B types nodes return sum; } // Driver code int main() { int n = 4; int k = 2; // Function call cout << countB(n, k); return 0; } |
Java
// Java Implementation class GFG { // Function to count nodes of type B static long countB( int n, int k) { // Intialise a sum = 0 long sum = 0 ; // Count number of node B possible sum = n * 1L * k; // Reduce A type nodes sum -= n; sum -= n - 2 ; // Return B types nodes return sum; } // Driver code public static void main(String[] args) { int n = 4 ; int k = 2 ; // Function call System.out.println(countB(n, k)); } } // This code is contributd by ragul21 |
Python3
# Python3 Implementation def count_b(n, k): # Function to count nodes of type B # Initialize a sum = 0 sum_value = 0 # Count the number of node B possible sum_value = n * k # Reduce A type nodes sum_value - = n sum_value - = n - 2 # Return B types nodes return sum_value # Driver code if __name__ = = "__main__" : n = 4 k = 2 # Function call print (count_b(n, k)) # This code is contributed by shivamgupta0987654321 |
C#
using System; class GFG { // Function to count nodes of type B static long CountB( int n, int k) { // Initialize a sum = 0 long sum = 0; // Count the number of node B possible sum = n * 1L * k; // Reduce A type nodes sum -= n; sum -= n - 2; // Return B types nodes return sum; } // Driver code public static void Main( string [] args) { int n = 4; int k = 2; // Function call Console.WriteLine(CountB(n, k)); } } |
Javascript
// javaScript code for the above approach // Function to count nodes of type B function countB(n, k) { // Intialise a sum = 0 let sum = 0; // Count number of node B possible sum = BigInt(n) * BigInt(k); // Reduce A type nodes sum -= BigInt(n); sum -= BigInt(n - 2); // Return B types nodes return sum; } // Driver code const n = 4; const k = 2; // Function call console.log(countB(n, k).toString()); |
2
Time Complexity: O(1)
Auxiliary Space: O(1)