Mindestsumme eines Paares, das mindestens K Abstand von einem Array entfernt ist
Bei einem gegebenen Array aus ganzen Zahlen A[] der Größe N besteht die Aufgabe darin, die minimale Summe zu finden, die von jedem Paar von Array-Elementen erhalten werden kann, die mindestens K Indizes voneinander entfernt sind.
Beispiele:
Eingabe: A[] = {1, 2, 3, 4, 5, 6}, K = 2
Ausgabe: 4
Erklärung:
Die minimal erzielbare Summe ergibt sich aus der Addition von 1 und 3, die einen Abstand von 2 haben.
Eingabe : A[] = {4, 2, 5, 4, 3, 2, 5}, K = 3
Ausgabe: 4
Erklärung:
Die minimale Summe, die erhalten werden kann, ist die Addition von 2 und 2, die einen Abstand von 4 haben.
Naiver Ansatz:
Der einfachste Ansatz zur Lösung des Problems besteht darin , für jeden i -ten Index über die Indizes [i + K, N – 1] zu iterieren und das minimale Element zu finden, z . B. min . Prüfen Sie, ob min + A[i] kleiner als die bisher erhaltene Mindestsumme ist, und aktualisieren Sie minimum_sum entsprechend. Geben Sie abschließend die minimum_sum aus .
Unten ist die Implementierung des obigen Ansatzes:
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); # Prthe 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 conytributed by divyeshrabadiya07. </script>
4
Zeitkomplexität: O(N 2 )
Hilfsraum: O(1)
Effizienter Ansatz:
Der obige Ansatz kann mit einem Suffix Array optimiert werden . Folgen Sie den unteren Schritten:
- Initialisieren Sie ein Suffix-Array (z. B. suffix[] ), wobei suffix[i] das Minimum aller Elemente von Index N-1 bis i speichert .
- Für jeden i -ten Index wird das minimale Element, das K voneinander entfernt ist, bei Index i + K im Suffix-Array gespeichert .
- Prüfen Sie für i im Bereich von 0 bis N – 1 , ob A[i] + suffix[i + k] < minimum_sum oder nicht und aktualisieren Sie minimum_sum entsprechend.
- Geben Sie schließlich minimum_sum als erforderliche Antwort aus.
Unten ist die Implementierung des obigen Ansatzes:
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]); } // Prlet the answer document.write(min_sum); } // Driver Code let A = [ 1, 2, 3, 4, 5, 6 ]; let K = 2; findMinSum(A, K); </script>
4
Zeitkomplexität: O(N)
Hilfsraum: O(N)
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .