Welcome to Subscribe On Youtube

3312. Sorted GCD Pair Queries

Description

You are given an integer array nums of length n and an integer array queries.

Let gcdPairs denote an array obtained by calculating the GCD of all possible pairs (nums[i], nums[j]), where 0 <= i < j < n, and then sorting these values in ascending order.

For each query queries[i], you need to find the element at index queries[i] in gcdPairs.

Return an integer array answer, where answer[i] is the value at gcdPairs[queries[i]] for each query.

The term gcd(a, b) denotes the greatest common divisor of a and b.

 

Example 1:

Input: nums = [2,3,4], queries = [0,2,2]

Output: [1,2,2]

Explanation:

gcdPairs = [gcd(nums[0], nums[1]), gcd(nums[0], nums[2]), gcd(nums[1], nums[2])] = [1, 2, 1].

After sorting in ascending order, gcdPairs = [1, 1, 2].

So, the answer is [gcdPairs[queries[0]], gcdPairs[queries[1]], gcdPairs[queries[2]]] = [1, 2, 2].

Example 2:

Input: nums = [4,4,2,1], queries = [5,3,1,0]

Output: [4,2,1,1]

Explanation:

gcdPairs sorted in ascending order is [1, 1, 1, 2, 2, 4].

Example 3:

Input: nums = [2,2], queries = [0,0]

Output: [2,2]

Explanation:

gcdPairs = [2].

 

Constraints:

  • 2 <= n == nums.length <= 105
  • 1 <= nums[i] <= 5 * 104
  • 1 <= queries.length <= 105
  • 0 <= queries[i] < n * (n - 1) / 2

Solutions

We can preprocess to obtain the occurrence count of the greatest common divisor (GCD) of all pairs in the array $\textit{nums}$, recorded in the array $\textit{cntG}$. Then, we calculate the prefix sum of the array $\textit{cntG}$. Finally, for each query, we can use binary search to find the index of the first element in the array $\textit{cntG}$ that is greater than $\textit{queries}[i]$, which is the answer.

Let $\textit{mx}$ denote the maximum value in the array $\textit{nums}$, and let $\textit{cnt}$ record the occurrence count of each number in the array $\textit{nums}$. Let $\textit{cntG}[i]$ denote the number of pairs in the array $\textit{nums}$ whose GCD is equal to $i$. To calculate $\textit{cntG}[i]$, we can follow these steps:

  1. Calculate the occurrence count $v$ of multiples of $i$ in the array $\textit{nums}$. Then, the number of pairs formed by any two elements from these multiples must have a GCD that is a multiple of $i$, i.e., $\textit{cntG}[i]$ needs to be increased by $v \times (v - 1) / 2$;
  2. We need to exclude pairs whose GCD is a multiple of $i$ and greater than $i$. Therefore, for multiples $j$ of $i$, we need to subtract $\textit{cntG}[j]$.

The above steps require us to traverse $i$ from large to small so that when calculating $\textit{cntG}[i]$, we have already calculated all $\textit{cntG}[j]$.

Finally, we calculate the prefix sum of the array $\textit{cntG}$, and for each query, we can use binary search to find the index of the first element in the array $\textit{cntG}$ that is greater than $\textit{queries}[i]$, which is the answer.

The time complexity is $O(n + (M + q) \times \log M)$, and the space complexity is $O(M)$. Here, $n$ and $M$ represent the length and the maximum value of the array $\textit{nums}$, respectively, and $q$ represents the number of queries.

  • class Solution {
        public int[] gcdValues(int[] nums, long[] queries) {
            int mx = Arrays.stream(nums).max().getAsInt();
            int[] cnt = new int[mx + 1];
            long[] cntG = new long[mx + 1];
            for (int x : nums) {
                ++cnt[x];
            }
            for (int i = mx; i > 0; --i) {
                int v = 0;
                for (int j = i; j <= mx; j += i) {
                    v += cnt[j];
                    cntG[i] -= cntG[j];
                }
                cntG[i] += 1L * v * (v - 1) / 2;
            }
            for (int i = 2; i <= mx; ++i) {
                cntG[i] += cntG[i - 1];
            }
            int m = queries.length;
            int[] ans = new int[m];
            for (int i = 0; i < m; ++i) {
                ans[i] = search(cntG, queries[i]);
            }
            return ans;
        }
    
        private int search(long[] nums, long x) {
            int n = nums.length;
            int l = 0, r = n;
            while (l < r) {
                int mid = l + r >> 1;
                if (nums[mid] > x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            return l;
        }
    }
    
    
  • class Solution {
    public:
        vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {
            int mx = ranges::max(nums);
            vector<int> cnt(mx + 1);
            vector<long long> cntG(mx + 1);
            for (int x : nums) {
                ++cnt[x];
            }
            for (int i = mx; i; --i) {
                long long v = 0;
                for (int j = i; j <= mx; j += i) {
                    v += cnt[j];
                    cntG[i] -= cntG[j];
                }
                cntG[i] += 1LL * v * (v - 1) / 2;
            }
            for (int i = 2; i <= mx; ++i) {
                cntG[i] += cntG[i - 1];
            }
            vector<int> ans;
            for (auto&& q : queries) {
                ans.push_back(upper_bound(cntG.begin(), cntG.end(), q) - cntG.begin());
            }
            return ans;
        }
    };
    
    
  • class Solution:
        def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:
            mx = max(nums)
            cnt = Counter(nums)
            cnt_g = [0] * (mx + 1)
            for i in range(mx, 0, -1):
                v = 0
                for j in range(i, mx + 1, i):
                    v += cnt[j]
                    cnt_g[i] -= cnt_g[j]
                cnt_g[i] += v * (v - 1) // 2
            s = list(accumulate(cnt_g))
            return [bisect_right(s, q) for q in queries]
    
    
  • func gcdValues(nums []int, queries []int64) (ans []int) {
    	mx := slices.Max(nums)
    	cnt := make([]int, mx+1)
    	cntG := make([]int, mx+1)
    	for _, x := range nums {
    		cnt[x]++
    	}
    	for i := mx; i > 0; i-- {
    		var v int
    		for j := i; j <= mx; j += i {
    			v += cnt[j]
    			cntG[i] -= cntG[j]
    		}
    		cntG[i] += v * (v - 1) / 2
    	}
    	for i := 2; i <= mx; i++ {
    		cntG[i] += cntG[i-1]
    	}
    	for _, q := range queries {
    		ans = append(ans, sort.SearchInts(cntG, int(q)+1))
    	}
    	return
    }
    
    

All Problems

All Solutions