C++ | O(N^2) | Identify all K and use the concept of "954. Array of Doubled Pairs"
Logic:\nSimilar to "954. Array of Doubled Pairs" or "2007. Find Original Array From Doubled Array"\n\nStep 1: Identify the possible K\'s\nStep 2: Maintain a cou
Logic:\nSimilar to "[954. Array of Doubled Pairs](https://leetcode.com/problems/array-of-doubled-pairs/)" or "[2007. Find Original Array From Doubled Array](https://leetcode.com/problems/find-original-array-from-doubled-array/)"\n\nStep 1: Identify the possible K\'s\nStep 2: Maintain a counter of all values of array\nStep 3: Check if for given K, the array can be divided into two arrays(smaller and larger arrays)\nStep 3.1: for any certain K, if \'arr[i]\' is present in arr, then \'arr[i] + 2k\' should also be present in arr\n\nFor Step 1: \nWe need to sort the arr, for example for nums = [2,10,6,4,8,12], we should make nums = [2,4,6,8,10,12]\nNote 1: 2 and 10 can\'t be a pair, as 2 is minimum of array and hence we can never be able to find the pair for 6 or 8\nNote 2: For a valid K, nums[0] + 2K, which is 2 + 2K can either be 4,6, or 8 (which are nums[1] to nums[3])\nNote 3: We can easily ignore other values than 2(nums[0]) to identify K\n\nFor Step 3.1: We can use hashmap, multiset etc. One should try either of the following problems to understand the concept:\n* [954. Array of Doubled Pairs](https://leetcode.com/problems/array-of-doubled-pairs/)\n* [2007. Find Original Array From Doubled Array](https://leetcode.com/problems/find-original-array-from-doubled-array/)\n\n\n```\nclass Solution {\npublic:\n    vector<int> findOriginalArray(vector<int>& arr, int k, unordered_map<int, int> counter) {\n        vector<int> ans;\n        vector<int> emptyArr;\n        /*Step 3.1\n            For each J, reduce the counter of arr[i] and arr[i] + 2*K by 1\n            If for some arr[i], arr[i] + 2*K doesn\'t exist or it\'s count can\'t be reduced further, then the K is invalid\n        */\n        for(int i = 0; i < arr.size(); i++){\n            if(counter[arr[i]] > 0){\n                ans.push_back(arr[i] + k);\n                counter[arr[i]]--;\n                if(counter[arr[i] + 2*k] <= 0)\n                    return emptyArr;\n                counter[arr[i] + 2*k]--;\n            }\n        }\n        return ans;\n    }\n    vector<int> recoverArray(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        vector<int> ans;\n        vector<int> listOfValidKs;\n        /*Step 1: Find the list of valid K\'s*/\n        for(int i = 1; i <= nums.size()/2; i++){\n            if(nums[i] != nums[0] && (nums[i] - nums[0])%2 == 0){\n                listOfValidKs.push_back((nums[i] - nums[0])/2);\n            }\n        }\n        /*!Step 1*/\n        /*Step 2: Maintain the counter*/\n        unordered_map<int, int> counter;\n        for(int i = 0; i < nums.size(); i++)\n            counter[nums[i]]++;\n        /*!Step 2*/\n        /*Step 3: Validate each K*/\n        for(int i = 0; i < listOfValidKs.size(); i++){\n            ans = findOriginalArray(nums, listOfValidKs[i], counter);\n            if(ans.size() > 0)\n                return ans;\n        }\n        /*!Step 3*/\n        ans.clear();\n        return ans;\n    }\n};\n```\n\nPlease share your feedbacks if any.
[]