C++ Simple Maths || Well Commented Code
IntuitionConstruct prefix array and then check for given palindrome what will be total costComplexity
Time complexity: O(n∗log(n))

Space complexity: O(n)
Code
# Intuition
Construct prefix array and then check for given palindrome what will be total cost



# Complexity
- Time complexity: $$O(n*log(n))$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(n)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
#define ll long long
class Solution {
public:
    long long minimumCost(vector<int>& nums) {
        vector<ll>pre;
        vector<ll>palin;
        
        ll sum = 0,cost = LONG_MAX,ct = 0;

        sort(nums.begin(),nums.end()); // construct prefix array
        for(auto x:nums){
            sum+=x;
            pre.push_back(sum);
        }

        // construct palidromes to test with:
        for(int i=1;i<10;i++){
            palin.push_back(i); // single digit palin
        }
        for(int i=1;i<=9999;i++){
            string s = to_string(i);
            string t = s;
            reverse(t.begin(),t.end());
             // even length palin
            ll pal = stol(s+t);
            palin.push_back(pal);
            if(pal>nums[nums.size()-1])
                continue;
            for(char ch ='0';ch<='9';ch++){ // odd lengths palin
                string t = s;
                reverse(t.begin(),t.end());
                t = s+ch+t;
                ll temp_num = stol(t);
                palin.push_back(temp_num);
                if(temp_num>nums[nums.size()-1])
                    break;
            }
        }

        // sort(palin.begin(),palin.end());

        for(auto x:palin){
            if(x>nums[nums.size()-1])
                ct++;
            if(ct>2 && (x>nums[nums.size()-1]))
                continue; // only run till first larger palindrome to max elem of nums.
            
            // find elem greater than x in nums:

            int idx = upper_bound(nums.begin(),nums.end(),x)-nums.begin();
            // uptil idx-1 mod will open with  x in negative sign

            ll sum_first_half = 0,sum_second_half,nums_first_half,nums_second_half;
            if(idx-1>=0)
                sum_first_half = pre[idx-1];
            
            sum_second_half = pre[pre.size()-1]-((idx-1)>=0?pre[idx-1]:0);

            nums_first_half = idx; // these will be +x
            nums_second_half = nums.size()-idx; // these will be -x

            ll total_cost = (nums_first_half-nums_second_half)*x + (sum_second_half-sum_first_half);

            cost = min(cost,total_cost);
        }
        return cost;
    }
};
```
['C++']