0

I am running this in Dev C++ it is giving me Id returned 1 exit status. What did i do wrong here?

A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Let p be any permutation of length n. We define the fingerprint F(p) of p as the sorted array of sums of adjacent elements in p. More formally,

F(p)=sort([p1+p2,p2+p3,…,pn−1+pn]). For example, if n=4 and p=[1,4,2,3], then the fingerprint is given by F(p)=sort([1+4,4+2,2+3])=sort([5,6,5])=[5,5,6].

You are given a permutation p of length n. Your task is to find a different permutation p′ with the same fingerprint. Two permutations p and p′ are considered different if there is some index i such that pi≠p′i.

#include <bits/stdc++.h>
using namespace std;
int* fingerprint(int p[],int n)
{
    int fp[n-1];
    for(int i=0;i<n-1;i++)
    {
        fp[i]=p[i]+p[i+1];
    }
    sort(fp,fp+n-1);

    return fp;
}
void display(int p[],int n)
{
    for(int i=0;i<n;i++)
        cout<<p[i]<<" ";
    cout<<endl;
}
void equality(int p[],int* fp,int n)
{
    int* fp1=fingerprint(p,n);
    int c=0;
    for(int i=0;i<n-1;i++)
    {
        if(fp[i]!=fp1[i])
            c=1;
    }
    if(c==0)
        display(p,n);
}
void findpermutations(int p[],int n)
{
    int* fp=fingerprint(p,n);
    sort(p,p+n);
    do{
        equality(p,fp,n);
    }while(next_permutation(p,p+n));
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int p[n];
        for(int i=0;i<n;i++)
        {
            cin>>p[i];

        }

        findpermutations(p,n);
    }
    return 0;
}

Input:

3

2

1 2

6

2 1 6 5 4 3

5

2 4 3 1 5

Output:

2 1

1 2 5 6 3 4

3 1 5 2 4

Suman Chatterjee
  • 1
  • 3
  • 1
    I strongly recommend using `vector` instead of arrays. Besides `cin >> n; int p[n]` is not valid c++. – cigien Sep 06 '20 at 17:10
  • [You should never use #include ](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). – rsjaffe Sep 06 '20 at 17:14
  • 1
    `int fp[n-1]; ... return fp;` --> `fp` will be deleted when the function exits. Therefore, you are returning a pointer to a memory location that does not hold anything meaningful. Using `vector`s as cigien suggested is one way around that problem. – Nico Schertler Sep 06 '20 at 17:26

1 Answers1

1

What I see is a mix between C and C++, if we used vectors instead of pointers (because why not) it would look like this:

vector<int> fingerprint(int p[],int n)
{
    vector<int> fp;
    fp.resize(n-1);
    for(int i=0;i<n-1;i++)
    {
        fp[i]=p[i]+p[i+1];
    }
    sort(fp.begin(),fp.end());
    return fp;
}
void equality(int p[],vector<int> fp,int n)
{
    vector<int> fp1=fingerprint(p,n);
    int c=0;
    for(int i=0;i<n-1;i++)
    {
        if(fp[i]!=fp1[i])
            c=1;
    }
    if(c==0)
        display(p,n);
}
void findpermutations(int p[],int n)
{
    vector<int>fp = fingerprint(p,n); //n-1
    sort(fp.begin(),fp.end());
    do{
        equality(p,fp,n);
    }while(next_permutation(p,p+n));
}
aliberro
  • 530
  • 2
  • 9