Menu Close

Length of the new array’s longest increasing sub-sequence…[Cprgm]FTC

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 an 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.

EXecuted using gcc