You are given an array a of integers with n elements. You are allowed to rearrange the elements of the array in any order. Your task is to determine if it is possible to reorder the array such that for every i from 0 to n-2 (i.e., for all adjacent elements), the absolute difference between consecutive elements is either 5 or 7. That is, for all i such that 0 <= i < n — 1, you need to check if: abs(v[i] — v[i + 1]) = 5 or abs(v[i] — v[i+ 1]) = 7.
What is the expected time complexity?
what are the constraints on a[i]?
I think I solved it. Lets discuss in the dm. But damn this was such a good question. You should have offered it as a problem in a contest. Please ping in dm.
Why dont you post it here so everybody can ser
First let me be sure if my approach is correct or not :)
Yea well I am curious about the solution, share it in my DMs if you are comfortable sharing here i guess? Thanks
i have some solution but i dont know is it correct or not. i am thinking that first sort the array then define the range as l = v[0] and r = v[0] then select the next element and insert the element on either side of range and then update thhe range.
And how will you determine which side of the range to insert it on?
ignore plz
Just writing whatever comes into my faulty memory at this point, but I think I faced a similar problem in an OA once and later found out that such problems are solved my building a graph out of it and determining the maximum flow or something similar on that line, I am not educated on the algorithm yet.
I dont believe theres a simpler solution but I'd be happy if someone figures it out.
I tried it out and initially thought it would work, bu then found myself a testcase where it would fail
The approach was like store all the elements in a multiset, and choose an elenment that is smallest and then find its neighbouring elements, that are either situated at a distance of +5 or +7. If you find it, put it adjacent to that element and erase them from the multiset and continue till the multiset is empty.
Ex: let us take a simpler testcase. {3 5 8 10}, smallest is 3 so now answer looks like
...3...
search for possible adjacent elements, ie 8 and 10, we find here both, so the array looks like
...8 3 10... now for 8, neighbours could be 3,13,15, we find none.
So search for neighbours of 10 we find 5. so the array now is 8 3 10 5, and our multiset is now empty.
But this fails miserably on a testcase like {10 3 10 17 22 15 8} Here, comes the problem, the neighbours could be 8 3 10 or 10 3 10
Unfortunately, if we take neighbours to be 8 3 10, we cant always empty the multiset.
for this, if you take 8 3 10 15 22, you are stuck, now no edge element have corresponding neighbour in set :(
Well again, I am sorry but that is a wrong greedy.
I realised :(
If you construct a graph such that there exists an edge $$$(u,v)$$$ if and only if $$$|a_u - a_v| = 5$$$ or $$$|a_u - a_v| = 7$$$, then the problem is a Hamiltonian Path Problem, and cannot be solved in poly time.
I bet this problem cannot be solved better than $$$\mathcal O(2^n \text{poly}(n))$$$.
Right, this problem is indeed NP-Complete.
This is a clever observation. Well done !