OVGDEL - Good Elements Editorial or Solution SPOJ - UCS - Unleash-Coding-Skills

## OVGDEL - Good Elements

The link for the problem OVGDEL - Good Elements is:

Note:

In the given problem it is given as aj=aik and  k>=0. and i≠j.

So consider the following test case:
If there are 6 elements in the sequence as an example like:

Example 1:
1 2 4 5 3 5

Output for the above example-1 testcase will be: 5

Suppose consider another example of 6 elements:
Example 2:
1 1 2 5 3 5

The output for the above example-2 is : 6

Explanation for example 1:

Since the condition is aj=aik  and  k>=0. and i≠j.

So for 1 there is no combination available like aj=aik

For 2 => 2 power (0) or 2^0 = 1

Similarly for 4 , 5 ,3 ,5 also powers of 0 are same like x power 0 =1

Here x is anything or anynumber.

So for this example the output is 'n-1' where 'n' no of elements in the given sequence.

Example 2:

The example 2 output is also like example-1 but one exception for '1' since the rule is:

aj=aik and k>=0. and i≠j.

So the index of 1st '1' is zero and the index of 2nd '1' is '1'

So the condition i≠j is valid now.

1 power (0) or 1^0 =1 which is another one available in the sequence so the output is 'n'. where 'n' is number of elements in given input.

Terminology used while designing my solution:

I have filled the array of character with 3 different letter and my index value of the array is considered as the value given by the sequence elements.

'f' : Represent the corresponding index of array is not present in the sequence.'t' : Represent the corresponding index of array is present once.'m' : Represent the corresponding index of array is present more than once.

Variables used in code:

count -> output is stored i.e. no of good elements.

onescount -> no of ones in given sequence.

Be carefull will printing the output format

The CPP solution for the problem OVGDEL - Good Elements :

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
char a;
long long int i,j,k,t,n,count,p,maxi,onescount;
//taking no of test cases input
cin>>t;
for(int ii=1;ii<=t;ii++)
{
memset(a,'f',sizeof(a));
count=0;
onescount =0;
maxi =0;
cin>>n;
for(i=0;i<n;i++)
{
cin>>p;
if(p==1){
onescount++;
}
if(p>maxi)
maxi = p;
if(a[p]=='f')
a[p]='t';
else{
//I have adding to count if is more than one.
//suppose there are 4 twos in sequence I have added 3 to count and remaining 1 in 4  is added //later  in logic
a[p]='m';
count++;
}
}
//if there is atleast one 1 in sequence case and in else block more than 1 one case
if(onescount==1)
{
cout<<"Case "<<ii<<": "<< n-1<<endl;
continue;
}
else if(onescount>1)
{
cout<<"Case "<<ii<<": "<< n<<endl;
continue;
}
//we have said that extra 1 will be adding count here incase of 'm'
for(i=2;i<=maxi;i++)
{
if(a[i]=='m')
count++;
}
//only  counting upto square root of maximum element in sequence is enough
for(i=2;i<=sqrt(maxi);i++)
{
if(a[i]=='t'){
long long r = i;
r=r*i;
while(r<=maxi)
{
if(a[r]=='m'||a[r]=='t')
{
//if I found element like a power(k) I will increment count and break
count++;

break;
}
r=r*i;
}
}
}
cout<<"Case "<<ii<<": "<< count<<endl;
}
return 0;
}

Happy Coding........

Tags:

OVGDEL , OVGDEL - Good Elements Editorial ,OVGDEL - Good Elements solution,
OVGDEL - Good Elements answer ,OVGDEL - Good Elements Editorial  SPOJ , SPOJ, ovgdel,
ovgdel good elements editorial spoj

1. 1. 