Dada una array de enteros arr[] , la tarea es contar el número de particiones posibles de modo que en cada partición el elemento mínimo divida todos los demás elementos de la partición. La partición no necesita ser continua.
Ejemplos:
Entrada: arr[] = {10, 7, 20, 21, 13}
Salida: 3
Las posibles particiones son {10, 20}, {7, 21} y {13}.
En cada partición, todos los elementos son divisibles por
el elemento mínimo de la partición.
Entrada: arr[] = {7, 6, 5, 4, 3, 2, 2, 3}
Salida: 4
Acercarse:
- Encuentre el elemento mínimo en la array que no es igual a INT_MAX .
- Eliminar todos los elementos (reemplazar por INT_MAX ) de la array divisible por el elemento mínimo.
- El número de elementos mínimos válidos como resultado de las operaciones es el número requerido de particiones.
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 count partitions
// possible from the given array such that
// the minimum element of any partition
// divides all the other elements
// of that partition
int countPartitions(int A[], int N)
{
// Initialize the count variable
int count = 0;
for (int i = 0; i < N; i++) {
// Find the minimum element
int min_elem = *min_element(A, A + N);
// Break if no minimum element present
if (min_elem == INT_MAX)
break;
// Increment the count if
// minimum element present
count++;
// Replace all the element
// divisible by min_elem
for (int i = 0; i < N; i++) {
if (A[i] % min_elem == 0)
A[i] = INT_MAX;
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 7, 6, 5, 4, 3, 2, 2, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << countPartitions(arr, N);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int INT_MAX = Integer.MAX_VALUE ;
static int min_element(int []A, int N)
{
int min = A[0];
int i;
for( i = 1; i < N ; i++)
{
if (min > A[i])
{
min = A[i];
}
}
return min;
}
// Function to return the count partitions
// possible from the given array such that
// the minimum element of any partition
// divides all the other elements
// of that partition
static int countPartitions(int []A, int N)
{
// Initialize the count variable
int count = 0;
int i, j;
for (i = 0; i < N; i++)
{
// Find the minimum element
int min_elem = min_element(A, N);
// Break if no minimum element present
if (min_elem == INT_MAX)
break;
// Increment the count if
// minimum element present
count++;
// Replace all the element
// divisible by min_elem
for (j = 0; j < N; j++)
{
if (A[j] % min_elem == 0)
A[j] = INT_MAX;
}
}
return count;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 7, 6, 5, 4, 3, 2, 2, 3 };
int N = arr.length;
System.out.println(countPartitions(arr, N));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach import sys INT_MAX = sys.maxsize; # Function to return the count partitions # possible from the given array such that # the minimum element of any partition # divides all the other elements # of that partition def countPartitions(A, N) : # Initialize the count variable count = 0; for i in range(N) : # Find the minimum element min_elem = min(A); # Break if no minimum element present if (min_elem == INT_MAX) : break; # Increment the count if # minimum element present count += 1; # Replace all the element # divisible by min_elem for i in range(N) : if (A[i] % min_elem == 0) : A[i] = INT_MAX; return count; # Driver code if __name__ == "__main__" : arr = [ 7, 6, 5, 4, 3, 2, 2, 3 ]; N = len(arr); print(countPartitions(arr, N)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int INT_MAX = int.MaxValue ;
static int min_element(int []A, int N)
{
int min = A[0];
int i;
for( i = 1; i < N ; i++)
{
if (min > A[i])
{
min = A[i];
}
}
return min;
}
// Function to return the count partitions
// possible from the given array such that
// the minimum element of any partition
// divides all the other elements
// of that partition
static int countPartitions(int []A, int N)
{
// Initialize the count variable
int count = 0;
int i, j;
for (i = 0; i < N; i++)
{
// Find the minimum element
int min_elem = min_element(A, N);
// Break if no minimum element present
if (min_elem == INT_MAX)
break;
// Increment the count if
// minimum element present
count++;
// Replace all the element
// divisible by min_elem
for (j = 0; j < N; j++)
{
if (A[j] % min_elem == 0)
A[j] = INT_MAX;
}
}
return count;
}
// Driver code
public static void Main()
{
int []arr = { 7, 6, 5, 4, 3, 2, 2, 3 };
int N = arr.Length;
Console.WriteLine(countPartitions(arr, N));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
var INT_MAX = 1000000000;
function min_element(A, N)
{
var min = A[0];
var i;
for( i = 1; i < N ; i++)
{
if (min > A[i])
{
min = A[i];
}
}
return min;
}
// Function to return the count partitions
// possible from the given array such that
// the minimum element of any partition
// divides all the other elements
// of that partition
function countPartitions(A, N)
{
// Initialize the count variable
var count = 0;
var i, j;
for (i = 0; i < N; i++)
{
// Find the minimum element
var min_elem = min_element(A, N);
// Break if no minimum element present
if (min_elem == INT_MAX)
break;
// Increment the count if
// minimum element present
count++;
// Replace all the element
// divisible by min_elem
for (j = 0; j < N; j++)
{
if (A[j] % min_elem == 0)
A[j] = INT_MAX;
}
}
return count;
}
// Driver code
var arr = [ 7, 6, 5, 4, 3, 2, 2, 3 ];
var N = arr.length;
document.write(countPartitions(arr, N));
// This code is contributed by rutvik_56.
</script>
Producción:
4
Complejidad temporal: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA