Question definition:
Given an array connected end to end(circular fashion). Find if thee is any arrangement of the array elements such that the absolute diff of adjacent elements is always one.

Need help to solve not able to approach it.

Could you specify what kind of complexity you need?
O(N) or O(N^2) ?

Sort the array and check if it equals to a sequence of consecutive integers
This should work in  O (n log n)  time.

But what if the problem needs to have adjacent difference exactlty equal to one. It won’t always work.

Hi @aviral311 as @vishaaaal said it won’t work since the elements are connected circularly.

Nope i don’t think that will work
For example take the case
2 3 2 3
According to problem statement this is a yes
but according to your logic this is a no

I think we can create a graph. First we connect all nodes that have value with absolute difference 1 this should be O(N^2)
Then we find the articulation points. If there are no articulation points then the answer is yes otherwise no. Again complexity is O(N^2).

Why do you find articulation points?

I mean if you create a graph with an edge between two nodes i and j if abs(a[i]-a[j])=1, then you will need to find a Hamiltonian Cycle in this graph.

Yes got it.

We don’t need to “find” a Hamiltonian cycle. we just need to check if there is a Hamiltonian cycle. And i think that 0 Articulation point means there is a Hamiltonian Cycle.
So we just run a dfs and find the low link values. If at any point we find an AP we terminate.

If you just need to check for any arrangement, then it would be fine.

I think I read the problem as “find an arrangement”, that’s why I said that we’ll need to “find” a Hamiltonian Cycle.

Then I think it solves the problem in O(n^2), @vraj1994 .

1 Like

I was thinking about the solution for this problem in my sleep and came up with an idea. Currently, it fails for some test cases. Some sort of corrections should (probably) fix my approach, viz:

• Sort the given array arr. The following steps are applicable to the sorted array.
• let freq[i] denote the frequency of element i in arr.
• Handle the base case, where, after sorting, arr[i] < (arr[i + 1] - 1) for any 1\le i \lt N implies NOT POSSIBLE case.
• Now, for the first and last elements of arr:
• If freq[first] > freq[first + 1] or freq[last] > freq[last - 1], then there is no possibility (think why).
• For elements other than first and last, we can observe that if freq[element] > freq[element - 1] + freq[element + 1], there is no such arrangement.
• It fails for some other test cases though.

Anyways, if anyone is working on this approach, I am attaching the scripts here.

Bruteforce that is guaranteed to pass, but slow
#include <bits/stdc++.h>

using namespace std;

#define FOR(x, N)					for(int x = 0; x < N; x++)

typedef unsigned long long int ull;
typedef long long int ll;

bool is_valid(vector<int>& a) {
const int N = a.size();
for(int i = 0; i < N; i++) {
if(abs(a[i] - a[(i + 1) % N]) != 1) {
return false;
}
}
return true;
}

void solve() {
int N = 0;
cin >> N;
vector<int> A(N);
FOR(i, N) cin >> A[i];
bool flag = false;
do {
if(is_valid(A)) {
flag = true;
break;
}
} while(next_permutation(A.begin(), A.end()));
cout << (flag ? 1 : 0) << '\n';
}

int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t = 0;
// t++;
if(!t) cin >> t;
FOR(test, t) {
// cout << "Case #" << (test + 1) << ": ";
solve();
}
return 0;
}

Generator I am using
#include <bits/stdc++.h>
using namespace std;

#define TEST 10
#define TEST_CASES true

int randint(int a, int b) {
return a + rand() % (b + 1 - a);
}

void generate() {
int n = randint(2, 10);
printf("%d\n", n);
for(int i = 0; i < n; i++) {
printf("%d ", randint(1, 10));
}
printf("\n");
}

int main(int argc, char* argv[]) {
srand(atoi(argv[1]));
int test_cases = randint(1, TEST);
if(TEST_CASES) {
printf("%d\n", test_cases);
}
for(int test = 0; test < test_cases; test++) {
generate();
}
return 0;
}


Ignore the following if the approach was clear.

(Contains template) My Approach, that fails for some test cases
/*
Author: Chitturi Sai Suman
Created: 2021-11-18 06:12:47
Contest: Codechef
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define FOR(x, N)					for(int x = 0; x < N; x++)
#define inverse(a, p)				power(a, p - 2, p)

typedef unsigned long long int ull;
typedef long long int ll;

const short int dc[] = {1, 0, 0, -1, -1, -1, 1, 1};
const short int dr[] = {0, 1, -1, 0, -1, 1, -1, 1};

const ll shit	= ((ll)(998244353));
const ll mod	= ((ll)(1e9 + 7));
const ll hell	= ((ll)(1e9 + 9));
const ll inf	= ((ll)(1e18 + 3));

static inline ll gcd(ll a, ll b) {
for(ll rem = 0; b > 0; rem = a % b, a = b, b = rem);
return a;
}
static inline ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}

#define nax 2000003

void pre_compute() {
return;
}

void solve() {
int N = 0;
cin >> N;
vector<int> a(N);
FOR(i, N) cin >> a[i];
sort(a.begin(), a.end());
map<int, int> freq;
FOR(i, N) freq[a[i]]++;
set<int> my_set(a.begin(), a.end());
for(int i = 0; i < N - 1; i++) {
if(abs(a[i] - a[i + 1]) > 1) {
cout << "0" << '\n';
return;
}
}
bool flag = true;
for(int i: my_set) {
if(i == a[0]) {
if(freq[i] != freq[i + 1]) {
flag = false;
break;
}
}
else if(i == a[N - 1]) {
if(freq[i] != freq[i - 1]) {
flag = false;
break;
}
}
else {
if(freq[i] != max(freq[i - 1], freq[i + 1])) {
if(freq[i] < freq[i + 1] + freq[i - 1]) {
flag = false;
break;
}
}
}
}
if(my_set.size() == 3) {
flag = true;
vector<int> b(my_set.begin(), my_set.end());
sort(b.begin(), b.end());
if(freq[b[1]] != freq[b[0]] + freq[b[2]]) {
flag = false;
}
}
if(flag) {
bool have_same = true;
for(int i = 0; i < N; i++) {
if(freq[a[i]] != 1) {
have_same = false;
break;
}
}
// cerr << "have_same: " << have_same << '\n';
if(!have_same) {
cout << "1" << '\n';
return;
}
cout << (a[0] == a[N - 1] - 1 ? "1" : "0") << '\n';
return;
}
cout << "0" << '\n';
}

int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t = 0;
// t++;
if(!t) cin >> t;
pre_compute();
FOR(test, t) {
// cout << "Case #" << (test + 1) << ": ";
solve();
}
return 0;
}

1 Like

Hi can u explain the approach with the below array
0,1,1,1,2,2,0,-1

The nodes and values
0:0
1:1
2:1
3:1
4:2
5:2
6:0
7:-1

0: 1,2,3,7
1:0,4,5,6
2:0,4,5,6
3:0,4,5,6
4:1,2,3
5:1,2,3
6:1,2,3,7
7:0,6

Note it is an undirected graph which may/may not contain cycles.

DFS order
0 1 4 2 5 3 6 7
low link value for all roots is zero (there is an edge from 7 to 0) thus we get a Hamiltonian cycle.
Basically that’s all we need to check. Lowlink value for everything should be zero.

Actually the point about first and last element of array

Should be
freq[first] >= freq[first + 1] or freq[last] >= freq[last - 1], then there is no possibility (think why).

Here also there is greater than equal to sign.

Apart from the two changes i suggested above your solution is brilliant and O(N)
But can you prove that If the all your conditions are false then a Hamiltonian Path definitely exists?

No, you got it wrong. Here’s an example.

[1, 1, 2, 2] \rightarrow [1, 2, 1, 2]. Even if freq[1] == freq[2], you are able to construct valid array. So, we will not get desired output if we check for the condition (freq[first] >= freq[first + 1]). It should be (freq[first] > freq[first + 1]). Similarly, for the last element (freq[last] > freq[last - 1]).

Thanks, but I don’t think it is O(N), it is at least O(N\log{N}) since we should definitely sort the array. I don’t have any proof for this, this is just a Vague idea I could come up with in my sleep .

@cubefreak777 is always there to help.

1 Like

Oh yes I never thought of that.