Given an array arr[] of N positive integers. We have to perform one operation on every odd element in the given array i.e., multiply every odd element by 2 in the given array, the task is to find the minimum difference between any two elements in the array after performing the given operation.
Examples:
Input: arr[] = {2, 8, 15, 29, 40}
Output: 1
Explanation:
Multiply the third element 15 by 2 so it will become 30.
Now you have 30 and 29, so the minimum difference will become 1.
Input: arr[] = { 3, 8, 13, 30, 50 }
Output : 2
Explanation:
Multiply 3 by 2 so it will become 6.
Now you have 6 and 8, so the minimum difference will become 2.
Approach:
- Convert every odd number in the given array to even by multiplying it by 2.
- Sort the given array in increasing order.
- Find the minimum difference between any two consecutive elements in the above-sorted array.
- The difference calculated above is the minimum difference between any two elements in the array after performing the given operation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define ll long long// Function to minimize the difference// between two elements of arrayvoid minDiff(vector<ll> a, int n){ // Find all the element which are // possible by multiplying // 2 to odd numbers for (int i = 0; i < n; i++) { if (a[i] % 2 == 1) a.push_back(a[i] * 2); } // Sort the array sort(a.begin(), a.end()); ll mindifference = a[1] - a[0]; // Find the minimum difference // Iterate and find which adjacent // elements have the minimum difference for (int i = 1; i < a.size(); i++) { mindifference = min(mindifference, a[i] - a[i - 1]); } // Print the minimum difference cout << mindifference << endl;}// Driver Codeint main(){ // Given array vector<ll> arr = { 3, 8, 13, 30, 50 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call minDiff(arr, n); return 0;} |
Java
// Java program for the above approach import java.util.*;class GFG{ // Function to minimize the difference // between two elements of array public static void minDiff(long[] a, int n) { // Find all the element which are // possible by multiplying // 2 to odd numbers for(int i = 0; i < n; i++) { if (a[i] % 2 == 1) a[i] *= 2; } // Sort the array Arrays.sort(a); long mindifference = a[1] - a[0]; // Find the minimum difference // Iterate and find which adjacent // elements have the minimum difference for(int i = 1; i < a.length; i++) { mindifference = Math.min(mindifference, a[i] - a[i - 1]); } // Print the minimum difference System.out.println(mindifference); } // Driver Code public static void main(String []args) { // Given array long [] arr = { 3, 8, 13, 30, 50 }; int n = arr.length; // Function call minDiff(arr, n); } }// This code is contributed by jrishabh99 |
Python3
# Python3 program for the above approach# Function to minimize the difference# between two elements of arraydef minDiff(a,n): # Find all the element which are # possible by multiplying # 2 to odd numbers for i in range(n): if (a[i] % 2 == 1): a.append(a[i] * 2) # Sort the array a = sorted(a) mindifference = a[1] - a[0] # Find the minimum difference # Iterate and find which adjacent # elements have the minimum difference for i in range(1, len(a)): mindifference = min(mindifference, a[i] - a[i - 1]) # Print the minimum difference print(mindifference)# Driver Codeif __name__ == '__main__': arr = [3, 8, 13, 30, 50] n = len(arr) # Function Call minDiff(arr, n)# This code is contributed by Mohit Kumar |
C#
// C# program for the above approach using System;class GFG{ // Function to minimize the difference // between two elements of array public static void minDiff(long[] a, int n) { // Find all the element which are // possible by multiplying // 2 to odd numbers for(int i = 0; i < n; i++) { if (a[i] % 2 == 1) a[i] *= 2; } // Sort the array Array.Sort(a); long mindifference = a[1] - a[0]; // Find the minimum difference // Iterate and find which adjacent // elements have the minimum difference for(int i = 1; i < a.Length; i++) { mindifference = Math.Min(mindifference, a[i] - a[i - 1]); } // Print the minimum difference Console.Write(mindifference); } // Driver Code public static void Main() { // Given array long []arr = { 3, 8, 13, 30, 50 }; int n = arr.Length; // Function call minDiff(arr, n); } }// This code is contributed by Code_Mech |
Javascript
<script>// Javascript implementation of the above approach// Function to minimize the difference // between two elements of array function minDiff(a, n) { // Find all the element which are // possible by multiplying // 2 to odd numbers for(let i = 0; i < n; i++) { if (a[i] % 2 == 1) a[i] *= 2; } // Sort the array a.sort((a, b) => a - b); let mindifference = a[1] - a[0]; // Find the minimum difference // Iterate and find which adjacent // elements have the minimum difference for(let i = 1; i < a.length; i++) { mindifference = Math.min(mindifference, a[i] - a[i - 1]); } // Print the minimum difference document.write(mindifference); } // Driver Code // Given array let arr = [ 3, 8, 13, 30, 50 ]; let n = arr.length; // Function call minDiff(arr, n);</script> |
Output:
2
Time complexity: O(nlogn)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
