 # Hack the Interview 6 (Constructing a Tree)

i am able to come up with an algorithm but i have no idea to implement it.
if anyone can give an alogrithm with its implementation ,that would be great.

2 Likes

yeah . its not visible. can u share it in other way.

Sorry…I thought that it’s visible…
I’m pasting my code as I can’t get the other wayy ``````#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--)
{
ll n,x;
cin>>n>>x;
if(n-1>x || x>(n*(n-1))/2)
cout<<-1<<' '<<-1<<'\n';
else
{
ll a[n+1]={0};

ll s=0,i=n,pos=2;
while(s<x)
{
if(i<pos)
{
pos++;
i=n;
}
a[i]++;
s++;
i--;

}
for(int k=1;k<n;k++)
{
for(int u=k+1;u<=n;u++)
{
if(a[u]==a[k]+1)
cout<<k<<' '<<u<<'\n';
else
break;
}
}

}
}
return 0;
}
``````
2 Likes

no problem. thanks for the code ``````#include "bits/stdc++.h"
using namespace std;

int main()
{
long long t;
cin >> t;
while(t--)
{
long long n , x , hi = 0, m;
cin >> n >> x;
if(x>(n*(n-1)/2) || x<(n-1)) cout << "-1 -1\n";
else if(n==1 && x==0) continue;
else
{
while((hi+2)*(hi+1)/2 + (n-hi-2) <= x) hi++;
for(int i = 2 ; i < 2 + hi ; i++) m[i] = i-1 ;
for(int i = 2 + hi ; i < n + 1 ; i++) m[i] = 1;
m[hi+2] = (x - (hi*(hi+1)/2) - (n-1-hi) + 1);
for(int i = 2 ; i < n + 1 ; i++) cout << i << ' ' << m[i] << endl;
}
}
}
``````

Here is one implementation I can think of.

2 Likes

appreciate it.