Given a N-ary Tree and Q queries where each query contains a node of the N-ary tree, the task is to count the number of nodes that have an odd number of divisors in the subtree for Q queries.
Examples:
Input:
Output: 1 3 0 1
Explanation:
Query 1: In the subtree rooted at node 100, there is only one node which is 100 which have 9 divisors {1, 2, 4, 5, 10, 20, 25, 50, 100}. Therefore, there is only one node having the odd number of divisors.
Query 2: In the subtree rooted at node 4, there are 5 nodes out of which 3 nodes are having an odd number of divisors. That is {4, 9, 100}
Query 3: In the subtree rooted at node 5, there is only one node which is 5 which has two divisors. Therefore, there zero nodes having an odd number of divisors.
Naive Approach: A simple solution is to traverse the subtree for each query and find the count of nodes that are having an odd number of divisors.
Efficient Approach: The idea is to pre-compute the count of an odd number of divisors for each subtree and storing the count in hash-map. To pre-compute the count of nodes having an odd number of divisors we can use Depth First Search Traversal. Finally, to check that the current node is having an odd number of divisors or not we can use the fact that every perfect square number has an odd number of divisors.
Below is the implementation of the above approach:
C++
// C++ implementation to count the// number of nodes having odd// number of divisors for each query#include <bits/stdc++.h>using namespace std;#define N 100001// Adjacency list// for tree.vector<int> adj[N];// Array for values and// answer at ith node.int a[N], ans[N];// Function to check whether N// has odd divisors or notbool hasOddNumberOfDivisors(int n){ if ((double)sqrt(n) == (int)sqrt(n)) return true; return false;}// DFS function to pre-compute// the answersint dfs(int node, int parent){ // Initialize the count int count = 0; for (auto i = adj[node].begin(); i != adj[node].end(); ++i) { if (*i != parent) { // Repeat for every child count += dfs(*i, node); } } // Increase the count if current node // has odd number of divisors if (hasOddNumberOfDivisors(a[node])) ++count; ans[node] = count; return count;}// Driver Codeint main(){ int n = 5, i; vector<int> q = { 4, 1, 5, 3 }; // Adjacency List adj[1].push_back(2); adj[2].push_back(1); adj[2].push_back(3); adj[3].push_back(2); adj[3].push_back(4); adj[4].push_back(3); adj[1].push_back(5); adj[5].push_back(1); a[1] = 4; a[2] = 9; a[3] = 14; a[4] = 100; a[5] = 5; // Function call dfs(1, -1); for (int i = 0; i < q.size(); i++) { cout << ans[q[i]] << " "; } return 0;} |
Java
// Java implementation to // count the number of nodes // having odd number of // divisors for each queryimport java.util.*;class GFG{static final int N = 100001;// Adjacency list// for tree.static Vector<Integer> []adj = new Vector[N];// Array for values and// answer at ith node.static int []a = new int[N];static int []ans = new int[N];// Function to check whether N// has odd divisors or notstatic boolean hasOddNumberOfDivisors(int n){ if ((double)Math.sqrt(n) == (int)Math.sqrt(n)) return true; return false;}// DFS function to // pre-compute the answersstatic int dfs(int node, int parent){ // Initialize the count int count = 0; for (int i : adj[node]) { if (i != parent) { // Repeat for every child count += dfs(i, node); } } // Increase the count if // current node has odd // number of divisors if (hasOddNumberOfDivisors(a[node])) ++count; ans[node] = count; return count;}// Driver Codepublic static void main(String[] args){ int n = 5; int[] q = {4, 1, 5, 3}; for (int i = 0; i < adj.length; i++) adj[i] = new Vector<Integer>(); // Adjacency List adj[1].add(2); adj[2].add(1); adj[2].add(3); adj[3].add(2); adj[3].add(4); adj[4].add(3); adj[1].add(5); adj[5].add(1); a[1] = 4; a[2] = 9; a[3] = 14; a[4] = 100; a[5] = 5; // Function call dfs(1, -1); for (int i = 0; i < q.length; i++) { System.out.print(ans[q[i]] + " "); }}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to count the# number of nodes having odd# number of divisors for each queryimport mathN = 100001 # Adjacency list# for tree.adj = [[] for i in range(N)] # Array for values and# answer at ith node.a = [0 for i in range(N)]ans = [0 for i in range(N)] # Function to check whether N# has odd divisors or notdef hasOddNumberOfDivisors(n): if (math.sqrt(n) == int(math.sqrt(n))): return True return False # DFS function to pre-compute# the answersdef dfs(node, parent): # Initialize the count count = 0 for i in adj[node]: if (i != parent): # Repeat for every child count += dfs(i, node) # Increase the count if current node # has odd number of divisors if (hasOddNumberOfDivisors(a[node])): count += 1 ans[node] = count return count# Driver Codeif __name__=="__main__": n = 5 i = 0 q = [ 4, 1, 5, 3 ] # Adjacency List adj[1].append(2) adj[2].append(1) adj[2].append(3) adj[3].append(2) adj[3].append(4) adj[4].append(3) adj[1].append(5) adj[5].append(1) a[1] = 4 a[2] = 9 a[3] = 14 a[4] = 100 a[5] = 5 # Function call dfs(1, -1) for i in range(len(q)): print(ans[q[i]], end = ' ') # This code is contributed by rutvik_56 |
C#
// C# implementation to // count the number of nodes // having odd number of // divisors for each queryusing System;using System.Collections.Generic;class GFG{static readonly int N = 100001;// Adjacency list// for tree.static List<int> []adj = new List<int>[N];// Array for values and// answer at ith node.static int []a = new int[N];static int []ans = new int[N];// Function to check whether N// has odd divisors or notstatic bool hasOddNumberOfDivisors(int n){ if ((double)Math.Sqrt(n) == (int)Math.Sqrt(n)) return true; return false;}// DFS function to // pre-compute the answersstatic int dfs(int node, int parent){ // Initialize the count int count = 0; foreach (int i in adj[node]) { if (i != parent) { // Repeat for every child count += dfs(i, node); } } // Increase the count if // current node has odd // number of divisors if (hasOddNumberOfDivisors(a[node])) ++count; ans[node] = count; return count;}// Driver Codepublic static void Main(String[] args){ int n = 5; int[] q = {4, 1, 5, 3}; for (int i = 0; i < adj.Length; i++) adj[i] = new List<int>(); // Adjacency List adj[1].Add(2); adj[2].Add(1); adj[2].Add(3); adj[3].Add(2); adj[3].Add(4); adj[4].Add(3); adj[1].Add(5); adj[5].Add(1); a[1] = 4; a[2] = 9; a[3] = 14; a[4] = 100; a[5] = 5; // Function call dfs(1, -1); for (int i = 0; i < q.Length; i++) { Console.Write(ans[q[i]] + " "); }}}// This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation to // count the number of nodes // having odd number of // divisors for each query let N = 100001; // Adjacency list // for tree. let adj = new Array(N); // Array for values and // answer at ith node. let a = new Array(N); let ans = new Array(N); // Function to check whether N // has odd divisors or not function hasOddNumberOfDivisors(n) { if (Math.sqrt(n) == parseInt(Math.sqrt(n), 10)) return true; return false; } // DFS function to // pre-compute the answers function dfs(node, parent) { // Initialize the count let count = 0; for (let i = 0; i < adj[node].length; i++) { if (adj[node][i] != parent) { // Repeat for every child count += dfs(adj[node][i], node); } } // Increase the count if // current node has odd // number of divisors if (hasOddNumberOfDivisors(a[node])) ++count; ans[node] = count; return count; } let n = 5; let q = [4, 1, 5, 3]; for (let i = 0; i < adj.length; i++) adj[i] = []; // Adjacency List adj[1].push(2); adj[2].push(1); adj[2].push(3); adj[3].push(2); adj[3].push(4); adj[4].push(3); adj[1].push(5); adj[5].push(1); a[1] = 4; a[2] = 9; a[3] = 14; a[4] = 100; a[5] = 5; // Function call dfs(1, -1); for (let i = 0; i < q.length; i++) { document.write(ans[q[i]] + " "); }// This code is contributed by decode2207.</script> |
Output
1 3 0 1
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
