Dados dos enteros positivos N y K , la tarea es generar un arreglo de longitud N tal que el producto de cada subarreglo de longitud mayor que 1 debe ser divisible por K y el elemento máximo del arreglo debe ser menor que K . Si tal array no es posible, imprima -1 .
Ejemplos:
Entrada: N = 3, K = 20
Salida: {15, 12, 5}
Explicación: Todos los subarreglos de longitud mayor que 1 son {15, 12}, {12, 5}, {15, 12, 5} y sus correspondientes los productos son 180, 60 y 900, todos divisibles por 20.Entrada: N = 4, K = 100
Salida: {90, 90, 90, 90}
Enfoque: El problema dado se puede resolver mediante las siguientes observaciones:
Se puede observar que al hacer el producto de cada subarreglo de longitud 2 divisible por K , el producto de cada subarreglo de longitud mayor que 2 será automáticamente divisible por K .
Por lo tanto, la idea es tomar dos divisores de K , digamos d1 y d2 , tales que d1 * d2 = K y colocarlos alternativamente en la array. Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables enteras d1 y d2 .
- Compruebe si K es primo . Si se encuentra que es cierto, imprima -1 .
- De lo contrario, calcule los divisores de K y almacene dos divisores en d1 y d2 .
- Después de eso, atraviesa de i = 0 a N – 1 .
- Imprime d1 si i es par. De lo contrario, imprima d2 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to check if the required
// array can be generated or not
void array_divisbleby_k(int N, int K)
{
// To check if divisor exists
bool flag = false;
// To store divisors of K
int d1, d2;
// Check if K is prime or not
for (int i = 2; i * i <= K; i++) {
if (K % i == 0) {
flag = true;
d1 = i;
d2 = K / i;
break;
}
}
// If array can be generated
if (flag) {
// Print d1 and d2 alternatively
for (int i = 0; i < N; i++) {
if (i % 2 == 1) {
cout << d2 << " ";
}
else {
cout << d1 << " ";
}
}
}
else {
// No such array can be generated
cout << -1;
}
}
// Driver Code
int main()
{
// Given N and K
int N = 5, K = 21;
// Function Call
array_divisbleby_k(N, K);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to check if the required
// array can be generated or not
public static void array_divisbleby_k(int N,
int K)
{
// To check if divisor exists
boolean flag = false;
// To store divisors of K
int d1 = 0, d2 = 0;
// Check if K is prime or not
for(int i = 2; i * i <= K; i++)
{
if (K % i == 0)
{
flag = true;
d1 = i;
d2 = K / i;
break;
}
}
// If array can be generated
if (flag)
{
// Print d1 and d2 alternatively
for(int i = 0; i < N; i++)
{
if (i % 2 == 1)
{
System.out.print(d2 + " ");
}
else
{
System.out.print(d1 + " ");
}
}
}
else
{
// No such array can be generated
System.out.print(-1);
}
}
// Driver Code
public static void main(String[] args)
{
// Given N and K
int N = 5, K = 21;
// Function Call
array_divisbleby_k(N, K);
}
}
// This code is contributed by divyesh072019
Python3
# Python3 program for the above approach # Function to check if the required # array can be generated or not def array_divisbleby_k(N, K): # To check if divisor exists flag = False # To store divisors of K d1, d2 = 0, 0 # Check if K is prime or not for i in range(2, int(K ** (1 / 2)) + 1): if (K % i == 0): flag = True d1 = i d2 = K // i break # If array can be generated if (flag): # Print d1 and d2 alternatively for i in range(N): if (i % 2 == 1): print(d2, end = " ") else: print(d1, end = " ") else: # No such array can be generated print(-1) # Driver Code if __name__ == "__main__": # Given N and K N = 5 K = 21 # Function Call array_divisbleby_k(N, K) # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if the required
// array can be generated or not
public static void array_divisbleby_k(int N,
int K)
{
// To check if divisor exists
bool flag = false;
// To store divisors of K
int d1 = 0, d2 = 0;
// Check if K is prime or not
for(int i = 2; i * i <= K; i++)
{
if (K % i == 0)
{
flag = true;
d1 = i;
d2 = K / i;
break;
}
}
// If array can be generated
if (flag)
{
// Print d1 and d2 alternatively
for(int i = 0; i < N; i++)
{
if (i % 2 == 1)
{
Console.Write(d2 + " ");
}
else
{
Console.Write(d1 + " ");
}
}
}
else
{
// No such array can be generated
Console.Write(-1);
}
}
// Driver Code
public static void Main(string[] args)
{
// Given N and K
int N = 5, K = 21;
// Function Call
array_divisbleby_k(N, K);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program for the above approach
// Function to check if the required
// array can be generated or not
function array_divisbleby_k(N, K)
{
// To check if divisor exists
let flag = false;
// To store divisors of K
let d1 = 0, d2 = 0;
// Check if K is prime or not
for(let i = 2; i * i <= K; i++)
{
if (K % i == 0)
{
flag = true;
d1 = i;
d2 = K / i;
break;
}
}
// If array can be generated
if (flag)
{
// Print d1 and d2 alternatively
for(let i = 0; i < N; i++)
{
if (i % 2 == 1)
{
document.write(d2 + " ");
}
else
{
document.write(d1 + " ");
}
}
}
else
{
// No such array can be generated
document.write(-1);
}
}
// Given N and K
let N = 5, K = 21;
// Function Call
array_divisbleby_k(N, K);
// This code is contributed by suresh07.
</script>
Producción:
3 7 3 7 3
Complejidad temporal: O(N + √K)
Espacio auxiliar: O(1)