Максимально возможный остаток, когда элемент делится на другой элемент в массиве
Учитывая массив arr [] из N целых чисел, задача состоит в том, чтобы найти максимальное значение mod для любой пары (arr [i], arr [j]) из массива.
Примеры:
Input: arr[] = {2, 4, 1, 5, 3, 6}
Output: 5
(5 % 6) = 5 is the maximum possible mod value.Input: arr[] = {6, 6, 6, 6}
Output: 0
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: известно, что когда целое число делится на другое целое число X , остаток всегда будет меньше X. Таким образом, максимальное значение mod, которое может быть получено из массива, будет, когда делитель является максимальным элементом из массива, и это значение будет максимальным, когда делимое будет максимальным среди оставшихся элементов, то есть вторым максимальным элементом из массива, который это требуемый ответ. Обратите внимание, что результат будет 0, когда все элементы массива равны.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std; // Function to return the maximum mod// value for any pair from the arrayint maxMod(int arr[], int n){ int maxVal = *max_element(arr, arr + n); int secondMax = 0; // Find the second maximum // element from the array for (int i = 0; i < n; i++) { if (arr[i] < maxVal && arr[i] > secondMax) { secondMax = arr[i]; } } return secondMax;} // Driver codeint main(){ int arr[] = { 2, 4, 1, 5, 3, 6 }; int n = sizeof(arr) / sizeof(int); cout << maxMod(arr, n); return 0;} |
Java
// Java implementation of the approach class GFG { static int max_element(int arr[], int n) { int max = arr[0]; for(int i = 1; i < n ; i++) { if (max < arr[i]) max = arr[i]; } return max; } // Function to return the maximum mod // value for any pair from the array static int maxMod(int arr[], int n) { int maxVal = max_element(arr, n); int secondMax = 0; // Find the second maximum // element from the array for (int i = 0; i < n; i++) { if (arr[i] < maxVal && arr[i] > secondMax) { secondMax = arr[i]; } } return secondMax; } // Driver code public static void main (String[] args) { int arr[] = { 2, 4, 1, 5, 3, 6 }; int n = arr.length; System.out.println(maxMod(arr, n)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to return the maximum mod # value for any pair from the array def maxMod(arr, n): maxVal = max(arr) secondMax = 0 # Find the second maximum # element from the array for i in range(0, n): if (arr[i] < maxVal and arr[i] > secondMax): secondMax = arr[i] return secondMax # Driver code arr = [2, 4, 1, 5, 3, 6]n = len(arr)print(maxMod(arr, n)) # This code is contributed # by Sanjit Prasad |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG { static int max_element(int []arr, int n) { int max = arr[0]; for(int i = 1; i < n ; i++) { if (max < arr[i]) max = arr[i]; } return max; } // Function to return the maximum mod // value for any pair from the array static int maxMod(int []arr, int n) { int maxVal = max_element(arr, n); int secondMax = 0; // Find the second maximum // element from the array for (int i = 0; i < n; i++) { if (arr[i] < maxVal && arr[i] > secondMax) { secondMax = arr[i]; } } return secondMax; } // Driver code public static void Main (String[] args) { int []arr = { 2, 4, 1, 5, 3, 6 }; int n = arr.Length; Console.WriteLine(maxMod(arr, n)); } } // This code is contributed by 29AjayKumar |
5
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.