Dados los tres enteros N , X e Y , la tarea es encontrar una serie de progresión aritmética de longitud N con el menor primer término posible que contenga X e Y .
Ejemplos:
Entrada: N = 5, X = 10, Y = 15
Salida: 5 10 15 20 25
Explicación:
El primer término mínimo posible del AP es 5. Diferencia común de AP = 5
El AP dado contiene 10 y 15.Entrada: N = 10, X = 5, Y = 15
Salida: 1 3 5 7 9 11 13 15 17 19
Enfoque ingenuo: el enfoque más simple es iterar todos los valores de posibles diferencias comunes de 1 a abs (XY) y verificar si existe un AP de longitud N con el primer término mayor que 0 y que contiene tanto X como Y.
Complejidad de tiempo: O(N * abs(XY))
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque se basa en la idea de que para incluir tanto a X como a Y en la serie, la diferencia común de AP debe ser un factor de abs(XY) . A continuación se muestran los pasos para resolver el problema:
- Iterar de 1 a sqrt(abs(XY)) y considerar solo aquellas diferencias comunes que son factores de abs(XY) .
- Para cada diferencia común posible, diga diff que divide a abs(XY) , encuentre el primer término mínimo mayor que 0 usando el algoritmo de búsqueda binaria .
- Almacene el primer término mínimo y la diferencia común correspondiente para imprimir la progresión aritmética de longitud N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the approach
#include <bits/stdc++.h>
using namespace std;
// Function that finds the minimum
// positive first term including X with given
// common difference and the number of terms
int minFirstTerm(int X, int diff, int N)
{
// Stores the first term
int first_term;
// Initialize the low and high
int low = 0, high = N;
// Perform binary search
while (low <= high) {
// Find the mid
int mid = (low + high) / 2;
// Check if first term is
// greater than 0
if (X - mid * diff > 0) {
// Store the possible first term
first_term = X - mid * diff;
// Search between mid + 1 to high
low = mid + 1;
}
else
// Search between low to mid-1
high = mid - 1;
}
// Return the minimum first term
return first_term;
}
// Function that finds the Arithmetic
// Progression with minimum possible
// first term containing X and Y
void printAP(int N, int X, int Y)
{
// Considering X to be
// smaller than Y always
if (X > Y)
swap(X, Y);
// Stores the max common difference
int maxDiff = Y - X;
// Stores the minimum first term
// and the corresponding common
// difference of the resultant AP
int first_term = INT_MAX, diff;
// Iterate over all the common difference
for (int i = 1; i * i <= maxDiff; i++) {
// Check if X and Y is included
// for current common difference
if (maxDiff % i == 0) {
// Store the possible
// common difference
int diff1 = i;
int diff2 = maxDiff / diff1;
// Number of terms from
// X to Y with diff1
// common difference
int terms1 = diff2 + 1;
// Number of terms from
// X to Y with diff2
// common difference
int terms2 = diff1 + 1;
// Find the corresponding first
// terms with diff1 and diff2
int first_term1
= minFirstTerm(X, diff1, N - terms1);
int first_term2
= minFirstTerm(X, diff2, N - terms2);
// Store the minimum first term
// and the corresponding
// common difference
if (first_term1 < first_term) {
first_term = first_term1;
diff = diff1;
}
if (first_term2 < first_term) {
first_term = first_term2;
diff = diff2;
}
}
}
// Print the resultant AP
for (int i = 0; i < N; i++) {
cout << first_term << " ";
first_term += diff;
}
}
// Driver Code
int main()
{
// Given length of AP
// and the two terms
int N = 5, X = 10, Y = 15;
// Function Call
printAP(N, X, Y);
return 0;
}
Java
// Java program for the approach
import java.util.*;
class GFG{
// Function that finds the minimum
// positive first term including X
// with given common difference and
// the number of terms
static int minFirstTerm(int X, int diff, int N)
{
// Stores the first term
int first_term = Integer.MAX_VALUE;
// Initialize the low and high
int low = 0, high = N;
// Perform binary search
while (low <= high)
{
// Find the mid
int mid = (low + high) / 2;
// Check if first term is
// greater than 0
if (X - mid * diff > 0)
{
// Store the possible first term
first_term = X - mid * diff;
// Search between mid + 1 to high
low = mid + 1;
}
else
// Search between low to mid-1
high = mid - 1;
}
// Return the minimum first term
return first_term;
}
// Function that finds the Arithmetic
// Progression with minimum possible
// first term containing X and Y
static void printAP(int N, int X, int Y)
{
// Considering X to be
// smaller than Y always
if (X > Y)
{
X = X + Y;
Y = X - Y;
X = X - Y;
}
// Stores the max common difference
int maxDiff = Y - X;
// Stores the minimum first term
// and the corresponding common
// difference of the resultant AP
int first_term = Integer.MAX_VALUE, diff = 0;
// Iterate over all the common difference
for(int i = 1; i * i <= maxDiff; i++)
{
// Check if X and Y is included
// for current common difference
if (maxDiff % i == 0)
{
// Store the possible
// common difference
int diff1 = i;
int diff2 = maxDiff / diff1;
// Number of terms from
// X to Y with diff1
// common difference
int terms1 = diff2 + 1;
// Number of terms from
// X to Y with diff2
// common difference
int terms2 = diff1 + 1;
// Find the corresponding first
// terms with diff1 and diff2
int first_term1 = minFirstTerm(X, diff1,
N - terms1);
int first_term2 = minFirstTerm(X, diff2,
N - terms2);
// Store the minimum first term
// and the corresponding
// common difference
if (first_term1 < first_term)
{
first_term = first_term1;
diff = diff1;
}
if (first_term2 < first_term)
{
first_term = first_term2;
diff = diff2;
}
}
}
// Print the resultant AP
for(int i = 0; i < N; i++)
{
System.out.print(first_term + " ");
first_term += diff;
}
}
// Driver Code
public static void main(String[] args)
{
// Given length of AP
// and the two terms
int N = 5, X = 10, Y = 15;
// Function call
printAP(N, X, Y);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the approach import sys # Function that finds the minimum # positive first term including X with given # common difference and the number of terms def minFirstTerm(X, diff, N): # Stores the first term first_term_1 = sys.maxsize # Initialize the low and high low = 0 high = N # Perform binary search while (low <= high): # Find the mid mid = (low + high) // 2 # Check if first term is # greater than 0 if (X - mid * diff > 0): # Store the possible first term first_term_1 = X - mid * diff # Search between mid + 1 to high low = mid + 1 else: # Search between low to mid-1 high = mid - 1 # Return the minimum first term return first_term_1 # Function that finds the Arithmetic # Progression with minimum possible # first term containing X and Y def printAP(N, X, Y): # Considering X to be # smaller than Y always if (X > Y): X = X + Y Y = X - Y X = X - Y # Stores the max common difference maxDiff = Y - X # Stores the minimum first term # and the corresponding common # difference of the resultant AP first_term = sys.maxsize diff = 0 # Iterate over all the common difference for i in range(1, maxDiff + 1): if i * i > maxDiff: break # Check if X and Y is included # for current common difference if (maxDiff % i == 0): # Store the possible # common difference diff1 = i diff2 = maxDiff // diff1 # Number of terms from # X to Y with diff1 # common difference terms1 = diff2 + 1 # Number of terms from # X to Y with diff2 # common difference terms2 = diff1 + 1 # Find the corresponding first # terms with diff1 and diff2 first_term1 = minFirstTerm(X, diff1, N - terms1) first_term2 = minFirstTerm(X, diff2, N - terms2) # Store the minimum first term # and the corresponding # common difference if (first_term1 < first_term): first_term = first_term1 diff = diff1 if (first_term2 < first_term): first_term = first_term2 diff = diff2 # Print the resultant AP for i in range(N): print(first_term, end = " ") first_term += diff # Driver Code if __name__ == '__main__': # Given length of AP # and the two terms N = 5 X = 10 Y = 15 # Function call printAP(N, X, Y) # This code is contributed by mohit kumar 29
C#
// C# program for the approach
using System;
class GFG{
// Function that finds the minimum
// positive first term including X
// with given common difference and
// the number of terms
static int minFirstTerm(int X, int diff,
int N)
{
// Stores the first term
int first_term = int.MaxValue;
// Initialize the low and high
int low = 0, high = N;
// Perform binary search
while (low <= high)
{
// Find the mid
int mid = (low + high) / 2;
// Check if first term is
// greater than 0
if (X - mid * diff > 0)
{
// Store the possible first term
first_term = X - mid * diff;
// Search between mid + 1 to high
low = mid + 1;
}
else
// Search between low to mid-1
high = mid - 1;
}
// Return the minimum first term
return first_term;
}
// Function that finds the Arithmetic
// Progression with minimum possible
// first term containing X and Y
static void printAP(int N, int X, int Y)
{
// Considering X to be
// smaller than Y always
if (X > Y)
{
X = X + Y;
Y = X - Y;
X = X - Y;
}
// Stores the max common difference
int maxDiff = Y - X;
// Stores the minimum first term
// and the corresponding common
// difference of the resultant AP
int first_term = int.MaxValue, diff = 0;
// Iterate over all the common difference
for(int i = 1; i * i <= maxDiff; i++)
{
// Check if X and Y is included
// for current common difference
if (maxDiff % i == 0)
{
// Store the possible
// common difference
int diff1 = i;
int diff2 = maxDiff / diff1;
// Number of terms from
// X to Y with diff1
// common difference
int terms1 = diff2 + 1;
// Number of terms from
// X to Y with diff2
// common difference
int terms2 = diff1 + 1;
// Find the corresponding first
// terms with diff1 and diff2
int first_term1 = minFirstTerm(X, diff1,
N - terms1);
int first_term2 = minFirstTerm(X, diff2,
N - terms2);
// Store the minimum first term
// and the corresponding
// common difference
if (first_term1 < first_term)
{
first_term = first_term1;
diff = diff1;
}
if (first_term2 < first_term)
{
first_term = first_term2;
diff = diff2;
}
}
}
// Print the resultant AP
for(int i = 0; i < N; i++)
{
Console.Write(first_term + " ");
first_term += diff;
}
}
// Driver Code
public static void Main(String[] args)
{
// Given length of AP
// and the two terms
int N = 5, X = 10, Y = 15;
// Function call
printAP(N, X, Y);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// Function that finds the minimum
// positive first term including X
// with given common difference and
// the number of terms
function minFirstTerm(X, diff, N)
{
// Stores the first term
let first_term = Number.MAX_VALUE;
// Initialize the low and high
let low = 0, high = N;
// Perform binary search
while (low <= high)
{
// Find the mid
let mid = Math.floor((low + high) / 2);
// Check if first term is
// greater than 0
if (X - mid * diff > 0)
{
// Store the possible first term
first_term = X - mid * diff;
// Search between mid + 1 to high
low = mid + 1;
}
else
// Search between low to mid-1
high = mid - 1;
}
// Return the minimum first term
return first_term;
}
// Function that finds the Arithmetic
// Progression with minimum possible
// first term containing X and Y
function prletAP(N, X, Y)
{
// Considering X to be
// smaller than Y always
if (X > Y)
{
X = X + Y;
Y = X - Y;
X = X - Y;
}
// Stores the max common difference
let maxDiff = Y - X;
// Stores the minimum first term
// and the corresponding common
// difference of the resultant AP
let first_term = Number.MAX_VALUE, diff = 0;
// Iterate over all the common difference
for(let i = 1; i * i <= maxDiff; i++)
{
// Check if X and Y is included
// for current common difference
if (maxDiff % i == 0)
{
// Store the possible
// common difference
let diff1 = i;
let diff2 = Math.floor(maxDiff / diff1);
// Number of terms from
// X to Y with diff1
// common difference
let terms1 = diff2 + 1;
// Number of terms from
// X to Y with diff2
// common difference
let terms2 = diff1 + 1;
// Find the corresponding first
// terms with diff1 and diff2
let first_term1 = minFirstTerm(X, diff1,
N - terms1);
let first_term2 = minFirstTerm(X, diff2,
N - terms2);
// Store the minimum first term
// and the corresponding
// common difference
if (first_term1 < first_term)
{
first_term = first_term1;
diff = diff1;
}
if (first_term2 < first_term)
{
first_term = first_term2;
diff = diff2;
}
}
}
// Print the resultant AP
for(let i = 0; i < N; i++)
{
document.write(first_term + " ");
first_term += diff;
}
}
// Driver Code
// Given length of AP
// and the two terms
let N = 5, X = 10, Y = 15;
// Function call
prletAP(N, X, Y);
// This code is contributed by souravghosh0416.
</script>
Producción:
5 10 15 20 25
Complejidad de tiempo: O(sqrt(abs(XY)) * log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por costheta_z y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA