Dada una array de enteros arr[] de tamaño N , la tarea es calcular el número total de máximos comunes divisores (MCD) distintos entre todas las subsecuencias no vacías de arr[] .
Ejemplos:
Entrada: arr[]={3,4,8} N=3
Salida:
4
Explicación:
Las diferentes subsecuencias no vacías posibles son {3}, {4}, {8}, {3,4}, {4, 8}, {3,8}, {3,4,8} y sus GCD correspondientes son 3,4,8,1,4,1,1.
Por lo tanto, el número total de GCD distintos es 4 (1,3,4,8).Entrada: arr[]={3,11,14,6,12}, N=5
Salida:
7
Enfoque ingenuo: el enfoque ingenuo es encontrar todas las subsecuencias, calcular los GCD para cada una de ellas y, finalmente, calcular el número total de GCD distintos .
Complejidad de tiempo: O(2 N .Log(M)), donde M es el elemento más grande de la array.
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- El GCD más grande posible no puede exceder el elemento más grande de la array (por ejemplo, M ). Por lo tanto, todos los GCD posibles se encuentran entre 1 y M .
- Al iterar sobre todos los valores posibles de GCD , es decir, de 1 a M , y verificar si hay múltiplos de i que estén presentes en la array y tengan un GCD igual a i , se puede resolver el problema.
Siga los pasos a continuación para resolver el problema:
- Inicializar una respuesta variable a 0.
- Calcule y almacene el elemento máximo en arr en una variable, digamos M .
- Almacene todos los elementos de arr en un mapa Mp para acceso en tiempo constante.
- Iterar a través de todos los valores posibles de GCD , es decir, de 1 a M , usando la variable i , y hacer lo siguiente:
- Itere a través de los múltiplos de M presentes en arr , usando la variable j , y haga lo siguiente:
- Si el GCD se convierte en i en cualquier punto, incremente ans y rompa.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the number
// of distinct GCDs among all
// non-empty subsequences of an array
int distinctGCDs(int arr[], int N)
{
// variables to store the largest element
// in array and the required count
int M = -1, ans = 0;
// Map to store whether
// a number is present in A
map<int, int> Mp;
// calculate largest number
// in A and mapping A to Mp
for (int i = 0; i < N; i++) {
M = max(M, arr[i]);
Mp[arr[i]] = 1;
}
// iterate over all possible values of GCD
for (int i = 1; i <= M; i++) {
// variable to check current GCD
int currGcd = 0;
// iterate over all multiples of i
for (int j = i; j <= M; j += i) {
// If j is present in A
if (Mp[j]) {
// calculate gcd of all encountered
// multiples of i
currGcd = __gcd(currGcd, j);
// current GCD is possible
if (currGcd == i) {
ans++;
break;
}
}
}
}
// return answer
return ans;
}
// Driver code
int main()
{
// Input
int arr[] = { 3, 11, 14, 6, 12 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function calling
cout << distinctGCDs(arr, N) << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
// Function to calculate the number
// of distinct GCDs among all
// non-empty subsequences of an array
static int distinctGCDs(int []arr, int N)
{
// Variables to store the largest element
// in array and the required count
int M = -1, ans = 0;
// Map to store whether
// a number is present in A
HashMap<Integer,
Integer> Mp = new HashMap<Integer,
Integer>();
// Calculate largest number
// in A and mapping A to Mp
for(int i = 0; i < N; i++)
{
M = Math.max(M, arr[i]);
if (Mp.containsKey(arr[i]))
Mp.put(arr[i],1);
else
Mp.put(arr[i],0);
}
// Iterate over all possible values of GCD
for(int i = 1; i <= M; i++)
{
// Variable to check current GCD
int currGcd = 0;
// Iterate over all multiples of i
for(int j = i; j <= M; j += i)
{
// If j is present in A
if (Mp.containsKey(j))
{
// Calculate gcd of all encountered
// multiples of i
currGcd = gcd(currGcd, j);
// Current GCD is possible
if (currGcd == i)
{
ans++;
break;
}
}
}
}
// Return answer
return ans;
}
// Driver code
public static void main(String [] args)
{
// Input
int []arr = { 3, 11, 14, 6, 12 };
int N = arr.length;
// Function calling
System.out.println(distinctGCDs(arr, N));
}
}
// This code is contributed by ukasp.
Python3
# Python 3 program for the above approach
from math import gcd
# Function to calculate the number
# of distinct GCDs among all
# non-empty subsequences of an array
def distinctGCDs(arr, N):
# variables to store the largest element
# in array and the required count
M = -1
ans = 0
# Map to store whether
# a number is present in A
Mp = {}
# calculate largest number
# in A and mapping A to Mp
for i in range(N):
M = max(M, arr[i])
Mp[arr[i]] = 1
# iterate over all possible values of GCD
for i in range(1, M + 1, 1):
# variable to check current GCD
currGcd = 0
# iterate over all multiples of i
for j in range(i, M + 1, i):
# If j is present in A
if (j in Mp):
# calculate gcd of all encountered
# multiples of i
currGcd = gcd(currGcd, j)
# current GCD is possible
if (currGcd == i):
ans += 1
break
# return answer
return ans
# Driver code
if __name__ == '__main__':
# Input
arr = [3, 11, 14, 6, 12]
N = len(arr)
# Function calling
print(distinctGCDs(arr, N))
# This code is contributed by bgangwar59.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
// Function to calculate the number
// of distinct GCDs among all
// non-empty subsequences of an array
static int distinctGCDs(int []arr, int N)
{
// Variables to store the largest element
// in array and the required count
int M = -1, ans = 0;
// Map to store whether
// a number is present in A
Dictionary<int,
int> Mp = new Dictionary<int,
int>();
// Calculate largest number
// in A and mapping A to Mp
for(int i = 0; i < N; i++)
{
M = Math.Max(M, arr[i]);
if (Mp.ContainsKey(arr[i]))
Mp[arr[i]] = 1;
else
Mp.Add(arr[i],1);
}
// Iterate over all possible values of GCD
for(int i = 1; i <= M; i++)
{
// Variable to check current GCD
int currGcd = 0;
// Iterate over all multiples of i
for(int j = i; j <= M; j += i)
{
// If j is present in A
if (Mp.ContainsKey(j))
{
// Calculate gcd of all encountered
// multiples of i
currGcd = gcd(currGcd, j);
// Current GCD is possible
if (currGcd == i)
{
ans++;
break;
}
}
}
}
// Return answer
return ans;
}
// Driver code
public static void Main()
{
// Input
int []arr = { 3, 11, 14, 6, 12 };
int N = arr.Length;
// Function calling
Console.Write(distinctGCDs(arr, N));
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate gcd
function gcd(a, b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to calculate the number
// of distinct GCDs among all
// non-empty subsequences of an array
function distinctGCDs(arr, N)
{
// variables to store the largest element
// in array and the required count
let M = -1, ans = 0;
// Map to store whether
// a number is present in A
var Mp = new Map();
// calculate largest number
// in A and mapping A to Mp
for (let i = 0; i < N; i++) {
M = Math.max(M, arr[i]);
Mp.set(arr[i], 1);
}
// iterate over all possible values of GCD
for (let i = 1; i <= M; i++) {
// variable to check current GCD
let currGcd = 0;
// iterate over all multiples of i
for (let j = i; j <= M; j += i) {
// If j is present in A
if (Mp.has(j)) {
// calculate gcd of all encountered
// multiples of i
currGcd = gcd(currGcd, j);
// current GCD is possible
if (currGcd == i) {
ans++;
break;
}
}
}
}
// return answer
return ans;
}
// Driver code
// Input
let arr = [3, 11, 14, 6, 12];
let N = arr.length;
// Function calling
document.write(distinctGCDs(arr, N) + '<br>');
// This code is contributed by Potta Lokesh
</script>
Producción
7
Complejidad de tiempo: O(M*log(M)), donde M es el elemento más grande de la array
Espacio auxiliar: O(M)