O(NlogN) approach | CPP
The problem setters didn\'t come up with good constraints this time.\nWe can solve this problem in NlogN time complexity.\n\nLet us think of this problem as a g
The problem setters didn\'t come up with good constraints this time.\nWe can solve this problem in NlogN time complexity.\n\nLet us think of this problem as a graph problem.\nSuppose there exists an edge between nodes i and nodes j if there absolute difference is k. We can see that we have to take non adjacent nodes from the graph. One special property of this graph is also that the components are a line graph.\n\nHow to find the number of ways to take non adjacent nodes from the graph. Suppose there exists an component of size A, then the number of ways to choose non adjacent nodes from that component is $F(A)$ where $F(i)$ is the i+2\'th fibonacci sum. So for A=1 , we can have 2 valid ways of choosing , for A=2 we have 3 and for A=3 we have 5 valid ways of choosing. To prove this we can think about adding a new node at the end of the current component of size A.\n\n```cpp\nclass Solution {\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        int n=nums.size();\n        \n        sort(nums.begin(),nums.end());\n\n        vector<int> parent(n,1);\n        for(int i=0;i<n;i++)\n            parent[i]=i;\n        \n        unordered_map<int,int> prev;\n        for(int i=0;i<n;i++)\n        {\n            if(prev.find(nums[i]-k)!=prev.end())\n                parent[i]=parent[ prev[nums[i]-k] ];\n            prev[nums[i]]=i;\n        }\n        \n        map<int,int> mp;\n        for(int i=0;i<n;i++)\n            mp[parent[i]]++;\n        \n        vector<int> fibo(25);\n        fibo[1]=2;\n        fibo[2]=3;\n        for(int i=3;i<=24;i++)\n            fibo[i]=fibo[i-1]+fibo[i-2];\n        \n        int ans=1;\n        for(auto &[rep,len] : mp)\n            ans=ans*(fibo[len]);\n        return ans-1;\n    }\n};
['C++']