Dados tres enteros positivos N , X e Y(X<Y) . La tarea es encontrar una array de longitud N que contenga tanto X como Y , y cuando se clasifique en orden creciente , la array debe formar una progresión aritmética
Ejemplos:
Entrada: N = 5, X = 20, Y = 50
Salida: 20 30 40 50 10
Explicación: La array cuando se ordena en orden creciente forma una progresión aritmética con diferencia común 10 .Entrada: n = 17, x = 23445, y = 1000000
Salida: 23445 218756 414067 609378 804689 1000000 1195311 1390622 1585933 1781244 19765555 2171866 2367177 2562488 275799 29533333110 1948444444 44 44
Enfoque: En este problema, se puede observar que si el elemento máximo se va a minimizar , entonces se puede suponer que Y debería ser el elemento mayor. Si Y es el mayor, entonces cada uno de los elementos restantes será menor o igual que Y. Si Y no es el elemento más grande de la array, entonces se pueden considerar elementos mayores que Y.
Siga los pasos a continuación para resolver el problema dado:
- Compruebe si algunos elementos que tienen una diferencia común están presentes entre X e Y. Para ello, comprueba si ( YX ) es divisible por ( N -1). Si es divisible, entonces decrece N y la diferencia común d viene dada por:
d = (YX)/(N-1)
- Si no es divisible, disminuya (n-1) y repita el paso anterior en un bucle hasta que el denominador sea distinto de cero.
- Si no existen tales elementos entre X e Y, entonces la diferencia común d viene dada por:
d = (YX)
- Deje que la array resultante se almacene en el vector ans . Empuje los elementos que se encuentran entre X e Y en el vector ans para usar un bucle for.
- Si N no es igual a cero, inserte los elementos en ans comenzando desde ( Xd ) con diferencia común d .
- Si N es igual a cero, emite ans . De lo contrario, inserte los elementos en ans comenzando desde ( Y+d ) hasta obtener la array requerida.
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 find the array which when // sorted forms an arithmetic progression // and has the minimum possible maximum element void findArray(int N, int X, int Y) { // Stores the difference of Y and X int r = Y - X; // To indicate the absence of required // elements between X and Y int d = -1; // Stores the number of required elements // present between X and Y int num = 0; // Loop to find the number of required // elements between X and Y for (int i = (N - 1); i > 0; i--) { // If r is divisible by i if (r % i == 0) { // Stores the common difference // of the elements d = r / i; // Decrease num by 1 num = i - 1; // Break from the loop break; } } // If the number of elements present // between X and Y is zero if (d == -1) { // Update common difference d = Y - X; } // Update N N = N - 2 - num; // Stores the resultant array vector<int> ans; // Loop to insert the found elements // in the resultant vector for (int i = X; i <= Y; i += d) { ans.push_back(i); } // Stores the element to be inserted in // the resultant vector int i = X; // Loop to insert elements less than X // in the resultant vector while (N > 0 && i > 0) { i = i - d; // i must be positive if (i > 0) { ans.push_back(i); // Update N N--; } } // Stores the element to be inserted in // the resultant vector i = Y; // Loop to insert elements greater than Y // in the resultant vector while (N > 0) { i = i + d; ans.push_back(i); // Update N N--; } // Output the required array for (int i = 0; i < ans.size(); ++i) { cout << ans[i] << " "; } } // Driver Code int main() { // Given N, X and Y int N = 5, X = 20, Y = 50; // Function Call findArray(N, X, Y); return 0; }
Java
// Java program for the above approach import java.util.ArrayList; class GFG { // Function to find the array which when // sorted forms an arithmetic progression // and has the minimum possible maximum element static void findArray(int N, int X, int Y) { // Stores the difference of Y and X int r = Y - X; // To indicate the absence of required // elements between X and Y int d = -1; // Stores the number of required elements // present between X and Y int num = 0; // Loop to find the number of required // elements between X and Y for (int i = (N - 1); i > 0; i--) { // If r is divisible by i if (r % i == 0) { // Stores the common difference // of the elements d = r / i; // Decrease num by 1 num = i - 1; // Break from the loop break; } } // If the number of elements present // between X and Y is zero if (d == -1) { // Update common difference d = Y - X; } // Update N N = N - 2 - num; // Stores the resultant array ArrayList<Integer> ans = new ArrayList<Integer>(); // Loop to insert the found elements // in the resultant vector for (int i = X; i <= Y; i += d) { ans.add(i); } // Stores the element to be inserted in // the resultant vector int j = X; // Loop to insert elements less than X // in the resultant vector while (N > 0 && j > 0) { j = j - d; // i must be positive if (j > 0) { ans.add(j); // Update N N--; } } // Stores the element to be inserted in // the resultant vector j = Y; // Loop to insert elements greater than Y // in the resultant vector while (N > 0) { j = j + d; ans.add(j); // Update N N--; } // Output the required array for (int i = 0; i < ans.size(); ++i) { System.out.print(ans.get(i) + " "); } } // Driver Code public static void main(String[] args) { // Given N, X and Y int N = 5, X = 20, Y = 50; // Function Call findArray(N, X, Y); } } // This code is contributed by gfgking.
Python3
# python program for the above approach # Function to find the array which when # sorted forms an arithmetic progression # and has the minimum possible maximum element def findArray(N, X, Y): # Stores the difference of Y and X r = Y - X # To indicate the absence of required # elements between X and Y d = -1 # Stores the number of required elements # present between X and Y num = 0 # Loop to find the number of required # elements between X and Y for i in range(N - 1, 0, -1): # If r is divisible by i if (r % i == 0): # Stores the common difference # of the elements d = r // i # Decrease num by 1 num = i - 1 # Break from the loop break # If the number of elements present # between X and Y is zero if (d == -1): # Update common difference d = Y - X # Update N N = N - 2 - num # Stores the resultant array ans = [] # Loop to insert the found elements # in the resultant vector for i in range(X, Y + 1, d): ans.append(i) # Stores the element to be inserted in # the resultant vector i = X # Loop to insert elements less than X # in the resultant vector while (N > 0 and i > 0): i = i - d # i must be positive if (i > 0): ans.append(i) # Update N N -= 1 # Stores the element to be inserted in # the resultant vector i = Y # Loop to insert elements greater than Y # in the resultant vector while (N > 0): i = i + d ans.append(i) # Update N N -= 1 # Output the required array for i in range(0, len(ans)): print(ans[i], end=" ") # Driver Code if __name__ == "__main__": # Given N, X and Y N = 5 X = 20 Y = 50 # Function Call findArray(N, X, Y) # This code is contributed by rakeshsahni
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to find the array which when // sorted forms an arithmetic progression // and has the minimum possible maximum element static void findArray(int N, int X, int Y) { // Stores the difference of Y and X int r = Y - X; // To indicate the absence of required // elements between X and Y int d = -1; // Stores the number of required elements // present between X and Y int num = 0; // Loop to find the number of required // elements between X and Y for (int i = (N - 1); i > 0; i--) { // If r is divisible by i if (r % i == 0) { // Stores the common difference // of the elements d = r / i; // Decrease num by 1 num = i - 1; // Break from the loop break; } } // If the number of elements present // between X and Y is zero if (d == -1) { // Update common difference d = Y - X; } // Update N N = N - 2 - num; // Stores the resultant array List<int> ans = new List<int>(); // Loop to insert the found elements // in the resultant vector for (int i = X; i <= Y; i += d) { ans.Add(i); } // Stores the element to be inserted in // the resultant vector int j = X; // Loop to insert elements less than X // in the resultant vector while (N > 0 && j > 0) { j = j - d; // i must be positive if (j > 0) { ans.Add(j); // Update N N--; } } // Stores the element to be inserted in // the resultant vector j = Y; // Loop to insert elements greater than Y // in the resultant vector while (N > 0) { j = j + d; ans.Add(j); // Update N N--; } // Output the required array for (int i = 0; i < ans.Count; ++i) { Console.Write( ans[i] + " "); } } // Driver Code public static void Main(String[] args) { // Given N, X and Y int N = 5, X = 20, Y = 50; // Function Call findArray(N, X, Y); } } // This code is contributed by code_hunt.
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the array which when // sorted forms an arithmetic progression // and has the minimum possible maximum element function findArray(N, X, Y) { // Stores the difference of Y and X let r = Y - X; // To indicate the absence of required // elements between X and Y let d = -1; // Stores the number of required elements // present between X and Y let num = 0; // Loop to find the number of required // elements between X and Y for (let i = (N - 1); i > 0; i--) { // If r is divisible by i if (r % i == 0) { // Stores the common difference // of the elements d = r / i; // Decrease num by 1 num = i - 1; // Break from the loop break; } } // If the number of elements present // between X and Y is zero if (d == -1) { // Update common difference d = Y - X; } // Update N N = N - 2 - num; // Stores the resultant array let ans = []; // Loop to insert the found elements // in the resultant vector for (let i = X; i <= Y; i += d) { ans.push(i); } // Stores the element to be inserted in // the resultant vector let i = X; // Loop to insert elements less than X // in the resultant vector while (N > 0 && i > 0) { i = i - d; // i must be positive if (i > 0) { ans.push(i); // Update N N--; } } // Stores the element to be inserted in // the resultant vector i = Y; // Loop to insert elements greater than Y // in the resultant vector while (N > 0) { i = i + d; ans.push(i); // Update N N--; } // Output the required array for (let i = 0; i < ans.length; ++i) { document.write(ans[i] + " "); } } // Driver Code // Given N, X and Y let N = 5, X = 20, Y = 50; // Function Call findArray(N, X, Y); // This code is contributed by Potta Lokesh </script>
20 30 40 50 10
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por anusha00466 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA