Dada una array arr [] de tamaño N y un entero K , la tarea es encontrar las operaciones mínimas tales que ninguna variable sea divisible por K. En cada operación:
- Seleccione cualquier entero X de la array.
- Divide todas las apariciones de X por K .
Ejemplos:
Entrada : arr[] = [2, 3, 4, 5], K = 2
Salida : 2
Explicación :
En la primera operación, elija X = 4; Por lo tanto, la array resultante será [2, 3, 2 , 5].
En la segunda operación, elija X = 2; Por lo tanto, la array resultante será [ 1 , 3, 1 , 5].
Después de estas dos operaciones, no quedó X tal que X % K = 0; por lo tanto, la respuesta es 2.Entrada : arr[] = [3, 5, 8, 12, 4], K = 4
Salida : 3
Explicación :
Primera operación X = 12, arr[] = [3, 5, 8, 3 , 4].
Segunda operación X = 8, arr[] = [3, 5, 2 , 3, 4].
Tercera operación X = 4, arr[] = [3, 5, 2, 3, 1 ].
Enfoque : este problema se puede resolver con la ayuda del enfoque codicioso basado en la siguiente idea.
Seleccione cualquier elemento y divídalo repetidamente por K hasta que ya no sea divisible. Haga lo mismo para todos los elementos de la array y encuentre el recuento total
Siga los pasos que se mencionan a continuación para resolver el problema:
- Inicializar un conjunto vacío para almacenar todos los diferentes elementos obtenidos al realizar las operaciones.
- Recorra todos los elementos de la array arr[] .
- Ejecute un ciclo while hasta que el arr[i] actual sea divisible por K .
- Si arr[i] no está presente en el conjunto, insértelo.
- Divide arr[i] por ‘K’.
- Ejecute un ciclo while hasta que el arr[i] actual sea divisible por K .
- Devuelve el tamaño del conjunto, ya que representa el número de veces que se realiza la operación de división.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find
// the minimum number of steps required
int minimumOps(int n, int k, vector<int>& arr)
{
// Initializing an empty set 'elements'.
set<int> elements;
// Looping over the array 'arr'.
for (int i = 0; i < n; i++) {
// While loop till current
// element is divisible by
// 'k'.
while (arr[i] % k == 0) {
// If current array element is
// not in the set then insert it.
if (elements.find(arr[i])
== elements.end()) {
elements.insert(arr[i]);
}
// Dividing the current
// array element by 'k'.
arr[i] /= k;
}
}
// Returning the answer:
// size of the set 'elements'.
return (int)elements.size();
}
// Driver code
int main()
{
int N = 5, K = 4;
vector<int> arr = { 3, 5, 8, 12, 4 };
// Function call
cout << minimumOps(n, k, arr);
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
class GFG {
// Function to find
// the minimum number of steps required
static int minimumOps(int n, int k, int arr[])
{
// Initializing an empty set 'elements'.
HashSet<Integer> elements=new HashSet<Integer>();
// Looping over the array 'arr'.
for (int i = 0; i < n; i++) {
// While loop till current
// element is divisible by
// 'k'.
while (arr[i] % k == 0) {
// If current array element is
// not in the set then insert it.
if (!elements.contains(arr[i])) {
elements.add(arr[i]);
}
// Dividing the current
// array element by 'k'.
arr[i] /= k;
}
}
// Returning the answer:
// size of the set 'elements'.
return elements.size();
}
// Driver code
public static void main (String[] args) {
int N = 5, K = 4;
int arr[] = { 3, 5, 8, 12, 4 };
// Function call
System.out.print(minimumOps(N, K, arr));
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python3 code to implement the approach # Function to find the minimum number of steps required def minimumOps(n, k, arr): # Initializing an empty set 'elements'. elements = set() # Looping over the array 'arr'. for i in range(n): # While loop till current # element is divisible by # 'k'. while (arr[i] % k == 0): # If current array element is # not in the set then insert it. if arr[i] not in elements: elements.add(arr[i]) # Dividing the current # array element by 'k'. arr[i] //= k # Returning the answer: # size of the set 'elements'. return len(elements) # Driver Code N, K = 5, 4 arr = [3, 5, 8, 12, 4] # Function Call print(minimumOps(N, K, arr)) # This code is contributed by phasing17
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find
// the minimum number of steps required
static int minimumOps(int n, int k, int[] arr)
{
// Initializing an empty set 'elements'.
HashSet<int> elements = new HashSet<int>();
// Looping over the array 'arr'.
for (int i = 0; i < n; i++)
{
// While loop till current
// element is divisible by
// 'k'.
while (arr[i] % k == 0)
{
// If current array element is
// not in the set then insert it.
if (!(elements.Contains(arr[i]))) {
elements.Add(arr[i]);
}
// Dividing the current
// array element by 'k'.
arr[i] /= k;
}
}
// Returning the answer:
// size of the set 'elements'.
return elements.Count;
}
public static void Main(string[] args)
{
int N = 5, K = 4;
int[] arr = { 3, 5, 8, 12, 4 };
// Function call
Console.Write(minimumOps(N, K, arr));
}
}
// This code is contributed by phasing17.
Javascript
<script>
// JavaScript code to implement the approach
// Function to find
// the minimum number of steps required
const minimumOps = (n, k, arr) => {
// Initializing an empty set 'elements'.
let elements = new Set();
// Looping over the array 'arr'.
for (let i = 0; i < n; i++)
{
// While loop till current
// element is divisible by
// 'k'.
while (arr[i] % k == 0)
{
// If current array element is
// not in the set then insert it.
if (!elements.has(arr[i]))
{
elements.add(arr[i]);
}
// Dividing the current
// array element by 'k'.
arr[i] = parseInt(arr[i] / k);
}
}
// Returning the answer:
// size of the set 'elements'.
return elements.size;
}
// Driver code
let n = 5, k = 4;
let arr = [3, 5, 8, 12, 4];
// Function call
document.write(minimumOps(n, k, arr));
// This code is contributed by rakeshsahni
</script>
3
Complejidad temporal: O(N * LogM), donde M es el elemento máximo del arreglo.
Espacio Auxiliar : O(N)