CODEWITHSUNDEEP
arraysalgorithm
Jytug
Jytug

Reputation: 1116

Two identical subsequences

I'm trying to find an effective algorithm (a function) that takes an array of integers A[1..2N] and returns true if the sequence represented in A can be divided into two identical subsequences of length N - and false otherwise.

I don't really know where to start. I was thinking of recursion - such sequences have to begin with A[1] and end with A[2N], but the next step isn't so obvious.

I would appreciate some help

Upvotes: 0

Views: 125

Answers (2)

Jytug
Jytug

Reputation: 1116

Probably it's not the perfect code yet, but the idea is this pseudo-code

function sameSubsequences(A:array[1..2n] of integer):boolean;

begin
memory:array[1..2n] of boolean; 
for i:=1 to 2n do memory[i]:=false;
i:=1; j:=2;
while i<=2n AND j<=2n do
    begin
    memory[i]:=true;
    while j<=2n and A[j]!=A[i] and (not memory[j]) do j:=j+1;
    if j<=2n then memory[j]:=true;
    while i<=2n or memory[i] do i:=i+1;
    end;

sameSubsequences:=(i>2n);
end;

Upvotes: 0

Shahriar
Shahriar

Reputation: 13804

Function CHECK() will do your duty if you are really expecting this..

Hope it will help

int A[]={1,2,1,3,4,2,3,4};
int vis[10];

bool CHECK()
{
    vis[10]={0};
    int j=1;

    for(int i=0; i<10; i++)
    {
        if(vis[i]==1) continue;
        bool find = false;

        for(; j<10; j++)
        {
            if(A[i]==A[j])
            {
                find=true;
                vis[i]=1;
                vis[j]=1;
                j++;
                break;
            }
        }
       if(!find)
       {
           return false;
       }
   }
   return true;
}

Upvotes: 1

Related Questions