- Given an array arr[] of 2*N integers such that it consists of all elements along with the twice values of another array, say A[], the task is to find the array A[].
Examples:
Input: arr[] = {4, 1, 18, 2, 9, 8}
Output: 1 4 9
Explanation:
After taking double values of 1, 4, and 9 then adding them to the original array, All elements of the given array arr[] are obtainedInput: arr[] = {4, 1, 2, 2, 8, 2, 4, 4}
Output: 1 2 2 4
Approach: The given problem can be solved by counting the frequency of array elements in the HashMap array elements and observation can be made that, the smallest element in the array will always be a part of the original array, therefore it can be included in the result list res[]. The element with a double value of the smallest element will be the duplicate element that is not part of the original array so its frequency can be reduced from the map. Below steps can be followed to solve the problem:
- Sort the given array arr[] in ascending order
- Iterate through the array elements and store the numbers and their frequencies in a hashmap
- Create a result list res[] to store the elements present in the original list
- Add the first element in the result list and reduce the frequency of the element which has a double value of the first element.
- Traverse the array and check for the frequency of every element in the map:
- If the frequency is greater than 0, then add the element in the result list and decrement the frequency.
- Otherwise, skip the element and move ahead because it is a double value and not a part of the original array.
- After completing the above steps, print the elements in the list res[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the original array// from the doubled arrayvector<int> findOriginal(vector<int>& arr){ // Stores the numbers and // their frequency map<int, int> numFreq; // Add number with their frequencies // in the hashmap for (int i = 0; i < arr.size(); i++) { numFreq[arr[i]]++; } // Sort the array sort(arr.begin(), arr.end()); // Initialize an arraylist vector<int> res; for (int i = 0; i < arr.size(); i++) { // Get the frequency of the number int freq = numFreq[arr[i]]; if (freq > 0) { // Element is of original array res.push_back(arr[i]); // Decrement the frequency of // the number numFreq[arr[i]]--; int twice = 2 * arr[i]; // Decrement the frequency of // the number having double value numFreq[twice]--; } } // Return the resultant string return res;}// Driver Codeint main(){ vector<int> arr = { 4, 1, 2, 2, 2, 4, 8, 4 }; vector<int> res = findOriginal(arr); // Print the result list for (int i = 0; i < res.size(); i++) { cout << res[i] << " "; } return 0;} // This code is contributed by rakeshsahni |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the original array // from the doubled array public static List<Integer> findOriginal(int[] arr) { // Stores the numbers and // their frequency Map<Integer, Integer> numFreq = new HashMap<>(); // Add number with their frequencies // in the hashmap for (int i = 0; i < arr.length; i++) { numFreq.put( arr[i], numFreq.getOrDefault(arr[i], 0) + 1); } // Sort the array Arrays.sort(arr); // Initialize an arraylist List<Integer> res = new ArrayList<>(); for (int i = 0; i < arr.length; i++) { // Get the frequency of the number int freq = numFreq.get(arr[i]); if (freq > 0) { // Element is of original array res.add(arr[i]); // Decrement the frequency of // the number numFreq.put(arr[i], freq - 1); int twice = 2 * arr[i]; // Decrement the frequency of // the number having double value numFreq.put( twice, numFreq.get(twice) - 1); } } // Return the resultant string return res; } // Driver Code public static void main(String[] args) { List<Integer> res = findOriginal( new int[] { 4, 1, 2, 2, 2, 4, 8, 4 }); // Print the result list for (int i = 0; i < res.size(); i++) { System.out.print( res.get(i) + " "); } }} |
Python3
# Python program for the above approach# Function to find the original array# from the doubled arraydef findOriginal(arr): # Stores the numbers and # their frequency numFreq = {} # Add number with their frequencies # in the hashmap for i in range(0, len(arr)): if (arr[i] in numFreq): numFreq[arr[i]] += 1 else: numFreq[arr[i]] = 1 # Sort the array arr.sort() # Initialize an arraylist res = [] for i in range(0, len(arr)): # Get the frequency of the number freq = numFreq[arr[i]] if (freq > 0): # Element is of original array res.append(arr[i]) # Decrement the frequency of # the number numFreq[arr[i]] -= 1 twice = 2 * arr[i] # Decrement the frequency of # the number having double value numFreq[twice] -= 1 # Return the resultant string return res# Driver Codearr = [4, 1, 2, 2, 2, 4, 8, 4]res = findOriginal(arr)# Print the result listfor i in range(0, len(res)): print(res[i], end=" ")# This code is contributed by _Saurabh_Jaiswal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to find the original array // from the doubled array public static List<int> findOriginal(int[] arr) { // Stores the numbers and // their frequency Dictionary<int, int> numFreq = new Dictionary<int, int>(); // Add number with their frequencies // in the hashmap for (int i = 0; i < arr.Length; i++) { if(numFreq.ContainsKey(arr[i])){ numFreq[arr[i]] = numFreq[arr[i]] + 1; }else{ numFreq.Add(arr[i], 1); } } // Sort the array Array.Sort(arr); // Initialize an arraylist List<int> res = new List<int>(); for (int i = 0; i < arr.Length; i++) { // Get the frequency of the number int freq = numFreq[arr[i]]; if (freq > 0) { // Element is of original array res.Add(arr[i]); // Decrement the frequency of // the number numFreq[arr[i]] = freq - 1; int twice = 2 * arr[i]; // Decrement the frequency of // the number having double value numFreq[twice] = numFreq[twice] - 1; } } // Return the resultant string return res; } // Driver Code public static void Main() { List<int> res = findOriginal(new int[] { 4, 1, 2, 2, 2, 4, 8, 4 }); // Print the result list for (int i = 0; i < res.Count; i++) { Console.Write(res[i] + " "); } }}// This code is contributed by gfgking. |
Javascript
<script>// Javascript program for the above approach// Function to find the original array// from the doubled arrayfunction findOriginal(arr) { // Stores the numbers and // their frequency let numFreq = new Map(); // Add number with their frequencies // in the hashmap for (let i = 0; i < arr.length; i++) { if (numFreq.has(arr[i])) { numFreq.set(arr[i], numFreq.get(arr[i]) + 1); } else { numFreq.set(arr[i], 1); } } // Sort the array arr.sort((a, b) => a - b); // Initialize an arraylist let res = []; for (let i = 0; i < arr.length; i++) { // Get the frequency of the number let freq = numFreq.get(arr[i]); if (freq > 0) { // Element is of original array res.push(arr[i]); // Decrement the frequency of // the number numFreq.set(arr[i], numFreq.get(arr[i]) - 1); let twice = 2 * arr[i]; // Decrement the frequency of // the number having double value numFreq.set(twice, numFreq.get(twice) - 1); } } // Return the resultant string return res;}// Driver Codelet arr = [4, 1, 2, 2, 2, 4, 8, 4];let res = findOriginal(arr);// Print the result listfor (let i = 0; i < res.length; i++) { document.write(res[i] + " ");}// This code is contributed by gfgking.</script> |
Output:
1 2 2 4
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
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!
