Dada una array arr[] de tamaño N y un entero M , la tarea es contar el número de subarreglos que tienen el producto de sus elementos igual a la potencia de M , donde M es un número primo .
Ejemplos:
Entrada: arr[] = {2, 2, 2, 2}, M = 2
Salida: 10
Explicación: Todos los posibles subarreglos no vacíos que tienen un producto igual a la potencia de M = (4 * (4 + 1)) / 2 = 10Entrada: arr[] = {1, 1, 1, 3}, M = 3
Salida: 10
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos posibles del arreglo arr[] y, para cada subarreglo, verificar si su producto es una potencia de M o no. Si es cierto, entonces incremente el conteo de dichos subarreglos en 1. Finalmente, imprima el conteo obtenido.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea óptima se basa en el hecho de que para que el producto de cualquier subarreglo sea igual a la potencia de M , todos los elementos del subarreglo también deben ser una potencia de M , ya que M es un número primo . Siga los pasos a continuación para resolver el problema dado:
- Inicialice la variable, digamos ans , para almacenar el recuento de subarreglos requeridos
- Inicializa una variable, digamos cnt , para almacenar el conteo de números consecutivos que son una potencia de M .
- Recorra la array sobre el rango de índices [0, N – 1] usando una variable, digamos i , y realice las siguientes operaciones:
- Si arr[i] es una potencia de M . Incremente cnt en 1. Actualice ans = ans + (cnt * (cnt – 1)) / 2
- De lo contrario, actualice cnt = 0.
- Después de completar los pasos anteriores, imprima el valor de cnt .
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 check if y
// is a power of m or not
bool isPower(int m, int y)
{
// Calculate log y base m and store
// it in a variable with integer datatype
int res1 = log(y) / log(m);
// Calculate log y base m and store
// it in a variable with double datatype
double res2 = log(y) / log(m);
// If res1 and res2 are equal, return
// True. Otherwise, return false
return (res1 == res2);
}
// Function to count the number of subarrays
// having product of elements equal to a
// power of m, where m is a prime number
int numSub(int arr[], int n, int m)
{
// Stores the count of
// subarrays required
int ans = 0;
// Stores current sequence of
// consecutive array elements
// which are a multiple of m
int cnt = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// If arr[i] is a power of M
if (isPower(m, arr[i])) {
// Increment cnt
cnt++;
// Update ans
ans += (cnt * (cnt - 1)) / 2;
}
else {
// Update cnt
cnt = 0;
}
}
// Return the count
// of subarrays
return ans;
}
// Driver Code
int main()
{
// Input
int arr[] = { 1, 1, 1, 3 };
int m = 3;
int n = sizeof(arr) / sizeof(arr[0]);
cout << numSub(arr, n, m);
return 0;
}
Java
// Java code of above approach
import java.util.*;
class GFG
{
// Function to check if y
// is a power of m or not
static boolean isPower(int m, int y)
{
// Calculate log y base m and store
// it in a variable with integer datatype
int res1 = (int)Math.log(y) / (int)Math.log(m);
// Calculate log y base m and store
// it in a variable with double datatype
double res2 = (int)Math.log(y) / (int)Math.log(m);
// If res1 and res2 are equal, return
// True. Otherwise, return false
return (res1 == res2);
}
// Function to count the number of subarrays
// having product of elements equal to a
// power of m, where m is a prime number
static int numSub(int arr[], int n, int m)
{
// Stores the count of
// subarrays required
int ans = 0;
// Stores current sequence of
// consecutive array elements
// which are a multiple of m
int cnt = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// If arr[i] is a power of M
if (isPower(m, arr[i])) {
// Increment cnt
cnt++;
// Update ans
ans += (cnt * (cnt - 1)) / 2;
}
else {
// Update cnt
cnt = 0;
}
}
// Return the count
// of subarrays
return ans;
}
// Driver code
public static void main(String[] args)
{
// Input
int arr[] = { 1, 1, 1, 3 };
int m = 3;
int n = arr.length;
System.out.println(numSub(arr, n, m));
}
}
// This code is contributed by offbeat
Python3
# Python 3 program for the above approach from math import log # Function to check if y # is a power of m or not def isPower(m, y): # Calculate log y base m and store # it in a variable with integer datatype res1 = log(y) // log(m) # Calculate log y base m and store # it in a variable with double datatype res2 = log(y) // log(m) # If res1 and res2 are equal, return # True. Otherwise, return false return (res1 == res2) # Function to count the number of subarrays # having product of elements equal to a # power of m, where m is a prime number def numSub(arr, n, m): # Stores the count of # subarrays required ans = 0 # Stores current sequence of # consecutive array elements # which are a multiple of m cnt = 0 # Traverse the array for i in range(n): # If arr[i] is a power of M if (isPower(m, arr[i])): # Increment cnt cnt += 1 # Update ans ans += (cnt * (cnt - 1)) // 2 else: # Update cnt cnt = 0 # Return the count # of subarrays return ans # Driver Code if __name__ == '__main__': # Input arr = [1, 1, 1, 3] m = 3 n = len(arr) print(numSub(arr, n, m)) # This code is contributed by bgangwar59.
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if y
// is a power of m or not
static bool isPower(int m, int y)
{
// Calculate log y base m and store
// it in a variable with integer datatype
int res1 = (int)Math.Log(y) / (int)Math.Log(m);
// Calculate log y base m and store
// it in a variable with double datatype
double res2 = (int)Math.Log(y) / (int)Math.Log(m);
// If res1 and res2 are equal, return
// True. Otherwise, return false
return (res1 == res2);
}
// Function to count the number of subarrays
// having product of elements equal to a
// power of m, where m is a prime number
static int numSub(int[] arr, int n, int m)
{
// Stores the count of
// subarrays required
int ans = 0;
// Stores current sequence of
// consecutive array elements
// which are a multiple of m
int cnt = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
// If arr[i] is a power of M
if (isPower(m, arr[i]))
{
// Increment cnt
cnt++;
// Update ans
ans += (cnt * (cnt - 1)) / 2;
}
else
{
// Update cnt
cnt = 0;
}
}
// Return the count
// of subarrays
return ans;
}
// Driver code
public static void Main()
{
// Input
int[] arr = { 1, 1, 1, 3 };
int m = 3;
int n = arr.Length;
Console.Write(numSub(arr, n, m));
}
}
// This code is contributed by subhammahato348
Javascript
<script>
// Javascript program for the above approach
// Function to check if y
// is a power of m or not
function isPower(m, y)
{
// Calculate log y base m and store
// it in a variable with integer datatype
let res1 = parseInt(Math.log(y) / Math.log(m));
// Calculate log y base m and store
// it in a variable with double datatype
let res2 = Math.log(y) / Math.log(m);
// If res1 and res2 are equal, return
// True. Otherwise, return false
return (res1 == res2);
}
// Function to count the number of subarrays
// having product of elements equal to a
// power of m, where m is a prime number
function numSub(arr, n, m)
{
// Stores the count of
// subarrays required
let ans = 0;
// Stores current sequence of
// consecutive array elements
// which are a multiple of m
let cnt = 0;
// Traverse the array
for (let i = 0; i < n; i++) {
// If arr[i] is a power of M
if (isPower(m, arr[i])) {
// Increment cnt
cnt++;
// Update ans
ans += parseInt((cnt * (cnt - 1)) / 2);
}
else {
// Update cnt
cnt = 0;
}
}
// Return the count
// of subarrays
return ans;
}
// Driver Code
// Input
let arr = [ 1, 1, 1, 3 ];
let m = 3;
let n = arr.length;
document.write(numSub(arr, n, m));
// This code is contributed by subhammahato348.
</script>
Producción:
10
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por prakhar_kochar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA