Given an array arr[] of n integers, where each integer is greater than 1. The task is to find the number of Full binary tree from the given integers, such that each non-leaf node value is the product of its children value.
Note: Each integer can be used multiple times in a full binary tree. The answer can be large, return  answer modulo 1000000007
Example 1:
Input:
n = 4
arr[] = {2, 3, 4, 6}
Output:
7
Explanation:
There are 7 full binary tree with
the given product property.
Four trees with single nodes
2  3  4  6
Three trees with three nodes
    4   
   / \
  2   2 ,
   6    
  / \
 2   3 ,
   6
  / \
 3   2
 
Example 2:
Input: 
n = 3
arr[] = {2, 4, 5} 
Output: 4
Explanation: There are 4 full binary tree
with the given product property. 
Three trees with single nodes 2 4 5
One tree with three nodes
   4
  / \
 2  2
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function numoffbt() which takes the array arr[]and its size n as inputs and returns the number of Full binary tree.
Expected Time Complexity: O(n. Log(n))
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ n ≤ 10^{5}
2 ≤ arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def numoffbt(self, arr, n):

     # Your code goes here



Solutions:
class Solution:

	def numoffbt(self, arr, n):
		d = {x: 1 for x in arr}
		a = sorted(d.keys())
		ans = 0
		for i in a:
			for j in range(2 * i, min(i * i + 1, a[-1] + 1), i):
				if j in d and j // i in d:
					temp = d[i] * d[j // i]
					if i * i != j:
						temp = 2 * temp
					d[j] += temp
			ans += d[i]
		return ans % 1000000007


class Solution:

	def numoffbt(self, arr, n):
		maxi = max(arr)
		mini = min(arr)
		dp = [0] * (maxi + 1)
		for i in arr:
			dp[i] = 1
		output = 0
		for i in range(mini, maxi + 1):
			if dp[i] != 0:
				j = i + i
				while j <= maxi and j / i <= i:
					if dp[j] != 0:
						dp[j] += dp[i] * dp[j // i]
						if i != j / i:
							dp[j] += dp[i] * dp[j // i]
					j += i
				output += dp[i]
				output %= 1000000007
		return output


import math

class Solution:

	def numoffbt(self, arr, n):
		ans = 0
		mod = 10 ** 9 + 7
		maxi = max(arr)
		mini = min(arr)
		d = {x: 1 for x in arr}
		a = sorted(d.keys())
		for i in a:
			for j in range(2 * i, min(i * i + 1, a[-1] + 1), i):
				if j in d and j // i in d:
					tmp = d[i] * d[j // i]
					if i * i != j:
						tmp = 2 * tmp
					d[j] += tmp
			ans += d[i]
		return ans % mod


class Solution:

	def numoffbt(self, arr, n):
		mod = 10 ** 9 + 7
		maximum = max(arr)
		dp = [0 for i in range(maximum + 1)]
		for i in arr:
			dp[i] = 1
		ans = 0
		for i in range(2, maximum + 1):
			if dp[i] == 0:
				continue
			ans += dp[i]
			for j in range(2 * i, maximum + 1, i):
				if dp[j] == 0 or j // i > i:
					continue
				if i != j // i:
					dp[j] += dp[i] * dp[j // i]
				dp[j] += dp[i] * dp[j // i]
				dp[j] = dp[j] % mod
		return ans % mod


class Solution:

	def numoffbt(self, arr, n):
		mod = 10 ** 9 + 7
		maxrange = max(arr)
		minrange = min(arr)
		present = {arr[i]: True for i in range(0, n)}
		dp = [0] * (maxrange + 2)
		for i in range(0, n):
			present[arr[i]] = True
			dp[arr[i]] = 1
		ans = 0
		for i in range(minrange, maxrange + 1):
			if i in present:
				j = 2 * i
				while j <= i * i and j <= maxrange:
					if j in present:
						if i != j // i:
							dp[j] = (dp[j] + 2 * (dp[i] * dp[j // i])) % mod
						elif i == j // i:
							dp[j] = (dp[j] + dp[i] * dp[j // i]) % mod
					j += i
				ans = (ans + dp[i]) % mod
		return ans


class Solution:

	def numoffbt(self, arr, n):
		N = max(arr) + 2
		mod = int(1000000000.0) + 7
		chk = [0] * N
		ans = 0
		for i in range(n):
			chk[arr[i]] = 1
		for i in range(N):
			if chk[i]:
				for j in range(2 * i, N, i):
					if chk[j] == 0 or j // i > i:
						continue
					if j // i != i:
						chk[j] = (chk[j] + 2 * (chk[i] * chk[j // i] % mod) % mod) % mod
					else:
						chk[j] = (chk[j] + chk[i] * chk[j // i] % mod) % mod
		for i in range(N):
			ans = (ans + chk[i]) % mod
		return ans


class Solution:

	def numoffbt(self, arr, n):
		maxvalue = -float('inf')
		minvalue = float('inf')
		for i in range(n):
			maxvalue = max(maxvalue, arr[i])
			minvalue = min(minvalue, arr[i])
		mark = [0] * (maxvalue + 2)
		value = [0] * (maxvalue + 2)
		for i in range(n):
			mark[arr[i]] = 1
			value[arr[i]] = 1
		ans = 0
		mod = 10 ** 9 + 7
		for i in range(minvalue, maxvalue + 1):
			if mark[i]:
				j = i + i
				while j <= maxvalue and j // i <= i:
					if not mark[j]:
						j += i
						continue
					value[j] = (value[j] + value[i] * value[j // i]) % mod
					if i != j // i:
						value[j] = (value[j] + value[i] * value[j // i]) % mod
					j += i
			ans = (ans + value[i]) % mod
		return ans


class Solution:

	def numoffbt(self, arr, n):
		min1 = 9999999999
		max1 = -999999999
		for i in arr:
			min1 = min(min1, i)
			max1 = max(max1, i)
		dp = [0] * (max1 + 1)
		for i in range(n):
			dp[arr[i]] = 1
		c = 0
		for i in range(min1, max1 + 1):
			if dp[i] > 0:
				j = i + i
				while j <= max1 and j <= i * i:
					if dp[j] > 0:
						dp[j] = dp[j] + dp[i] * dp[j // i]
						if i != j // i:
							dp[j] = dp[j] + dp[i] * dp[j // i]
					j = j + i
		return sum(dp) % 1000000007


def binary_search(arr, low, high, x):
	if high >= low:
		mid = (high + low) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return binary_search(arr, low, mid - 1, x)
		else:
			return binary_search(arr, mid + 1, high, x)
	else:
		return -1

class Solution:

	def numoffbt(self, arr, n):
		MOD1 = 1000000007
		max_var = max(arr)
		min_var = min(arr)
		dp1 = [0] * (max_var + 1)
		for i in arr:
			dp1[i] = 1
		ans1 = 0
		for i in range(min_var, max_var + 1):
			if dp1[i] != 0:
				j = 2 * i
				while j <= max_var and j // i <= i:
					if dp1[j] != 0:
						dp1[j] += dp1[i] * dp1[j // i]
						if j // i != i:
							dp1[j] += dp1[i] * dp1[j // i]
					j += i
				ans1 += dp1[i]
				ans1 = ans1 % MOD1
		return ans1


class Solution:

	def numoffbt(self, arr, n):
		d = {x: 1 for x in arr}
		a = sorted(d.keys())
		ans = 0
		mod = 10 ** 9 + 7
		for i in a:
			for j in range(2 * i, min(i * i + 1, a[-1] + 1), i):
				if j in d and j // i in d:
					temp = d[i] * d[j // i]
					if i * i != j:
						temp = 2 * temp
					d[j] += temp
			ans += d[i]
		return ans % mod


class Solution:

	def numoffbt(self, arr, n):
		mod = 1000000007
		dicti = {x: 1 for x in arr}
		newarr = sorted(dicti.keys())
		sol = 0
		for i in newarr:
			for j in range(2 * i, min(i * i + 1, newarr[-1] + 1), i):
				if j in dicti and j // i in dicti:
					temp = dicti[i] * dicti[j // i]
					if i * i != j:
						temp = 2 * temp
					dicti[j] += temp
			sol += dicti[i]
		return sol % 1000000007


class Solution:

	def numoffbt(self, arr, n):
		memo = {num: 1 for num in arr}
		keys = sorted(memo.keys())
		count = 0
		mod = 10 ** 9 + 7
		for i in keys:
			for j in range(2 * i, min(i * i + 1, keys[-1] + 1), i):
				if j in memo and j // i in memo:
					temp = memo[i] * memo[j // i]
					if i * i != j:
						temp = 2 * temp
					memo[j] += temp
			count += memo[i]
		return count % mod
		return count % 1000000007


class Solution:

	def numoffbt(self, arr, n):
		ans = 0
		min_a = min(arr)
		max_a = max(arr)
		dp = [0] * (max_a + 1)
		for i in arr:
			dp[i] = 1
		for i in range(min_a, max_a + 1):
			if dp[i] != 0:
				j = i + i
				while j <= max_a and j / i <= i:
					if dp[j] != 0:
						dp[j] += dp[i] * dp[j // i]
						if j / i != i:
							dp[j] += dp[i] * dp[j // i]
					j += i
				ans = ans + dp[i]
		return ans % 1000000007