Given an array A[] of size N, the task is to maximize the count of distinct elements in the array by inserting the absolute differences of the existing array elements.
Examples:
Input: A[] = {1, 2, 3, 5}
Output: 5
Explanation:
Possible absolute differences among the array elements are:
(2 – 1) = 1
(5 – 3) = 2
(5 – 2) = 3
(5 – 1) = 4
Hence, inserting 4 into the array maximizes the count of distinct elements.
Input: A[] = {1, 2, 3, 6}
Output: 6
Naive Approach:
Generate all possible pairs from the array and store their absolute differences in a set. Insert all the array elements into the set. The final size of the set denotes the maximum distinct elements that the array can possess after performing given operations.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach:
Follow the steps below to optimize the above approach:
- Find the maximum element of the array.The maximum possible absolute difference of any two elements does not exceed the maximum element of the array.
- Calculate the GCD of the array, since it is the common factor of the whole array.
- Divide the maximum element with the gcd of the array to get the count of the distinct elements.
Below is the implementation of the above approach:
C++
// C++ program to find the maximum // possible distinct elements that // can be obtained from the array // by performing the given operations #include <bits/stdc++.h> using namespace std; // Function to find the gcd // of two numbers int gcd( int x, int y) { if (x == 0) return y; return gcd(y % x, x); } // Function to calculate and return // the count of maximum possible // distinct elements in the array int findDistinct( int arr[], int n) { // Find the maximum element int maximum = *max_element(arr, arr + n); // Base Case if (n == 1) return 1; if (n == 2) { return (maximum / gcd(arr[0], arr[1])); } // Finding the gcd of first // two element int k = gcd(arr[0], arr[1]); // Calculate Gcd of the array for ( int i = 2; i < n; i++) { k = gcd(k, arr[i]); } // Return the total count // of distinct elements return (maximum / k); } // Driver Code int main() { int arr[] = { 1, 2, 3, 5 }; int n = sizeof (arr) / sizeof (arr[0]); cout << findDistinct(arr, n); return 0; } |
Java
// Java program to find the maximum // possible distinct elements that // can be obtained from the array // by performing the given operations import java.util.*; class GFG{ // Function to find the gcd // of two numbers static int gcd( int x, int y) { if (x == 0 ) return y; return gcd(y % x, x); } // Function to calculate and return // the count of maximum possible // distinct elements in the array static int findDistinct( int arr[], int n) { // Find the maximum element int maximum = Arrays.stream(arr).max().getAsInt(); // Base Case if (n == 1 ) return 1 ; if (n == 2 ) { return (maximum / gcd(arr[ 0 ], arr[ 1 ])); } // Finding the gcd of first // two element int k = gcd(arr[ 0 ], arr[ 1 ]); // Calculate Gcd of the array for ( int i = 2 ; i < n; i++) { k = gcd(k, arr[i]); } // Return the total count // of distinct elements return (maximum / k); } // Driver code public static void main (String[] args) { int arr[] = { 1 , 2 , 3 , 5 }; int n = arr.length; System.out.println(findDistinct(arr, n)); } } // This code is contributed by offbeat |
Python3
# Python3 program to find the maximum # possible distinct elements that # can be obtained from the array # by performing the given operations # Function to find the gcd # of two numbers def gcd(x, y): if (x = = 0 ): return y return gcd(y % x, x) # Function to calculate and return # the count of maximum possible # distinct elements in the array def findDistinct(arr, n): # Find the maximum element maximum = max (arr) # Base Case if (n = = 1 ): return 1 if (n = = 2 ): return (maximum / / gcd(arr[ 0 ], arr[ 1 ])) # Finding the gcd of first # two element k = gcd(arr[ 0 ], arr[ 1 ]) # Calculate Gcd of the array for i in range ( 2 , n): k = gcd(k, arr[i]) # Return the total count # of distinct elements return (maximum / / k) # Driver Code if __name__ = = '__main__' : arr = [ 1 , 2 , 3 , 5 ] n = len (arr) print (findDistinct(arr, n)) # This code is contributed by mohit kumar 29 |
C#
// C# program to find the maximum // possible distinct elements that // can be obtained from the array // by performing the given operations using System; using System.Linq; class GFG{ // Function to find the gcd // of two numbers static int gcd( int x, int y) { if (x == 0) return y; return gcd(y % x, x); } // Function to calculate and return // the count of maximum possible // distinct elements in the array static int findDistinct( int []arr, int n) { // Find the maximum element int maximum = arr.Max(); // Base Case if (n == 1) return 1; if (n == 2) { return (maximum / gcd(arr[0], arr[1])); } // Finding the gcd of first // two element int k = gcd(arr[0], arr[1]); // Calculate Gcd of the array for ( int i = 2; i < n; i++) { k = gcd(k, arr[i]); } // Return the total count // of distinct elements return (maximum / k); } // Driver Code public static void Main() { int []arr = { 1, 2, 3, 5 }; int n = arr.Length; Console.Write(findDistinct(arr, n)); } } // This code is contributed by Code_Mech |
Javascript
<script> // Javascript program to find the maximum // possible distinct elements that // can be obtained from the array // by performing the given operations // Function to find the gcd // of two numbers function gcd(x, y) { if (x == 0) return y; return gcd(y % x, x); } // Function to calculate and return // the count of maximum possible // distinct elements in the array function findDistinct(arr, n) { // Find the maximum element let maximum = Math.max(...arr); // Base Case if (n == 1) return 1; if (n == 2) { return (maximum / gcd(arr[0], arr[1])); } // Finding the gcd of first // two element let k = gcd(arr[0], arr[1]); // Calculate Gcd of the array for (let i = 2; i < n; i++) { k = gcd(k, arr[i]); } // Return the total count // of distinct elements return (maximum / k); } // Driver Code let arr = [ 1, 2, 3, 5 ]; let n = arr.length; document.write(findDistinct(arr, n)); </script> |
5
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!