Question Name:Min Subsets with Consecutive Numbers

#include<math.h>
#include<string.h>
#include<stdio.h>

int main()
{
	int i,n,m,j,k,l,o,p;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
	    scanf("%d",&p);
	    int a[p];
	    for(j=0;j<p;j++)
	    {
	        scanf("%d",&a[j]);
	    }
	    int I,J,key;
	    for(I=1;I<p;I++)
	    {
	        key=a[I];
	        J=I-1;
	        while(J>=0 && a[J]>key)
	        {
	            a[J+1]=a[J];
	            J=J-1;
	        }
	        a[J+1]=key;
	    }
	    int T = 0;
	    for(j=0;j<p-1;j++)
	    {
	        if(a[j]+1!=a[j+1])
	        {
	            T++;
	        }
	    }
	    T++;
	    printf("%d\n",T);
	}
  return 0;
}

Problem Description

Given an array of distinct positive numbers, the task is to calculate the minimum number of subsets (or subsequences) from the array such that each subset contains consecutive numbers.

Input:

The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains an integer N, denoting the length of the array. Next line contains N space separated integers of the array.
Output:

For each test case output a new line denoting count of number of such subset’s that contains consecutive numbers.
Constraints:

1<=T<=100
1<=N<=50

  • Test Case 1

    Input (stdin)

    2
    11
    100 56 5 6 102 58 101 57 7 103 5
    3
    10 10 105
    

    Expected Output

    4
    3
  • Test Case 2

    Input (stdin)

    2
    4
    58 101 57 10
    2
    10 15
    

    Expected Output

    3
    2

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.