Given a positive integer N, the task is to find the height of the Factor Tree of the given integer N.
Examples:
Input: N = 20
Output: 3
Explanation: The height of the Factor Tree of 20 shown in the image below is 3.
Input: N = 48
Output: 5
Approach: The given problem can be solved by using the steps discussed below:
- Initialize a variable, say height as 0 that stores the height of the Factor Tree of the given integer N.
- Iterate over all the values of i in the range [2, ?N] and perform the following steps:
- Find the smallest divisor of N and if it exists, then increment the value of height by 1.
- If a divisor i exists, then repeat the above step by updating the value of N to N / i, until N > 1.
- If no divisors of N exist break the loop.
- After completing the above steps, print the value of height as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to find the height of the// Factor Tree of the integer Nint factorTree(int N){    // Stores the height of Factor Tree    int height = 0;Â
    // Loop to iterate over values of N    while (N > 1) {        // Stores if there exist        // a factor of N or not        bool flag = false;Â
        // Loop to find the smallest        // factor of N        for (int i = 2; i <= sqrt(N); i++) {            // If i is a factor of N            if (N % i == 0) {                N = N / i;                flag = true;                break;            }        }Â
        // Increment the height        height++;Â
        // If there are no factors of N        // i.e, N is prime, break loop        if (!flag) {            break;        }    }Â
    // Return Answer    return height;}Â
// Driver Codeint main(){Â Â Â Â int N = 48;Â Â Â Â cout << factorTree(N);Â
    return 0;} |
Java
// Java program for the above approachpublic class Main{    // Function to find the height of the    // Factor Tree of the integer N    static int factorTree(int N)    {                // Stores the height of Factor Tree        int height = 0;               // Loop to iterate over values of N        while (N > 1)        {                       // Stores if there exist            // a factor of N or not            boolean flag = false;                   // Loop to find the smallest            // factor of N            for (int i = 2; i <= Math.sqrt(N); i++)            {                               // If i is a factor of N                if (N % i == 0) {                    N = N / i;                    flag = true;                    break;                }            }                   // Increment the height            height++;                   // If there are no factors of N            // i.e, N is prime, break loop            if (!flag) {                break;            }        }               // Return Answer        return height;    }         public static void main(String[] args) {        int N = 48;        System.out.println(factorTree(N));    }}Â
// This code is contributed by mukesh07. |
Python3
# Python 3 program for the above approachfrom math import sqrtÂ
# Function to find the height of the# Factor Tree of the integer Ndef factorTree(N):       # Stores the height of Factor Tree    height = 0Â
    # Loop to iterate over values of N    while (N > 1):               # Stores if there exist        # a factor of N or not        flag = FalseÂ
        # Loop to find the smallest        # factor of N        for i in range(2,int(sqrt(N))+1,1):            # If i is a factor of N            if (N % i == 0):                N = N // i                flag = True                breakÂ
        # Increment the height        height += 1Â
        # If there are no factors of N        # i.e, N is prime, break loop        if (flag==False):            breakÂ
    # Return Answer    return heightÂ
# Driver Codeif __name__ == '__main__':Â Â Â Â N = 48Â Â Â Â print(factorTree(N))Â Â Â Â Â Â Â Â Â # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;class GFG {         // Function to find the height of the    // Factor Tree of the integer N    static int factorTree(int N)    {               // Stores the height of Factor Tree        int height = 0;              // Loop to iterate over values of N        while (N > 1) {            // Stores if there exist            // a factor of N or not            bool flag = false;                  // Loop to find the smallest            // factor of N            for (int i = 2; i <= Math.Sqrt(N); i++) {                // If i is a factor of N                if (N % i == 0) {                    N = N / i;                    flag = true;                    break;                }            }                  // Increment the height            height++;                  // If there are no factors of N            // i.e, N is prime, break loop            if (!flag) {                break;            }        }              // Return Answer        return height;    }Â
  static void Main() {    int N = 48;    Console.Write(factorTree(N));  }}Â
// This code is contributed by decode2207. |
Javascript
<script>        // JavaScript Program to implement        // the above approachÂ
        // Function to find the height of the        // Factor Tree of the integer N        function factorTree(N)         {                     // Stores the height of Factor Tree            let height = 0;Â
            // Loop to iterate over values of N            while (N > 1)            {                             // Stores if there exist                // a factor of N or not                let flag = false;Â
                // Loop to find the smallest                // factor of N                for (let i = 2; i <= Math.sqrt(N); i++)                 {                                     // If i is a factor of N                    if (N % i == 0) {                        N = Math.floor(N / i);                        flag = true;                        break;                    }                }Â
                // Increment the height                height++;Â
                // If there are no factors of N                // i.e, N is prime, break loop                if (!flag) {                    break;                }            }Â
            // Return Answer            return height;        }Â
        // Driver Code        let N = 48;        document.write(factorTree(N));Â
// This code is contributed by Potta LokeshÂ
    </script> |
Output:Â
5
Â
Time Complexity: O(?N*log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More on that Topic: geeksforgeeks.org/height-of-factor-tree-for-a-given-number/ […]