No DP, No Recursion, C++ Graph Solution
class Solution {\npublic:\n\n    \n    int minimumIncompatibility(vector& arr, int k) {\n        \n        \n        int n = arr.size();\n        \n        vect
class Solution {\npublic:\n\n    \n    int minimumIncompatibility(vector<int>& arr, int k) {\n        \n        \n        int n = arr.size();\n        \n        vector<int> masks;\n        unordered_map<int, int> cost;\n        k = n / k;\n        \n        for(int i = 0; i < (1 << n); i++)\n        {\n            int x = __builtin_popcount(i);\n            \n            \n            if(x == k)\n            {\n                int mask = 0;\n                bool flag = 1;\n                \n                for(int j = 0; j < n; j++)\n                if(i & (1 << j))\n                {\n                      if(mask & (1 << arr[j]))\n                        {\n                            flag = 0;\n                            break;\n                        }\n                    else mask = mask | (1 << arr[j]);\n                }\n                     \n                if(flag)\n                {\n                     masks.push_back(i);\n                    \n                     int x = 0;\n                    \n                     for(int k = 16; k >= 0; k--)\n                         if(mask & (1 << k))\n                         {\n                             x = k;\n                             break;\n                         }\n                    \n                    for(int k = 0; k <= 16; k++)\n                        if(mask & (1 << k))\n                        {\n                            x = x - k;\n                            break;\n                        }\n                             \n                     cost[i] = x;\n\n                }\n                 \n            }\n            \n        }\n        \n       \n\n       priority_queue< pair<int, int> , vector< pair<int, int> >, greater< pair<int, int> > > pq;\n        \n        int x = (1 << n) - 1;\n        int m = masks.size();\n        \n        vector<int> dis(1 << n, 1e9);\n        \n        pq.push({0, x});\n        \n        dis[x] = 0;\n        \n        \n        while(pq.size())\n        {\n            auto pr = pq.top();\n            pq.pop();\n            \n            int mask = pr.second;\n            int d = pr.first;\n            \n            if(d > dis[mask])\n                continue;\n\n            if(mask == 0)\n                return dis[0];\n            \n            for(int i = 0; i < m; i++)\n                if((masks[i] & (mask)) == masks[i])\n                {\n                     if(dis[masks[i] ^ mask] > (d + cost[masks[i]]))\n                     {\n                         dis[masks[i] ^ mask] = d + cost[masks[i]];\n                         pq.push({dis[masks[i] ^ mask], mask ^ masks[i]});\n                     }\n                }\n            \n        \n        }\n        \n        return -1;\n    }\n};\n
[]