Dado un entero K , la tarea es construir una array de longitud máxima con el producto de todos los elementos de la array igual a K , de modo que cada elemento de la array, excepto el primero, sea divisible por su elemento adyacente anterior.
Nota: Cada elemento de array en la array generada debe ser mayor que 1.
Ejemplos:
Entrada : K = 4
Salida : {2, 2}
Explicación :
El segundo elemento, es decir, arr[1] (= 2) es divisible por el primer elemento, es decir, arr[0] (= 2).
Producto de los elementos del arreglo = 2 * 2 = 4(= K).
Por lo tanto, la array cumple la condición requerida.Entrada : K = 23
Salida : {23}
Planteamiento: La idea para resolver este problema es encontrar todos los factores primos de K con sus respectivas potencias tales que:
factor_principal[1] x * factor_principal[2] y … * factor_principal[i] z = K
Siga los pasos a continuación para resolver este problema:
- Encuentre el factor primo, digamos X, con el mayor poder, digamos Y.
- Entonces, Y será la longitud de la array requerida.
- Por lo tanto, construya una array de longitud Y con todos los elementos iguales a X.
- Para hacer que el producto de la array sea igual a K , multiplique el último elemento por K/X y .
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 construct longest array
// with product K such that each element
// is divisible by its previous element
void findLongestArray(int K)
{
// Stores the prime factors of K
vector<pair<int, int> > primefactors;
int K_temp = K;
for (int i = 2; i * i <= K; i++) {
// Stores the power to which
// primefactor i is raised
int count = 0;
while (K_temp % i == 0) {
K_temp /= i;
count++;
}
if (count > 0)
primefactors.push_back({ count, i });
}
if (K_temp != 1)
primefactors.push_back(
{ 1, K_temp });
// Sort prime factors in descending order
sort(primefactors.rbegin(),
primefactors.rend());
// Stores the final array
vector<int> answer(
primefactors[0].first,
primefactors[0].second);
// Multiply the last element by K
answer.back() *= K;
for (int i = 0;
i < primefactors[0].first; i++) {
answer.back() /= primefactors[0].second;
}
// Print the constructed array
cout << "{";
for (int i = 0; i < (int)answer.size(); i++) {
if (i == answer.size() - 1)
cout << answer[i] << "}";
else
cout << answer[i] << ", ";
}
}
// Driver Code
int main()
{
int K = 4;
findLongestArray(K);
}
Java
// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to construct longest array
// with product K such that each element
// is divisible by its previous element
static void findLongestArray(int K)
{
// Stores the prime factors of K
ArrayList<int[]> primefactors = new ArrayList<>();
int K_temp = K;
for (int i = 2; i * i <= K; i++) {
// Stores the power to which
// primefactor i is raised
int count = 0;
while (K_temp % i == 0) {
K_temp /= i;
count++;
}
if (count > 0)
primefactors.add(new int[] { count, i });
}
if (K_temp != 1)
primefactors.add(new int[] { 1, K_temp });
// Sort prime factors in descending order
Collections.sort(primefactors, (x, y) -> {
if (x[0] != y[0])
return y[0] - x[0];
return y[1] - x[1];
});
// Stores the final array
int n = primefactors.get(0)[0];
int val = primefactors.get(0)[1];
int answer[] = new int[n];
Arrays.fill(answer, val);
// Multiply the last element by K
answer[n - 1] *= K;
for (int i = 0; i < n; i++) {
answer[n - 1] /= val;
}
// Print the constructed array
System.out.print("{");
for (int i = 0; i < answer.length; i++) {
if (i == answer.length - 1)
System.out.print(answer[i] + "}");
else
System.out.print(answer[i] + ", ");
}
}
// Driver Code
public static void main(String[] args)
{
int K = 4;
findLongestArray(K);
}
}
// This code is contributed by Kingash.
Python3
# Python 3 program for the above approach
# Function to construct longest array
# with product K such that each element
# is divisible by its previous element
def findLongestArray(K):
# Stores the prime factors of K
primefactors = []
K_temp = K
i = 2
while i * i <= K:
# Stores the power to which
# primefactor i is raised
count = 0
while (K_temp % i == 0):
K_temp //= i
count += 1
if (count > 0):
primefactors.append([count, i])
i += 1
if (K_temp != 1):
primefactors.append(
[1, K_temp])
# Sort prime factors in descending order
primefactors.sort()
# Stores the final array
answer = [primefactors[0][0],
primefactors[0][1]]
# Multiply the last element by K
answer[-1] *= K
for i in range(primefactors[0][0]):
answer[-1] //= primefactors[0][1]
# Print the constructed array
print("{", end = "")
for i in range(len(answer)):
if (i == len(answer) - 1):
print(answer[i], end = "}")
else:
print(answer[i], end = ", ")
# Driver Code
if __name__ == "__main__":
K = 4
findLongestArray(K)
# This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Function to construct longest array
// with product K such that each element
// is divisible by its previous element
function findLongestArray(K)
{
// Stores the prime factors of K
let primefactors = [];
let K_temp = K;
for (let i = 2; i * i <= K; i++) {
// Stores the power to which
// primefactor i is raised
let count = 0;
while (K_temp % i == 0) {
K_temp = Math.floor(K_temp/i);
count++;
}
if (count > 0)
primefactors.push([ count, i ]);
}
if (K_temp != 1)
primefactors.push([ 1, K_temp ]);
// Sort prime factors in descending order
primefactors.sort(function(x, y) {
if (x[0] != y[0])
return y[0] - x[0];
return y[1] - x[1];
});
// Stores the final array
let n = primefactors[0][0];
let val = primefactors[0][1];
let answer = new Array(n);
for(let i=0;i<n;i++)
{
answer[i]=val;
}
// Multiply the last element by K
answer[n - 1] *= K;
for (let i = 0; i < n; i++) {
answer[n - 1] = Math.floor(answer[n - 1]/val);
}
// Print the constructed array
document.write("{");
for (let i = 0; i < answer.length; i++) {
if (i == answer.length - 1)
document.write(answer[i] + "}");
else
document.write(answer[i] + ", ");
}
}
// Driver Code
let K = 4;
findLongestArray(K);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
{2, 2}
Complejidad de tiempo: O(√(K) * log(√(K)))
Espacio auxiliar: O(√(K))