Progresión aritmética que contiene X e Y con el primer término mínimo posible

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:

  1. Iterar de 1 a sqrt(abs(XY)) y considerar solo aquellas diferencias comunes que son factores de abs(XY) .
  2. 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 .
  3. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *