Median Search | C
Intuition\nTo find the minimum cost to convert an array of integers to a single palindromic number, search around the median of the array for palindromic number
# Intuition\nTo find the minimum cost to convert an array of integers to a single palindromic number, search around the median of the array for palindromic numbers and calculate the cost for each.\n\n# Approach\nSort the array, choose the median, search for palindromic numbers in a reasonable range around the median, and calculate the cost for each to find the minimum.\n\n# Complexity\n- Time complexity:O(nlogn+k.n)\n\n- Space complexity:O(1)\n\n# Code\n```\n#include <stdio.h>\n#include <stdlib.h>\n#include <limits.h>\n\n// Function to check if a number is palindromic\nint isPalindromic(int num) {\n    if (num < 0) return 0;\n    int reversed = 0, original = num;\n    while (num > 0) {\n        int digit = num % 10;\n        if (reversed > (INT_MAX - digit) / 10) return 0; // Check for overflow\n        reversed = reversed * 10 + digit;\n        num /= 10;\n    }\n    return reversed == original;\n}\n\n// Function to calculate the cost to convert the array to a single palindromic number\nlong long calculateCost(int* nums, int numsSize, int target) {\n    long long cost = 0;\n    for (int i = 0; i < numsSize; i++) {\n        cost += abs(nums[i] - target);\n    }\n    return cost;\n}\n\n// Comparison function for qsort\nint cmp(const void* a, const void* b) {\n    return (*(int*)a - *(int*)b);\n}\n\nlong long minimumCost(int* nums, int numsSize) {\n    // Sort the input array\n    qsort(nums, numsSize, sizeof(int), cmp);\n\n    // Choose the median as the candidate for minimization\n    int median = nums[numsSize / 2];\n\n    // Set a reasonable range for palindromic number search around the median\n    int lowerBound = median - 100000; // 100,000 below median\n    int upperBound = median + 100000; // 100,000 above median\n    if (lowerBound < 1) lowerBound = 1; // Ensure bounds are within valid range\n    if (upperBound > 1000000000) upperBound = 1000000000; // Ensure bounds are within valid range\n\n    // Calculate the minimum cost\n    long long minCost = LLONG_MAX;\n    for (int i = lowerBound; i <= upperBound; i++) {\n        if (isPalindromic(i)) {\n            long long cost = calculateCost(nums, numsSize, i);\n            if (cost < minCost) {\n                minCost = cost;\n            }\n        }\n    }\n\n    return minCost;\n}\n\n```
['Array', 'Math', 'Greedy', 'C', 'Sorting']