Dada una array de enteros A[] de tamaño N , la tarea es encontrar la suma mínima que se puede obtener de cualquier par de elementos de la array que estén al menos separados por K índices entre sí.
Ejemplos:
Entrada: A[] = {1, 2, 3, 4, 5, 6}, K = 2
Salida: 4
Explicación:
La suma mínima que se puede obtener es sumando 1 y 3 que están a una distancia de 2.
Entrada : A[] = {4, 2, 5, 4, 3, 2, 5}, K = 3
Salida: 4
Explicación:
La suma mínima que se puede obtener es sumando 2 y 2 que están a una distancia de 4.
Enfoque ingenuo:
el enfoque más simple para resolver el problema es iterar sobre los índices [i + K, N – 1] para cada i -ésimo índice y encontrar el elemento mínimo, digamos min . Compruebe si min + A[i] es menor que la suma mínima obtenida hasta el momento y actualice la suma_mínima en consecuencia. Finalmente, imprima la suma_mínima .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include<bits/stdc++.h> using namespace std; // Function to find the minimum // sum of two elements that // are atleast K distance apart void findMinSum(int A[], int K, int n) { int minimum_sum = INT_MAX; // Iterate over the array for(int i = 0; i < n; i++) { // Initialize the min value int mini = INT_MAX; // Iterate from i + k to N for(int j = i + K; j < n; j++) // Find the minimum mini = min(mini, A[j]); if (mini == INT_MAX) continue; // Update the minimum sum minimum_sum = min(minimum_sum, A[i] + mini); } // Print the answer cout << (minimum_sum); } // Driver Code int main() { int A[] = { 4, 2, 5, 4, 3, 2, 5 }; int K = 3; int n = sizeof(A) / sizeof(A[0]); findMinSum(A, K, n); return 0; } // This code is contributed by chitranayal
Java
// Java Program to implement // the above approach import java.util.*; class GFG { // Function to find the minimum // sum of two elements that // are atleast K distance apart public static void findMinSum(int A[], int K) { // Length of the array int n = A.length; int minimum_sum = Integer.MAX_VALUE; // Iterate over the array for (int i = 0; i < n; i++) { // Initialize the min value int min = Integer.MAX_VALUE; // Iterate from i + k to N for (int j = i + K; j < n; j++) // Find the minimum min = Math.min(min, A[j]); if (min == Integer.MAX_VALUE) continue; // Update the minimum sum minimum_sum = Math.min(minimum_sum, A[i] + min); } // Print the answer System.out.println(minimum_sum); } // Driver Code public static void main(String[] args) { int A[] = { 4, 2, 5, 4, 3, 2, 5 }; int K = 3; findMinSum(A, K); } }
Python3
# Python3 Program to implement # the above approach import sys # Function to find the minimum # sum of two elements that # are atleast K distance apart def findMinSum(A, K): # Length of the array n = len(A); minimum_sum = sys.maxsize; # Iterate over the array for i in range(n): # Initialize the min value minimum = sys.maxsize; # Iterate from i + k to N for j in range(i + K, n, 1): # Find the minimum minimum = min(minimum, A[j]); if (minimum == sys.maxsize): continue; # Update the minimum sum minimum_sum = min(minimum_sum, A[i] + minimum); # Print answer print(minimum_sum); # Driver Code if __name__ == '__main__': A = [4, 2, 5, 4, 3, 2, 5]; K = 3; findMinSum(A, K); # This code is contributed by sapnasingh4991
C#
// C# Program to implement // the above approach using System; class GFG{ // Function to find the minimum // sum of two elements that // are atleast K distance apart public static void findMinSum(int []A, int K) { // Length of the array int n = A.Length; int minimum_sum = int.MaxValue; // Iterate over the array for (int i = 0; i < n; i++) { // Initialize the min value int min = int.MaxValue; // Iterate from i + k to N for (int j = i + K; j < n; j++) // Find the minimum min = Math.Min(min, A[j]); if (min == int.MaxValue) continue; // Update the minimum sum minimum_sum = Math.Min(minimum_sum, A[i] + min); } // Print the answer Console.WriteLine(minimum_sum); } // Driver Code public static void Main(String[] args) { int []A = { 4, 2, 5, 4, 3, 2, 5 }; int K = 3; findMinSum(A, K); } } // This code is contributed by Rohit_ranjan
Javascript
<script> // Javascript program to implement // the above approach // Function to find the minimum // sum of two elements that // are atleast K distance apart function findMinSum(A, K, n) { let minimum_sum = Number.MAX_VALUE; // Iterate over the array for(let i = 0; i < n; i++) { // Initialize the min value let mini = Number.MAX_VALUE; // Iterate from i + k to N for(let j = i + K; j < n; j++) // Find the minimum mini = Math.min(mini, A[j]); if (mini == Number.MAX_VALUE) continue; // Update the minimum sum minimum_sum = Math.min(minimum_sum, A[i] + mini); } // Print the answer document.write(minimum_sum); } let A = [ 4, 2, 5, 4, 3, 2, 5 ]; let K = 3; let n = A.length; findMinSum(A, K, n); // This code is contributed by divyeshrabadiya07. </script>
4
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente:
el enfoque anterior se puede optimizar utilizando una array de sufijos . Siga los pasos a continuación:
- Inicialice una array de sufijos (digamos sufijo [] ), donde sufijo [i] almacena el mínimo de todos los elementos del índice N-1 a i .
- Para cualquier i -ésimo índice, el elemento mínimo que está separado por una distancia K se almacena en el índice i + K en la array de sufijos.
- Para i que va de 0 a N – 1 , compruebe si A[i] + sufijo[i + k] < suma_mínima o no y actualice la suma_mínima en consecuencia.
- Finalmente, imprima minimal_sum como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement //the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum // sum of two elements that // are atleast K distance apart void findMinSum(int A[], int K, int len) { // Length of the array int n = len; int suffix_min[n] = {0}; suffix_min[n - 1] = A[n - 1]; // Find the suffix array for (int i = n - 2; i >= 0; i--) suffix_min[i] = min(suffix_min[i + 1], A[i]); int min_sum = INT_MAX; // Iterate in the array for (int i = 0; i < n; i++) { if (i + K < n) // Update minimum sum min_sum = min(min_sum, A[i] + suffix_min[i + K]); } // Print the answer cout << min_sum; } // Driver Code int main() { int A[] = { 1, 2, 3, 4, 5, 6 }; int K = 2; int n = sizeof(A) / sizeof(A[0]); findMinSum(A, K, n); return 0; } // This code is contributed by Rohit_ranjan
Java
// Java Program to implement // the above approach import java.util.*; class GFG { // Function to find the minimum // sum of two elements that // are atleast K distance apart public static void findMinSum(int A[], int K) { // Length of the array int n = A.length; int suffix_min[] = new int[n]; suffix_min[n - 1] = A[n - 1]; // Find the suffix array for (int i = n - 2; i >= 0; i--) suffix_min[i] = Math.min(suffix_min[i + 1], A[i]); int min_sum = Integer.MAX_VALUE; // Iterate in the array for (int i = 0; i < n; i++) { if (i + K < n) // Update minimum sum min_sum = Math.min( min_sum, A[i] + suffix_min[i + K]); } // Print the answer System.out.println(min_sum); } // Driver Code public static void main(String[] args) { int A[] = { 1, 2, 3, 4, 5, 6 }; int K = 2; findMinSum(A, K); } }
Python3
# Python3 program to implement # the above approach import sys # Function to find the minimum # sum of two elements that # are atleast K distance apart def findMinSum(A, K): # Length of the array n = len(A); suffix_min = [0] * n; suffix_min[n - 1] = A[n - 1]; # Find the suffix array for i in range(n - 2, -1, -1): suffix_min[i] = min(suffix_min[i + 1], A[i]); min_sum = sys.maxsize; # Iterate in the array for i in range(n): if (i + K < n): # Update minimum sum min_sum = min(min_sum, A[i] + suffix_min[i + K]); # Print the answer print(min_sum); # Driver Code if __name__ == '__main__': A = [ 1, 2, 3, 4, 5, 6 ]; K = 2; findMinSum(A, K); # This code is contributed by Amit Katiyar
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find the minimum // sum of two elements that // are atleast K distance apart public static void findMinSum(int []A, int K) { // Length of the array int n = A.Length; int []suffix_min = new int[n]; suffix_min[n - 1] = A[n - 1]; // Find the suffix array for(int i = n - 2; i >= 0; i--) suffix_min[i] = Math.Min(suffix_min[i + 1], A[i]); int min_sum = int.MaxValue; // Iterate in the array for(int i = 0; i < n; i++) { if (i + K < n) // Update minimum sum min_sum = Math.Min(min_sum, A[i] + suffix_min[i + K]); } // Print the answer Console.WriteLine(min_sum); } // Driver Code public static void Main(String[] args) { int []A = { 1, 2, 3, 4, 5, 6 }; int K = 2; findMinSum(A, K); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program for the above approach // Function to find the minimum // sum of two elements that // are atleast K distance apart function findMinSum(A, K) { // Length of the array let n = A.length; let suffix_min = Array.from({length: n}, (_, i) => 0); suffix_min[n - 1] = A[n - 1]; // Find the suffix array for (let i = n - 2; i >= 0; i--) suffix_min[i] = Math.min(suffix_min[i + 1], A[i]); let min_sum = Number.MAX_VALUE; // Iterate in the array for (let i = 0; i < n; i++) { if (i + K < n) // Update minimum sum min_sum = Math.min( min_sum, A[i] + suffix_min[i + K]); } // Print the answer document.write(min_sum); } // Driver Code let A = [ 1, 2, 3, 4, 5, 6 ]; let K = 2; findMinSum(A, K); </script>
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por jrishabh99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA