Dados dos números naturales A y B (B >= A) y un número entero N , su tarea es generar una array de números naturales en orden no decreciente, de modo que tanto A como B deben ser parte de la array y la diferencia entre cada par de elementos adyacentes es el mismo manteniendo el elemento máximo de la array lo más mínimo posible.
Ejemplo:
Entrada: A = 10, B = 20, N = 4
Salida: 5 10 15 20
Explicación: La array {5, 10, 15, 20} contiene solo números naturales y tanto A=10 como B=20 están incluidos en la array . La diferencia entre cada par adyacente es 5 y el elemento máximo es 20, que no se puede reducir más.Entrada: A = 12, B = 33, N = 2
Salida: 12 33Entrada: A = 7, B = 17, N = 5
Salida: 2 7 12 17 22
Enfoque: La array requerida forma una serie AP . Dado que A y B deben estar incluidos en el AP, la diferencia común d entre términos adyacentes debe ser un divisor de (B – A). Para minimizar el término más grande, el enfoque óptimo es generar la array con la diferencia común más pequeña posible que satisfaga las condiciones dadas. El problema se puede resolver siguiendo los pasos a continuación:
- Iterar sobre todos los valores de d de 1 a BA .
- Si d es un factor de BA y el número de elementos de A a B con diferencia común d no es mayor que N , continúe. De lo contrario, muévase al siguiente valor de d .
- Hay dos casos posibles
- Caso 1 : el número de elementos menores o iguales a B que tienen una diferencia común d es mayor que N. En este caso, el primer elemento de la array será B – (d*(N-1)) .
- Caso 2 : el número de elementos menores o iguales a B que tienen una diferencia común d es menor que N. En este caso, el primer elemento de la array será B – d*( B-1 )/d (es decir, 1).
- Imprime la array usando el primer elemento y la diferencia común.
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 print the array of N
// natural numbers in increasing order
// with equal difference of adjacent
// elements and containing A and B
void generateAP(int A, int B, int N)
{
// maximum possible difference
int d = B - A;
int cd, f;
// Iterating over all values of d
for (int i = 1; i <= d; i++) {
// Check if i is a factor of d
// and number of elements from
// a to b with common difference
// d are not more than N
if (d % i == 0 && (d / i) + 1 <= N) {
// Number off natural numbers
// less than B and having
// difference as i
int cnt = min((B - 1) / i, N - 1);
// Calculate the 1st element of
// the required array
f = B - (cnt * i);
cd = i;
break;
}
}
// Print the resulting array
for (int i = 0; i < N; i++) {
cout << (f + i * cd) << " ";
}
}
// Driver code
int main()
{
int A = 10, B = 20, N = 4;
// Function call
generateAP(A, B, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
public static int min(int a ,int b){
if(a < b){
return a;
}
return b;
}
public static void generateAP(int A, int B, int N)
{
// maximum possible difference
int d = B - A;
int cd = 0, f= 0;
// Iterating over all values of d
for (int i = 1; i <= d; i++) {
// Check if i is a factor of d
// and number of elements from
// a to b with common difference
// d are not more than N
if (d % i == 0 && (d / i) + 1 <= N) {
// Number off natural numbers
// less than B and having
// difference as i
int cnt = min((B - 1) / i, N - 1);
// Calculate the 1st element of
// the required array
f = B - (cnt * i);
cd = i;
break;
}
}
// Print the resulting array
for (int i = 0; i < N; i++) {
System.out.print((f + i * cd) + " ");
}
}
// Driver code
public static void main(String[] args)
{
int A = 10, B = 20, N = 4;
// Function call
generateAP(A, B, N);
}
}
// This code is contributed by maddler.
Python3
# Python program for the above approach # Function to print array of N # natural numbers in increasing order # with equal difference of adjacent # elements and containing A and B def generateAP(A, B, N): # maximum possible difference d = B - A # Iterating over all values of d for i in range(1,d+1): # Check if i is a factor of d # and number of elements from # a to b with common difference # d are not more than N if (d % i == 0 and (d // i) + 1 <= N): # Number off natural numbers # less than B and having # difference as i cnt = min((B - 1) // i, N - 1) # Calculate the 1st element of # the required array f = B - (cnt * i) cd = i break # Print resulting array for i in range(N): print(f + i * cd , end=" ") # Driver code A = 10 B = 20 N = 4 # Function call generateAP(A, B, N) # This code is contributed by shivanisinghss2110
C#
// C# program for the above approach
using System;
class GFG{
public static int min(int a ,int b){
if(a < b){
return a;
}
return b;
}
public static void generateAP(int A, int B, int N)
{
// maximum possible difference
int d = B - A;
int cd = 0, f= 0;
// Iterating over all values of d
for (int i = 1; i <= d; i++) {
// Check if i is a factor of d
// and number of elements from
// a to b with common difference
// d are not more than N
if (d % i == 0 && (d / i) + 1 <= N) {
// Number off natural numbers
// less than B and having
// difference as i
int cnt = min((B - 1) / i, N - 1);
// Calculate the 1st element of
// the required array
f = B - (cnt * i);
cd = i;
break;
}
}
// Print the resulting array
for (int i = 0; i < N; i++) {
Console.Write((f + i * cd) + " ");
}
}
// Driver Code
public static void Main()
{
int A = 10, B = 20, N = 4;
// Function call
generateAP(A, B, N);
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// Javascript program for the above approach
function min(a, b)
{
if (a < b)
{
return a;
}
return b;
}
// Function to print the array of N
// natural numbers in increasing order
// with equal difference of adjacent
// elements and containing A and B
function generateAP(A, B, N)
{
// Maximum possible difference
var d = B - A;
var cd = 0, f = 0;
// Iterating over all values of d
for(var i = 1; i <= d; i++)
{
// Check if i is a factor of d
// and number of elements from
// a to b with common difference
// d are not more than N
if (d % i == 0 && (d / i) + 1 <= N)
{
// Number off natural numbers
// less than B and having
// difference as i
var cnt = min((B - 1) / i, N - 1);
// Calculate the 1st element of
// the required array
f = B - (cnt * i);
cd = i;
break;
}
}
// Print the resulting array
for(var i = 0; i < N; i++)
{
document.write((f + i * cd) + " ");
}
}
// Driver code
var A = 10, B = 20, N = 4;
// Function call
generateAP(A, B, N);
// This code is contributed by shivanisinghss2110
</script>
5 10 15 20
Complejidad temporal: O(N + √B)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por parthmanchanda81 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA