Step By Step Explaination
Logic\nThis Problem is all about finding K which is subtracted from original array (lower[i] = ar[i] - K) or added to the original array (higher[i] = ar[i] + K)
## Logic\nThis Problem is all about finding K which is subtracted from original array (lower[i] = ar[i] - K) or added to the original array (higher[i] = ar[i] + K)\n\n## Code\n```\nclass Solution {\npublic:\n    vector<int> recoverArray(vector<int>& nums) {\n        int n = nums.size();\n//         step - 1: arrange elements in ascending order\n        sort(nums.begin(), nums.end());\n//         Now, the smallest element will always belong to "lower" array\n//         so, let it be lower[0]\n//         now 2c = higher[0] - lower[0] \n//         step - 2: find higher[0]\n        for(int i = 1; i < n; i++){\n            vector<int> v;\n            v.push_back(nums[0]);\n//             lets say ar[i] is highest[0] then\n//             say k = 2c\n//             1. k should be even and not equal to 0\n//             2. for every element present in lower there must exist an element in higher\n//             as lower[i] = higher[i] + k\n//             Step-3: find k\n            int k = nums[i] - v.back();\n//             Step-4: check condition 1\n            if(k & 1 || k == 0){\n                continue;\n            }\n            // cout << k << " ";\n//             Step-5: Check condition 2\n//             Create a Multiset to check if the element exist or not in log n time\n            multiset<int> s(nums.begin(), nums.end());\n//             now we don\'t need the used elements so remove nums[0] and nums[i]\n            s.erase(s.find(nums[0])), s.erase(s.find(nums[i]));\n//             check if k is valid for all remaining elements of set\n            while(!s.empty()){\n//                 get lowerest element\n                int x = *(s.begin());\n//                 and push x in answer vector\n                v.push_back(x);       \n//                 remove x from se to avoid repeating elements\n                s.erase(s.find(x));\n//                 find if x + k exist\n                if(s.find(x+k) == s.end()){\n//                 if is doesn\'t exist then k is invalid\n                   break;\n                }\n//              if it exist then remove x + k\n                s.erase(s.find(x + k));\n                }\n            if(s.empty()){\n//                 this means k is valid\n//                 original array = arr[i]\n//                 lower = arr[i] - c\n//                 k = 2c;\n                for(int j = 0; j < v.size(); j++){\n                    v[j] += k/2;\n                }\n                return v;\n            }\n        }\n        return {};\n    }\n};\n```\nI wasn\'t able to solve the Question on my own at first, But then I read and understood all the discussions and finally created this solution which seems like the easiest possible solution to me. Hopefully, this solution can help you better understand and solve this problem.
['C']