🔄 Transforming Arrays into Palindromes: Minimizing Costs 💡Beginner's Guide
\uD83D\uDD04 Finding Minimum Cost for Palindromic Transformation\n\n## \uD83D\uDCA1 Problem Overview\n\nGiven an array of integers, the goal is to transform it 
# \uD83D\uDD04 Finding Minimum Cost for Palindromic Transformation\n\n## \uD83D\uDCA1 Problem Overview\n\nGiven an array of integers, the goal is to transform it into a palindrome by changing each element to the nearest palindrome. The cost of transformation is the sum of absolute differences between the original and transformed values. The objective is to minimize this cost.\n\n## \u2728 Approach\n\n1. **Check Palindrome:**\n   - Implement a function to check if a given number is a palindrome.\n\n2. **Find Median and Nearest Palindromes:**\n   - Find the median of the sorted array.\n   - Locate the nearest palindromes on both sides of the median.\n\n3. **Calculate Costs:**\n   - Calculate the cost of transforming the array to each of the nearest palindromes.\n   - Return the minimum cost.\n\n## \uD83D\uDCDD Step-by-Step Explanation\n\n1. **Check Palindrome Function:**\n   - Convert the number to a string for easy comparison of digits.\n   - Use two pointers (left and right) to check if the string is a palindrome.\n\n2. **Sort the Numbers:**\n   - Create a copy of the input array and sort it to find the median.\n\n3. **Find Nearest Palindromes:**\n   - Starting from the median, increment and decrement until a palindrome is found on both sides.\n\n4. **Calculate Costs:**\n   - For each nearest palindrome, calculate the cost of transforming the array.\n   - The cost is the sum of absolute differences between the original and transformed values.\n\n5. **Return Minimum Cost:**\n   - Return the minimum cost among the calculated costs.\n\n### **Dry Run 1: Odd-Length Array**\n\n**Input Array:** `[4, 9, 2, 6, 1]`\n\n**Step 1: Sorting the Array**\nSorted array: `[1, 2, 4, 6, 9]`\n\n**Step 2: Identify Nearest Palindromic Numbers**\n- Median: 4\n- Nearest Palindromic Numbers: 3 and 5\n\n**Step 3: Calculate Costs**\n- For Palindromic Number 3:\n  - Cost: `abs(1-3) + abs(2-3) + abs(4-3) + abs(6-3) + abs(9-3) = 16`\n- For Palindromic Number 5:\n  - Cost: `abs(1-5) + abs(2-5) + abs(4-5) + abs(6-5) + abs(9-5) = 16`\n\n**Step 4: Determine Minimum Cost**\nMinimum Cost: 16\n\n### **Dry Run 2: Even-Length Array**\n\n**Input Array:** `[7, 2, 5, 9]`\n\n**Step 1: Sorting the Array**\nSorted array: `[2, 5, 7, 9]`\n\n**Step 2: Identify Nearest Palindromic Numbers**\n- Median: 5\n- Nearest Palindromic Numbers: 4 and 6\n\n**Step 3: Calculate Costs**\n- For Palindromic Number 4:\n  - Cost: `abs(2-4) + abs(5-4) + abs(7-4) + abs(9-4) = 12`\n- For Palindromic Number 6:\n  - Cost: `abs(2-6) + abs(5-6) + abs(7-6) + abs(9-6) = 10`\n\n**Step 4: Determine Minimum Cost**\nMinimum Cost: 10\n\n\n\n\n## \uD83D\uDE80 Efficiency of the Approach\n\n1. **Time Complexity:**\n   - The time complexity is determined by the sorting operation, resulting in O(N log N).\n\n2. **Space Complexity:**\n   - The space complexity is O(N) due to the sorted copy of the input array.\n\n## \uD83D\uDD17 Related Problems\n\n- [LeetCode - Palindrome Pairs](https://leetcode.com/problems/palindrome-pairs/)\n\n\n## \uD83D\uDCDD Full Code \n```cpp []\nclass Solution {\npublic:\n    bool isPalindrome(int number) {\n        string strNumber = to_string(number);\n        int left = 0, right = strNumber.length() - 1;\n\n        while (left < right) {\n            if (strNumber[left] != strNumber[right]) {\n                return false;\n            }\n            left++;\n            right--;\n        }\n\n        return true;\n    }\n\n    long long minimumCost(vector<int>& numbers) {\n        vector<int> sortedNumbers = numbers;\n        sort(sortedNumbers.begin(), sortedNumbers.end());\n\n        int size = sortedNumbers.size();\n        int median = sortedNumbers[size / 2];\n\n        int nearestPalindromic1, nearestPalindromic2;\n        int difference = 0;\n\n        while (true) {\n            int candidate1 = median + difference;\n\n            if (isPalindrome(candidate1)) {\n                nearestPalindromic1 = candidate1;\n                break;\n            }\n\n            difference++;\n\n\n        }\n\n        difference = 0;\n\n        while (true) {\n            int candidate2 = median - difference;\n\n            if (isPalindrome(candidate2)) {\n                nearestPalindromic2 = candidate2;\n                break;\n            }\n\n            difference++;\n        }\n\n        long long cost1 = 0, cost2 = 0;\n\n        for (int i = 0; i < size; ++i) {\n            cost1 += abs(sortedNumbers[i] - nearestPalindromic1);\n            cost2 += abs(sortedNumbers[i] - nearestPalindromic2);\n        }\n\n        return min(cost1, cost2);\n    }\n};\n```\n\n\n```java []\nimport java.util.Arrays;\n\nclass Solution {\n    public boolean isPalindrome(int number) {\n        String strNumber = Integer.toString(number);\n        int left = 0, right = strNumber.length() - 1;\n\n        while (left < right) {\n            if (strNumber.charAt(left) != strNumber.charAt(right)) {\n                return false;\n            }\n            left++;\n            right--;\n        }\n\n        return true;\n    }\n\n    public long minimumCost(int[] numbers) {\n        int[] sortedNumbers = Arrays.copyOf(numbers, numbers.length);\n        Arrays.sort(sortedNumbers);\n\n        int size = sortedNumbers.length;\n        int median = sortedNumbers[size / 2];\n\n        int difference = 0;\n        int nearestPalindromic1, nearestPalindromic2;\n\n        while (true) {\n            int candidate1 = median + difference;\n\n            if (isPalindrome(candidate1)) {\n                nearestPalindromic1 = candidate1;\n                break;\n            }\n\n            difference++;\n        }\n\n        difference = 0;\n\n        while (true) {\n            int candidate2 = median - difference;\n\n            if (isPalindrome(candidate2)) {\n                nearestPalindromic2 = candidate2;\n                break;\n            }\n\n            difference++;\n        }\n\n        long cost1 = 0, cost2 = 0;\n\n        for (int i = 0; i < size; ++i) {\n            cost1 += Math.abs(sortedNumbers[i] - nearestPalindromic1);\n            cost2 += Math.abs(sortedNumbers[i] - nearestPalindromic2);\n        }\n\n        return Math.min(cost1, cost2);\n    }\n}\n```\n\n```javascript []\n\n    var isPalindrome = function(number) {\n        const strNumber = number.toString();\n        let left = 0, right = strNumber.length - 1;\n\n        while (left < right) {\n            if (strNumber[left] !== strNumber[right]) {\n                return false;\n            }\n            left++;\n            right--;\n        }\n\n        return true;\n    }\n\n    var minimumCost= function (numbers) {\n        const sortedNumbers = [...numbers].sort((a, b) => a - b);\n        const size = sortedNumbers.length;\n        const median = sortedNumbers[Math.floor(size / 2)];\n\n        let difference = 0;\n        let nearestPalindromic1, nearestPalindromic2;\n\n        while (true) {\n            const candidate1 = median + difference;\n\n            if ( isPalindrome(candidate1)) {\n                nearestPalindromic1 = candidate1;\n                break;\n            }\n\n            difference++;\n        }\n\n        difference = 0;\n\n        while (true) {\n            const candidate2 = median - difference;\n\n            if ( isPalindrome(candidate2)) {\n                nearestPalindromic2 = candidate2;\n                break;\n            }\n\n            difference++;\n        }\n\n        let cost1 = 0, cost2 = 0;\n\n        for (let i = 0; i < size; ++i) {\n            cost1 += Math.abs(sortedNumbers[i] - nearestPalindromic1);\n            cost2 += Math.abs(sortedNumbers[i] - nearestPalindromic2);\n        }\n\n        return Math.min(cost1, cost2);\n    }\n```\n``` python []\nclass Solution:\n    def isPalindrome(self, number):\n        strNumber = str(number)\n        left, right = 0, len(strNumber) - 1\n\n        while left < right:\n            if strNumber[left] != strNumber[right]:\n                return False\n            left += 1\n            right -= 1\n\n        return True\n\n    def minimumCost(self, numbers):\n        sortedNumbers = sorted(numbers)\n        size = len(sortedNumbers)\n        median = sortedNumbers[size // 2]\n\n        difference = 0\n        while True:\n            candidate1 = median + difference\n            if self.isPalindrome(candidate1):\n                nearestPalindromic1 = candidate1\n                break\n            difference += 1\n\n        difference = 0\n        while True:\n            candidate2 = median - difference\n            if self.isPalindrome(candidate2):\n                nearestPalindromic2 = candidate2\n                break\n            difference += 1\n\n        cost1, cost2 = 0, 0\n        for i in range(size):\n            cost1 += abs(sortedNumbers[i] - nearestPalindromic1)\n            cost2 += abs(sortedNumbers[i] - nearestPalindromic2)\n\n        return min(cost1, cost2)\n\n```\n```csharp []\nusing System;\nusing System.Linq;\n\npublic class Solution {\n    public bool IsPalindrome(int number) {\n        string strNumber = number.ToString();\n        int left = 0, right = strNumber.Length - 1;\n\n        while (left < right) {\n            if (strNumber[left] != strNumber[right]) {\n                return false;\n            }\n            left++;\n            right--;\n        }\n\n        return true;\n    }\n\n    public long MinimumCost(int[] numbers) {\n        int[] sortedNumbers = numbers.ToArray();\n        Array.Sort(sortedNumbers);\n\n        int size = sortedNumbers.Length;\n        int median = sortedNumbers[size / 2];\n\n        int difference = 0;\n        int nearestPalindromic1, nearestPalindromic2;\n\n        while (true) {\n            int candidate1 = median + difference;\n\n            if (IsPalindrome(candidate1)) {\n                nearestPalindromic1 = candidate1;\n                break;\n            }\n\n            difference++;\n        }\n\n        difference = 0;\n\n        while (true) {\n            int candidate2 = median - difference;\n\n            if (IsPalindrome(candidate2)) {\n                nearestPalindromic2 = candidate2;\n                break;\n            }\n\n            difference++;\n        }\n\n        long cost1 = 0, cost2 = 0;\n\n        for (int i = 0; i < size; ++i) {\n            cost1 += Math.Abs(sortedNumbers[i] - nearestPalindromic1);\n            cost2 += Math.Abs(sortedNumbers[i] - nearestPalindromic2);\n        }\n\n        return Math.Min(cost1, cost2);\n    }\n}\n```\n# \uD83D\uDCCAAnalysis\n![Figure_1.png](https://assets.leetcode.com/users/images/975480e1-50f1-4608-ab41-68f151e34dfe_1702789262.9098206.png)\n\n| Language    | Runtime (ms) | Memory (MB) |\n|-------------|--------------|-------------|\n| **C++**      | 68            | 52.4          |\n| **Java**     | 16            | 55.2          |\n| **C#**       | 161            | 59.7          |\n| **Python**   | 382          | 29.3        |\n| **JavaScript** | 134         | 55.5        |\n---\n# Consider UPVOTING\u2B06\uFE0F\n\n![image.png](https://assets.leetcode.com/users/images/853344be-bb84-422b-bdec-6ad5f07d0a7f_1696956449.7358863.png)\n\n\n# DROP YOUR SUGGESTIONS IN THE COMMENT\n\n## Keep Coding\uD83E\uDDD1\u200D\uD83D\uDCBB\n\n -- *CodingCTL SIGNING OFF*\n\n
['Array', 'Math', 'Sorting', 'C++', 'Java', 'Python3', 'JavaScript', 'C#']