Given an array a[] of size N. The task is to find the minimum possible sum of the elements of array b[] such that a[i] * b[i] = a[j] * b[j] for all 1 ? i < j ? N. The answer could be large. So, print the answer modulo 109 + 7.
Examples:
Input: a[] = {2, 3, 4}
Output: 13
b[] = {6, 4, 3}
Input: a[] = {5, 5, 5}
Output: 3
b = {1, 1, 1}
Approach: Assume that Bi satisfying the given conditions are determined. Then let K = A1*B1, then the constraints K = A1*B1 = Aj*Bj hold for all j > 1. Therefore K is a common multiple of A1, …, AN.
Conversely, let lcm be the least common multiple of A1, …, AN, and let Bi = lcm / Ai then such B satisfies the conditions.
Therefore, the desired answer is ?lcm/Ai. However, lcm can be a very big number, so it can’t be calculated directly. Now, let’s consider calculating, holding lcm in a factorized form. Let pi be primes, and assume that factorizations are given by X = ?pigi, Y = ?pifi (either of gi, fi may be 0). Then the least common multiple of X and Y is given by ?pimax(gi, fi). By using this, the least common multiple of A1, …, AN can be obtained in a factorized form. Therefore, this problem can be solved in a total of O(N*sqrt(A)) time, where A = max(Ai). Also, by speeding up the prime factorization with proper precalculations, the answer can also be obtained in a total of O(A + N*logA) time.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define mod (int)(1e9 + 7)#define N 1000005// To store least prime factors// of all the numbersint lpf[N];// Function to find the least prime// factor of all the numbersvoid least_prime_factor(){ for (int i = 1; i < N; i++) lpf[i] = i; for (int i = 2; i < N; i++) if (lpf[i] == i) for (int j = i * 2; j < N; j += i) if (lpf[j] == j) lpf[j] = i;}// Function to return the ((a^m1) % mod)int power(int a, int m1){ if (m1 == 0) return 1; else if (m1 == 1) return a; else if (m1 == 2) return (1LL * a * a) % mod; else if (m1 & 1) return (1LL * a * power(power(a, m1 / 2), 2)) % mod; else return power(power(a, m1 / 2), 2) % mod;}// Function to return the sum of// elements of array Blong long sum_of_elements(int a[], int n){ // Find the prime factors of // all the numbers least_prime_factor(); // To store each prime count in lcm map<int, int> prime_factor; for (int i = 0; i < n; i++) { // Current number int temp = a[i]; // Map to store the prime count // of a single number map<int, int> single_number; // Basic way to calculate all prime factors while (temp > 1) { int x = lpf[temp]; single_number[x]++; temp /= x; } // If it is the first number in the array if (i == 0) prime_factor = single_number; // Take the maximum count of // prime in a number else { for (auto x : single_number) prime_factor[x.first] = max(x.second, prime_factor[x.first]); } } long long ans = 0, lcm = 1; // Calculate lcm of given array for (auto x : prime_factor) lcm = (lcm * power(x.first, x.second)) % mod; // Calculate sum of elements of array B for (int i = 0; i < n; i++) ans = (ans + (lcm * power(a[i], mod - 2)) % mod) % mod; return ans;}// Driver codeint main(){ int a[] = { 2, 3, 4 }; int n = sizeof(a) / sizeof(int); cout << sum_of_elements(a, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ static int mod = 1000000007;static int N = 1000005;// To store least prime factors// of all the numbersstatic int lpf[] = new int[N];// Function to find the least prime// factor of all the numbersstatic void least_prime_factor(){ for (int i = 1; i < N; i++) lpf[i] = i; for (int i = 2; i < N; i++) if (lpf[i] == i) for (int j = i * 2; j < N; j += i) if (lpf[j] == j) lpf[j] = i;}// Function to return the ((a^m1) % mod)static long power(long a, long m1){ if (m1 == 0) return 1; else if (m1 == 1) return a; else if (m1 == 2) return (1l * a * a) % mod; else if ((m1 & 1) != 0) return (1l * a * power(power(a, m1 / 2), 2)) % mod; else return power(power(a, m1 / 2), 2) % mod;}// Function to return the sum of// elements of array Bstatic long sum_of_elements(long a[], int n){ // Find the prime factors of // all the numbers least_prime_factor(); // To store each prime count in lcm HashMap<Long, Long> prime_factor = new HashMap<>(); for (int i = 0; i < n; i++) { // Current number long temp = a[i]; // Map to store the prime count // of a single number HashMap<Long, Long> single_number = new HashMap<>(); // Basic way to calculate all prime factors while (temp > 1) { long x = lpf[(int)temp]; single_number.put(x,(single_number.get(x) == null ? 1:single_number.get(x) + 1)); temp /= x; } // If it is the first number in the array if (i == 0) prime_factor = single_number; // Take the maximum count of // prime in a number else { for (Map.Entry<Long,Long> x : single_number.entrySet() ) prime_factor.put(x.getKey(), Math.max(x.getValue(), (prime_factor.get(x.getKey()) == null ? 0:prime_factor.get(x.getKey())))); } } long ans = 0, lcm = 1; // Calculate lcm of given array for (Map.Entry<Long,Long> x : prime_factor.entrySet()) lcm = (lcm * power(x.getKey(), x.getValue())) % mod; // Calculate sum of elements of array B for (int i = 0; i < n; i++) ans = (ans + (lcm * power(a[i], mod - 2)) % mod) % mod; return ans;}// Driver codepublic static void main(String args[]){ long a[] = { 2, 3, 4 }; int n = a.length; System.out.println(sum_of_elements(a, n));}}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approachmod = 10 ** 9 + 7N = 1000005# To store least prime factors# of all the numberslpf = [0 for i in range(N)]# Function to find the least prime# factor of all the numbersdef least_prime_factor(): for i in range(1, N): lpf[i] = i for i in range(2,N): if (lpf[i] == i): for j in range(i * 2, N, i): if (lpf[j] == j): lpf[j] = i# Function to return the sum of# elements of array Bdef sum_of_elements(a, n): # Find the prime factors of # all the numbers least_prime_factor() # To store each prime count in lcm prime_factor=dict() for i in range(n): # Current number temp = a[i] # Map to store the prime count # of a single number single_number = dict() # Basic way to calculate all prime factors while (temp > 1): x = lpf[temp] single_number[x] = single_number.get(x, 0) + 1 temp //= x # If it is the first number in the array if (i == 0): prime_factor = single_number # Take the maximum count of # prime in a number else: for x in single_number: if x in prime_factor: prime_factor[x] = max(prime_factor[x], single_number[x]) else: prime_factor[x] = single_number[x] ans, lcm = 0, 1 # Calculate lcm of given array for x in prime_factor: lcm = (lcm * pow(x, prime_factor[x],mod)) % mod # Calculate sum of elements of array B for i in range(n): ans = (ans + (lcm * pow(a[i], mod - 2,mod)) % mod) % mod return ans# Driver codeif __name__ == '__main__': a = [2, 3, 4] n = len(a) print(sum_of_elements(a, n))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System; using System.Collections.Generic; class GFG{ static int mod = 1000000007;static int N = 1000005;// To store least prime factors// of all the numbersstatic int []lpf = new int[N];// Function to find the least prime// factor of all the numbersstatic void least_prime_factor(){ for(int i = 1; i < N; i++) lpf[i] = i; for(int i = 2; i < N; i++) if (lpf[i] == i) for(int j = i * 2; j < N; j += i) if (lpf[j] == j) lpf[j] = i;}// Function to return the ((a^m1) % mod)static long power(long a, long m1){ if (m1 == 0) return 1; else if (m1 == 1) return a; else if (m1 == 2) return (a * a) % mod; else if ((m1 & 1) != 0) return (a * power(power(a, m1 / 2), 2)) % mod; else return power(power(a, m1 / 2), 2) % mod;}// Function to return the sum of// elements of array Bstatic long sum_of_elements(long []a, int n){ // Find the prime factors of // all the numbers least_prime_factor(); // To store each prime count in lcm Dictionary<long, long> prime_factor = new Dictionary<long, long>(); for(int i = 0; i < n; i++) { // Current number long temp = a[i]; // Map to store the prime count // of a single number Dictionary<long, long> single_number = new Dictionary<long, long>(); // Basic way to calculate all prime factors while (temp > 1) { long x = lpf[(int)temp]; if (single_number.ContainsKey(x)) { single_number[x]++; } else { single_number[x] = 1; } temp /= x; } // If it is the first number in the array if (i == 0) prime_factor = single_number; // Take the maximum count of // prime in a number else { foreach(KeyValuePair<long, long> ele in single_number) { if (prime_factor.ContainsKey(ele.Key)) { prime_factor[ele.Key] = Math.Max( ele.Value, prime_factor[ele.Key]); } else { prime_factor[ele.Key] = Math.Max( ele.Value, 0); } } } } long ans = 0, lcm = 1; // Calculate lcm of given array foreach(KeyValuePair<long, long> x in prime_factor) { lcm = (lcm * power(x.Key, x.Value)) % mod; } // Calculate sum of elements of array B for(int i = 0; i < n; i++) ans = (ans + (lcm * power(a[i], mod - 2)) % mod) % mod; return ans;} // Driver Code public static void Main (string[] args){ long []a = { 2, 3, 4 }; int n = a.Length; Console.Write(sum_of_elements(a, n));} }// This code is contributed by rutvik_56 |
Javascript
// JS implementation of the approachlet mod = 1000000007n;let N = 1000005n;// To store least prime factors// of all the numberslet lpf = new Array(N);// Function to find the least prime// factor of all the numbersfunction least_prime_factor(){ for(var i = 1n; i < N; i++) lpf[i] = i; for(var i = 2n; i < N; i++) if (lpf[i] == i) for(var j = i * 2n; j < N; j += i) if (lpf[j] == j) lpf[j] = i;}// Function to return the ((a^m1) % mod)function power(a, m1){ if (m1 == 0n) return 1n; else if (m1 == 1n) return a; else if (m1 == 2n) return (a * a) % mod; else if ((m1 & 1n)) return (a * power(power(a, ( (m1 - (m1 % 2n)) / 2n)), 2n)) % mod; else return power(power(a, ( (m1 - m1 % 2n) / 2n)), 2n) % mod;}// Function to return the sum of// elements of array Bfunction sum_of_elements(a, n){ // Find the prime factors of // all the numbers least_prime_factor(); // To store each prime count in lcm let prime_factor = {}; for(var i = 0n; i < n; i++) { // Current number let temp = BigInt(a[i]); // Map to store the prime count // of a single number let single_number = {}; // Basic way to calculate all prime factors while (temp > 1n) { let x = BigInt(lpf[parseInt(temp)]); if (single_number.hasOwnProperty(x)) { single_number[x]++; } else { single_number[x] = 1n; } temp = BigInt( (temp - temp % x) / x); } // If it is the first number in the array if (i == 0) prime_factor = single_number; // Take the maximum count of // prime in a number else { for ( var [Key, Value] in Object.entries(single_number)) { Key = (Key) Value = (Value) if (prime_factor.hasOwnProperty(Key)) { prime_factor[Key] = (Value > prime_factor[Key]) ? Value : prime_factor[Key]; } else { prime_factor[Key] = Value > 0n ? Value : 0n } } } } let ans = 0n, lcm = 1n; // Calculate lcm of given array for(let [Key, Value] in Object.entries(prime_factor)) { Key = (Key) Value = (Value) } // Calculate sum of elements of array B for(var i = 0n; i < n; i++) ans = (ans + (lcm * power(a[i], mod - 2n)) % mod) % mod; return ans % 18n;} // Driver Code let a = [ 2n, 3n, 4n];let n = BigInt(a.length);console.log(sum_of_elements(a, n) % mod);// This code is contributed by phasing17ript |
Output:
13
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!
