2 Solutions | Brute Force, Optimized
Solution-1 Code (Brute Force, Simulation): -- TC: O(N^3), SC: O(N).\n\nclass Solution {\npublic:\n\t// TC: O(N^3), SC: O(N).\n    int minimumAddedInteger(vector
# Solution-1 Code (Brute Force, Simulation): -- TC: O(N^3), SC: O(N).\n```\nclass Solution {\npublic:\n\t// TC: O(N^3), SC: O(N).\n    int minimumAddedInteger(vector<int>& v1, vector<int>& v2) \n\t{\n\t    // STEP-1: SORT inputs.\n\t\tsort(v1.begin(),v1.end());\n        sort(v2.begin(),v2.end());\n        \n\t\tint ans=INT_MAX;\n        int m=v2.size();\n        int n=v1.size();\n        \n\t\t// STEP-2: Try removing all possible pairs & track the result:\n        for ( int i=0; i<n; i++ ) \n\t\t{\n            for ( int j=i+1; j<n; j++ ) \n\t\t\t{\n                vector<int>t; // vector after removing 2 elements\n                for ( int k=0; k<n; k++ )  \n\t\t\t\t{\n                    if ( k!=i && k!=j )  { \n                        t.push_back(v1[k]);\n                    }\n                }\n\t\t\t\t\n\t\t\t\t// Validate that diff is same in new array & if so track/update results.\n                int diff=v2[m-1]-t[m-1];\n                int f=0;\n                for ( int k=m-2; k>=0; k-- ) \n\t\t\t\t{\n                    int d=v2[k]-t[k];\n                    if ( d != diff ) {\n                        f=1;\n                        break;\n                    }\n                }\n                if ( f==0 )\n                    ans=min(ans,v2[m-1]-t[m-1]);\n            }\n        }\n        return ans;\n    }\n};\n```\n# Solution-2 Code (Optimized): -- TC: O(N^2), SC: O(logN)\n```\nclass Solution {\nprivate:\n\t// TC: O(N), SC: O(1)\n    bool check(vector<int>& nums1, vector<int>& nums2, int k)\n\t{\n        int count = 0, j = 0;\n        for ( int i = 0;  i < nums1.size() && j < nums2.size();  i++ ) \n\t\t{\n            if ( nums1[i] + k != nums2[j] ) count++;\n            else j++;\n        }\n        if ( count > 2 ) return 0;\n        return 1;\n    }\n\npublic:\n\t// TC: O(N^2), SC: O(logN)\n    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) \n\t{\n\t   // SORT inputs\n        sort(nums1.begin(), nums1.end());\n        sort(nums2.begin(), nums2.end());\n        \n\t\tint minEle = INT_MAX;  \n        for ( int i = 0;  i < nums1.size();  i++ ) \n\t\t{\n            int x = nums2[0] - nums1[i];\n            if ( check(nums1, nums2, x) ) {\n                minEle = min(minEle, x);\n            }\n        }\n        return minEle;\n    }\n};\n```
['Sorting', 'Simulation']