Dada una array arr[] , la tarea es encontrar el número de sub-arrays con un valor GCD igual a 1 .
Ejemplos:
Entrada: arr[] = {1, 1, 1}
Salida: 6
Todos los subarreglos de la array dada
tendrán GCD igual a 1.
Entrada: arr[] = {2, 2, 2}
Salida: 0
Enfoque: La observación clave es que si se conoce el GCD de todos los elementos del subconjunto arr[l…r ] , entonces se puede obtener el GCD de todos los elementos del subconjunto arr[l…r+1]. simplemente tomando el GCD del subarreglo anterior con arr[r + 1] .
Por lo tanto, para cada índice i , siga iterando hacia adelante y calcule el GCD del índice i al j y verifique si es igual a 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the required count int cntSubArr(int* arr, int n) { // To store the final answer int ans = 0; for (int i = 0; i < n; i++) { // To store the GCD starting from // index 'i' int curr_gcd = 0; // Loop to find the gcd of each subarray // from arr[i] to arr[i...n-1] for (int j = i; j < n; j++) { curr_gcd = __gcd(curr_gcd, arr[j]); // Increment the count if curr_gcd = 1 ans += (curr_gcd == 1); } } // Return the final answer return ans; } // Driver code int main() { int arr[] = { 1, 1, 1 }; int n = sizeof(arr) / sizeof(int); cout << cntSubArr(arr, n); return 0; }
Java
// Java implementation of the approach class GFG { // Function to return the required count static int cntSubArr(int []arr, int n) { // To store the final answer int ans = 0; for (int i = 0; i < n; i++) { // To store the GCD starting from // index 'i' int curr_gcd = 0; // Loop to find the gcd of each subarray // from arr[i] to arr[i...n-1] for (int j = i; j < n; j++) { curr_gcd = __gcd(curr_gcd, arr[j]); // Increment the count if curr_gcd = 1 ans += (curr_gcd == 1) ? 1 : 0; } } // Return the final answer return ans; } static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); } // Driver code public static void main(String []args) { int arr[] = { 1, 1, 1 }; int n = arr.length; System.out.println(cntSubArr(arr, n)); } } // This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach from math import gcd # Function to return the required count def cntSubArr(arr, n) : # To store the final answer ans = 0; for i in range(n) : # To store the GCD starting from # index 'i' curr_gcd = 0; # Loop to find the gcd of each subarray # from arr[i] to arr[i...n-1] for j in range(i, n) : curr_gcd = gcd(curr_gcd, arr[j]); # Increment the count if curr_gcd = 1 ans += (curr_gcd == 1); # Return the final answer return ans; # Driver code if __name__ == "__main__" : arr = [ 1, 1, 1 ]; n = len(arr); print(cntSubArr(arr, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach using System; class GFG { // Function to return the required count static int cntSubArr(int []arr, int n) { // To store the final answer int ans = 0; for (int i = 0; i < n; i++) { // To store the GCD starting from // index 'i' int curr_gcd = 0; // Loop to find the gcd of each subarray // from arr[i] to arr[i...n-1] for (int j = i; j < n; j++) { curr_gcd = __gcd(curr_gcd, arr[j]); // Increment the count if curr_gcd = 1 ans += (curr_gcd == 1) ? 1 : 0; } } // Return the final answer return ans; } static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); } // Driver code public static void Main(String []args) { int []arr = { 1, 1, 1 }; int n = arr.Length; Console.WriteLine(cntSubArr(arr, n)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript implementation of the approach function __gcd(a, b) { if (b == 0) return a; return __gcd(b, a % b); } // Function to return the required count function cntSubArr(arr, n) { // To store the final answer var ans = 0; for (var i = 0; i < n; i++) { // To store the GCD starting from // index 'i' var curr_gcd = 0; // Loop to find the gcd of each subarray // from arr[i] to arr[i...n-1] for (var j = i; j < n; j++) { curr_gcd = __gcd(curr_gcd, arr[j]); // Increment the count if curr_gcd = 1 ans += (curr_gcd == 1); } } // Return the final answer return ans; } // Driver code var arr = [1, 1, 1]; var n = arr.length; document.write( cntSubArr(arr, n)); </script>
6
Complejidad de tiempo: O(N 2 log(max(arr[])))
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA