Def:
You had an array of integer numbers. You also had a beautiful operations called "Copy-Paste" which allowed you to copy any contiguous sub-sequence of your array and paste it in any position of your array. For example, if you have array [1, 2, 3, 4, 5] and copy it's sub-sequence from the second to the fourth element and paste it after the third one, then you will get [1, 2, 3, 2, 3, 4, 4, 5] array. You remember that you have done a finite(probably zero) number of such operations over your initial array and got an array A as a result. Unfortunately you don't remember the initial array itself, so you would like to know what could it be. You are interested by the smallest such array. So the task is to find the minimal size(length) of the array that A can be obtained from by using "Copy-Paste" operations.
PS : This is CodeChef's problem
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of elements in obtained array A. The second line contains N space-separated integers A1, A2, ..., AN denoting the array.
Example :
5 , 1 1 1 1 1
5 , 1 2 3 1 2
Output:
1
3
Explanation :
What we want here is to get exactly the count of unique number.
One way is to do with Two loops, for each number check whole string.
Second way is to create hash for each individual number and keep count.
Third and simple way is to keep a hash kind of array, for each single occurrence of a number w'll just mark it True. and keep the counter.
Thanks to Dhaval for suggesting this approach and Code
Code :
You can find it working at http://ideone.com/e.js/xuHuWk
You had an array of integer numbers. You also had a beautiful operations called "Copy-Paste" which allowed you to copy any contiguous sub-sequence of your array and paste it in any position of your array. For example, if you have array [1, 2, 3, 4, 5] and copy it's sub-sequence from the second to the fourth element and paste it after the third one, then you will get [1, 2, 3, 2, 3, 4, 4, 5] array. You remember that you have done a finite(probably zero) number of such operations over your initial array and got an array A as a result. Unfortunately you don't remember the initial array itself, so you would like to know what could it be. You are interested by the smallest such array. So the task is to find the minimal size(length) of the array that A can be obtained from by using "Copy-Paste" operations.
PS : This is CodeChef's problem
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of elements in obtained array A. The second line contains N space-separated integers A1, A2, ..., AN denoting the array.
Example :
5 , 1 1 1 1 1
5 , 1 2 3 1 2
Output:
1
3
Explanation :
What we want here is to get exactly the count of unique number.
One way is to do with Two loops, for each number check whole string.
Second way is to create hash for each individual number and keep count.
Third and simple way is to keep a hash kind of array, for each single occurrence of a number w'll just mark it True. and keep the counter.
Thanks to Dhaval for suggesting this approach and Code
Code :
#include <stdio.h>
#include <stdbool.h>
int rrcopy(int n, int a[]){
int i=0,ans=0;
bool c[100001]={0}; ans=0;
for(i=0;i<n;i++){
if(!c[a[i]]) {c[a[i]]=1;ans++; }
}
return ans;
}
int main(void) {
int n;
//int a[]={1,1,1}; //op 1
int a[]={1,2,3,2,3,4,4,5}; //op 5
//int a[]={1,2,3,2,3,5}; // op 4
n=sizeof(a)/sizeof(int);
int l=rrcopy(n,a);
printf("min length %d",l);
return l;
}
You can find it working at http://ideone.com/e.js/xuHuWk
