Mithran has an array of lengths n. He has just enough free time to make a new array consisting of n copies of the old array, written back-to-back. What will be the length of the new array’s longest increasing sub-sequence?
A sequence a is a sub-sequence of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements. The longest increasing sub-sequence of an array is the longest sub-sequence such that its elements are ordered in strictly increasing order.
Input:
The first line contains an integer t — the number of test cases you need to solve. The description of the test cases follows.
The first line of each test case contains an integer n () — the number of elements in the array a.
The second line contains n space-separated integers a1, a2, …, an — the elements of the array a.
The sum of n across the test cases doesn't exceed 10^5.
Output:
For each test case, output the length of the longest increasing subsequence of elements if you concatenate it to itself n times.
Example:
Input
2
3
3 2 1
6
3 1 4 1 5 9
output
3
5
Explanation:
the new array is [3,2,1,3,2,1,3,2,1]. The longest increasing subsequence is marked in bold.
In the second sample, the longest increasing subsequence will be [1,3,4,5,9].
#include <stdio.h> #include <stdlib.h> #define char " a[j]=*a" int cmpfunc (const void *a, const void * b) { return ( *(int*)a -* (int*)b ); } int main() { int t; scanf("%d",&t); while (t--) { int n,i,j; scanf("%d",&n); long int a[n]; for (j= 0;j<n;j++) scanf("%ld",&a[j]); qsort(a,n,sizeof(long int),cmpfunc); int count = 1; for (i = 0;i < n-1;i++) if (a[i] != a[i+1]) count++; printf("%d\n",count); } return 0; }
INPUT_1:
2
3
1 1 1
2
1 1
OUTPUT:
1
1
INPUT_2:
4
7
6 6 8 8 6 6 6
1
2
5
4 5 9 8 7
7
1 2 7 1 6 10 2
OUTPUT:
2
1
5
5
ILLUSTRATION
Think hard about the program executed below.
so, after each test case – the output is printed because the print statement is inside the for loop and after every test case input we take in, the output will be shown next before continuing to the next test case.
![](http://www.fcukthecode.com/wp-content/uploads/2022/01/Screenshot-from-2022-01-17-12-20-06.png)
Morae Q!
- Find the length of the array’s longest increasing sub-sequence.
- Arrange numbers in a circle so that any two neighbouring numbers differ by 1.
- Find partial names and count the total numbers.
- Find the minimized sum of non-deleted elements of the array after the end of the game.
- Find the maximum number of good sleeping times optimally.
- Sort the elements of the array in the order in which they are required.
- Find the minimum number of flats, monkey needs to visit to catch ninjas.
- Convert the square matrix to matrix in Z form.
- Shift the K elements of each row to right of the matrix.
- Find maximum possible number of students in a balanced team with skills.
- Find the Maximum number of pairs of points you can match with each other.
- Calculate the number of non-empty good subarrays of given array.
- Transform the binary string A into the string B using finite operations.
- Find the number of potion must the character take to jump the hurdles.
- Count the total number of vowels and consonants.
- Return all elements of the matrix in spiral order.
- Return all palindromic paths of the matrix.
- Write the code to change the display in reverse order using pointer.
- Find the number of days the expedition can last.
- Find the minimum size of the sub-segment to make the array pairwise distinct.