मान लीजिए हमारे पास एक सरणी A है जहां दूसरी सरणी के हर संभव जोड़े का GCD दिया गया है, हमें मूल संख्याओं को ढूंढना है जिनका उपयोग दी गई GCD सरणी की गणना के लिए किया गया है।
तो, यदि इनपुट A = [6, 1, 1, 13] की तरह है, तो आउटपुट [13, 6] होगा क्योंकि gcd(13, 13) 13 है, gcd(13, 6) 1 है, gcd(6, 13) 1 है, gcd(6, 6) 6 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
n := A का आकार
सरणी A को अवरोही क्रम में क्रमबद्ध करें
occurrence := A[0] के आकार की एक सरणी और 0 से भरें
i के लिए 0 से n की सीमा में, करें
occurrence[A[i]] := occurrence[A[i]] + 1
size := n के वर्गमूल का पूर्णांक भाग
res := A के आकार के समान आकार की एक सरणी और 0 से भरें
l := 0
i के लिए 0 से n की सीमा में, करें
यदि occurrence[A[i]] > 0, तो
res[l] := A[i]
occurrence[res[l]] := occurrence[res[l]] - 1
l := l + 1
j के लिए 0 से l की सीमा में, करें
यदि i, j के समान नहीं है, तो
g := gcd(A[i], res[j])
occurrence[g] := occurrence[g] - 2
res[इंडेक्स 0 से size तक] लौटाएं
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
from math import sqrt, gcd def get_actual_array(A): n = len(A) A.sort(reverse = True) occurrence = [0 for i in range(A[0] + 1)] for i in range(n): occurrence[A[i]] += 1 size = int(sqrt(n)) res = [0 for i in range(len(A))] l = 0 for i in range(n): if (occurrence[A[i]] > 0): res[l] = A[i] occurrence[res[l]] -= 1 l += 1 for j in range(l): if (i != j): g = gcd(A[i], res[j]) occurrence[g] -= 2 return res[:size] A = [6, 1, 1, 13] print(get_actual_array(A))
इनपुट
[6, 1, 1, 13]
आउटपुट
[13, 6]
