Given an array arr[] of size N, the task is to maximize the count of distinct array elements by repeatedly inserting the absolute difference between all possible pairs of the given array.
Examples:
Input: arr[] = { 2, 4, 16 }
Output: 9
Explanation:
Inserting (arr[2] – arr[1]) modifies arr[] to { 2, 4, 12, 16 }
Inserting (arr[2] – arr[1]) modifies arr[] to { 2, 4, 8, 12, 16 }
Inserting (arr[2] – arr[1]) modifies arr[] to { 2, 4, 6, 8, 12, 16 }
Inserting (arr[4] – arr[0]) modifies arr[] to { 2, 4, 6, 8, 10, 12, 16 }
Inserting (arr[6] – arr[0]) modifies arr[] to { 2, 4, 6, 8, 10, 12, 14 16 }
Inserting (arr[2] – arr[0]) modifies arr[] to { 2, 4, 4 6, 8, 10, 12, 14 16 }
Inserting (arr[2] – arr[1]) modifies arr[] to { 0, 2, 4, 4 6, 8, 10, 12, 14 16 }
Therefore, the required output is 9.Input: arr[] = { 3, 6, 5, 4 }
Output: 7
Naive Approach: The simplest approach to solve this problem is to repeatedly select a pair from the given array and insert the absolute difference of that pair. Finally, check if the absolute difference of all possible pairs is already present in the array or not. If found to be true, then print the count of distinct elements into the array.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The idea is to use the fact that the GCD of two numbers can be obtained by repeatedly subtracting the smaller number from the bigger number until two elements become equal. Therefore, insert the elements into the array such that the absolute difference between all the adjacent elements must be equal to the GCD of the array. Follow the steps below to solve the problem:
- Find the largest element of the array say Max.
- Find the GCD of the array say, GCDArr.
- Finally, print the value of ((Max / GCDArr) + 1).
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the gcd of// the two numbersint gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);}// Function to find distinct elements in the array// by repeatedly inserting the absolute difference// of all possible pairsint DistinctValues(int arr[], int N){ // Stores largest element // of the array int max_value = INT_MIN; // Traverse the array, arr[] for (int i = 0; i < N; ++i) { // Update max_value max_value = max(max_value, arr[i]); } // Stores GCD of array int GCDArr = arr[0]; // Traverse the array, arr[] for (int i = 1; i < N; ++i) { // Update GCDArr GCDArr = gcd(GCDArr, arr[i]); } // Stores distinct elements in the array by // repeatedly inserting absolute difference // of all possible pairs int answer = (max_value / GCDArr) + 1; return answer;}// Driver Codeint main(){ // Given array arr[] int arr[] = { 4, 12, 16, 24 }; int N = sizeof(arr) / sizeof(int); cout << DistinctValues(arr, N); return 0;}// This code is contributed by hemanth gadarla |
Java
// Java program of the above approachimport java.util.*;class GFG{ // Function to find the gcd of// the two numbersstatic int gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);}// Function to find distinct elements in the array// by repeatidely inserting the absolute difference// of all possible pairsstatic int DistinctValues(int arr[], int N){ // Stores largest element // of the array int max_value = Integer.MIN_VALUE; // Traverse the array, arr[] for (int i = 0; i < N; ++i) { // Update max_value max_value = Math.max(max_value, arr[i]); } // Stores GCD of array int GCDArr = arr[0]; // Traverse the array, arr[] for (int i = 1; i < N; ++i) { // Update GCDArr GCDArr = gcd(GCDArr, arr[i]); } // Stores distinct elements in the array by // repeatidely inserting absolute difference // of all possible pairs int answer = (max_value / GCDArr) + 1; return answer;} // Driver codepublic static void main(String[] args){ // Given array arr[] int arr[] = { 4, 12, 16, 24 }; int N = arr.length; System.out.println(DistinctValues(arr, N));}}// This code is contributed by sanjoy_62 |
Python3
# Python3 program of the above approachimport sys # Function to find the gcd of# the two numbersdef gcd(a, b): if a == 0: return b return gcd(b % a, a)# Function to find distinct elements in # the array by repeatidely inserting the # absolute difference of all possible pairsdef DistinctValues(arr, N): # Stores largest element # of the array max_value = -sys.maxsize - 1 # Update max_value max_value = max(arr) # Stores GCD of array GCDArr = arr[0] # Traverse the array, arr[] for i in range(1, N): # Update GCDArr GCDArr = gcd(GCDArr, arr[i]) # Stores distinct elements in the array by # repeatedely inserting absolute difference # of all possible pairs answer = max_value // GCDArr return answer + 1# Driver code# Given array arr[]arr = [ 4, 12, 16, 24 ]N = len(arr)print(DistinctValues(arr, N))# This code is contributed by hemanth gadarla |
C#
// C# program of the above approach using System;class GFG { // Function to find the gcd of // the two numbers static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to find distinct elements in the array // by repeatidely inserting the absolute difference // of all possible pairs static int DistinctValues(int[] arr, int N) { // Stores largest element // of the array int max_value = Int32.MinValue; // Traverse the array, arr[] for (int i = 0; i < N; ++i) { // Update max_value max_value = Math.Max(max_value, arr[i]); } // Stores GCD of array int GCDArr = arr[0]; // Traverse the array, arr[] for (int i = 1; i < N; ++i) { // Update GCDArr GCDArr = gcd(GCDArr, arr[i]); } // Stores distinct elements in the array by // repeatidely inserting absolute difference // of all possible pairs int answer = (max_value / GCDArr) + 1; return answer; } // Driver code static void Main() { // Given array arr[] int[] arr = { 4, 12, 16, 24 }; int N = arr.Length; Console.WriteLine(DistinctValues(arr, N)); }}// This code is contributed by susmitakundugoaldanga. |
Javascript
<script>// javascript program of the above approach // Function to find the gcd of // the two numbers function gcd(a , b) { if (a == 0) return b; return gcd(b % a, a); } // Function to find distinct elements in the array // by repeatidely inserting the absolute difference // of all possible pairs function DistinctValues(arr , N) { // Stores largest element // of the array var max_value = Number.MIN_VALUE; // Traverse the array, arr for (i = 0; i < N; ++i) { // Update max_value max_value = Math.max(max_value, arr[i]); } // Stores GCD of array var GCDArr = arr[0]; // Traverse the array, arr for (i = 1; i < N; ++i) { // Update GCDArr GCDArr = gcd(GCDArr, arr[i]); } // Stores distinct elements in the array by // repeatidely inserting absolute difference // of all possible pairs var answer = (max_value / GCDArr) + 1; return answer; } // Driver code // Given array arr var arr = [ 4, 12, 16, 24 ]; var N = arr.length; document.write(DistinctValues(arr, N));// This code contributed by gauravrajput1 </script> |
7
Time complexity: O(N * Min), where Min is the smallest element of the array
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
