Out of the box and easy to understand solution
The problem asks us to generate an array of size \'n\' where the number of distinct absolute difference of adjacent elements are \'k\'. The problem can be solve
The problem asks us to generate an array of size \'n\' where the number of distinct absolute difference of adjacent elements are \'k\'. The problem can be solved by making a set of solutions and then observing the pattern within that solution.\n\n**For example,**\nLets take ```n=5 and k=1```\nOne of the possible solution is: ``1, 2, 3, 4, 5``\n\n**Now lets consider n=5 and k=2**\n\nWe can see that if we adjust the first 3 elements such that we get 2 different abolute differences, we would be left with only remaining n-3 elements and we can arrange them in any order keeping in mind the difference is either of the value which we got from the first 2 elements.\n\nLets take the absolute difference as , ```+2,-1. (Dont worry the sign is just for explanation)```\n- So, lets put 1 as the first number of array.\n- The next number would be **1 + 2 = 3**\n- The third number would be **3 - 1 = 2**\n\nSince we are done with the first 3 elements we can simply store the remaining n-3 elements, in sorted order. Thus assuring that the abolute difference of adjacent elements remain 1 whereas the difference between the 3rd element(i.e. 2) and its next element(i.e. 4) remains 2 thus it doesn\'t violate our condition. Hence the sequence becomes: 1, 3, 2, 4, 5\n\n**Now lets consider n=5 and k=3**\n\nWe can again make a pattern **```+3, -2, +1```**\nOnce again put 1 as the first element of the answer vector. Followed by 1 + 3 = 4, followed by 4 - 2 = 2, followed by 2 + 1 = 3.\nThen we store the remaining elements that are nothing but from k+2 to n.\nHence the resultant array would be: 1, 4, 2, 3, 5\n\n**Now a DIY**\n\nTry to solve for n=9, k=4.\n\n**Hint - The pattern would be: +4, -3, +2, -1**\n\nThe elements will be 1, (1+4=)5, (5-3=)2, (2+2=)4, (4-1=)3, (remaining number from [k+2 till n]), 6, 7, 8, 9\nHence the resultant sequence would be: ```1, 5, 2, 4, 3, 6, 7, 8, 9``` \n\n- - - - -\n```\nclass Solution {\npublic:\n    vector<int> constructArray(int n, int k) {\n        vector<int> pre;\n        int f=1;\n        int temp=k;\n        while(k)\n        {\n            pre.push_back(k);\n            k = abs(k)-1;\n            if(f)\n            {\n                k*=-1;\n            }\n            f^=1;\n        }\n        vector<int> ans;\n        ans.push_back(1);\n        for(int i=0;i<temp;i++)\n        {\n            int ele = ans[i]+pre[i];\n            ans.push_back(ele);\n        }\n        for(int i=temp+2;i<=n;i++)\n        {\n            ans.push_back(i);\n        }\n        return ans;\n    }\n};\n```\n\nDo upvote and put your queries(if any) below.
['Greedy', 'C']