Nikhita
BAN USER- 0of 0 votes
AnswersInput:
- Nikhita in India
3
3 1 2
nny
nnn
ynn
output:
2 1 3
n size of permutation P.First line of input is n.Second line is the permutation P.A Permutation X is said to be lexicographically smaller than Y if for all digits till i X[i]=Y[i] and for i+1 X[i]<=Y[i]so you can exchange the integers in the given permutation P if character j of line i+2 is 'y' then i th and j th integer in P can be exchanged .
Output:Lexicographically smallest premutation of the given P using rule| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Coding
This solution is by using the adjacency matrix.
if a[0][1]==1 and a[1][2]==1 then we check if a[0][2]==1 then one triangle exists
We scan the matrix just downwards in the upper half of the marix
for example if we have 5 nodes then
scan starts from 0th node from a[0][1] and check starts from a[1][2]
And then 1st node from a[1][2] and compared with next node from a[2][3] and so on
In this way we avoid making duplicates
#include<iostream>
using namespace std;
int main()
{
int n,i,j,k,entries,no=0;
cout<<"enter no of nodes:\n";
cin>>n;
int a[n][n];
cout<<"enter no of entries:\n";
cin>>entries;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
a[i][j]=0;
}
for(i=0;i<entries;i++)
{
cin>>j>>k;
a[j][k]=1;
a[k][j]=1;
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i][j]==1)
{
for(k=j+1;k<n;k++)
{
if(a[j][k]==1)
{
if(a[i][k]==1)
no++;
}
}
}
}
}
cout<<"no of triangles="<<no<<endl;
return 0;
}
Since the rule matrix is symmetric and the diagonal elements are 'n' all the time since [1][1]=n that means first digit cannot be exchanged with the first one,which doesn't permute the P.
so in your test case
[1][2]=y so first digit can be exchanged with the second one
so we get by applying rule
2 3 1
[1][3]=n so first digit cannot be exchanged with the third one
then we can directly consider
[2][3]=y so second digit can be exchanged with the third one
so we get
3 1 2
so between 3 2 1 (input ) and two obtained permutations 2 3 1 and 3 1 2 smaller is 2 3 1
Output:
2 3 1
1. We scan the no from the Least significant digit and store it
- Nikhita April 08, 20142. The scan continues unitl we find a digit lesser than the previous digit
3. If the order is in ascending from least significant digit to the most then return the same number
4. Else the found digit is swapped with the least significant digit and the rest digits are sorted in ascending order and the final number is made
#include<iostream>
#include<math.h>
//#include<algorithm>
using namespace std;
int get_length(int n)
{
int temp=0;
while(n)
{
n=n/10;
temp++;
}
cout<<"in get_length ="<<temp<<endl;
return temp;
}
void sortRest(int arr[],int i)
{
int j,k,temp;
for(j=0;j<=i-1;j++)
{
for(k=j+1;k<=i;k++)
{
if(arr[j]>arr[k])
{
temp=arr[k];
arr[k]=arr[j];
arr[j]=temp;
}
}
}
cout<<"after sorting\n";
for(j=0;j<=i;j++)
cout<<arr[j];
cout<<endl;
}
double swap(int arr[], int i, double n)
{
int j=i;
//int temp = arr[0];
//arr[0] = arr[i];
//arr[i]= temp;
cout<<"0,i= "<<arr[0]<<arr[i]<<endl;
sortRest(arr+1, i-1);
cout<<"0,i= "<<arr[0]<<arr[i]<<endl;
while(j>=0)
{ cout<<"in swap n="<<n<<" i="<<i<<endl;
n=n*10+arr[i-j];
j--;
}
return n;
}
int main()
{
int n,num,len,i=0,ans=-1;
cout<<"enter n\n";
cin>>n;num=n;
len=get_length(n);
int arr[len];
while(n)
{
arr[i]=n%10;cout<<"arr["<<i<<"]="<<arr[i]<<endl;
n=n/10;cout<<"n="<<n<<endl;
if(i!=0)
{
if(arr[i]<arr[i-1])
{
ans=swap(arr, i, n);
break;
}
}
i++;
}
if(ans!=-1)
cout<<ans<<endl;
else
cout<<num<<endl;
return ans;
}