Min Subsets with Consecutive Numbers

QUESTION

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.\n\nInput:\n\nThe 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 seperated integers of the array. \nOutput:\n\nFor each test case output a new line denoting count of number of such subset’s that contains consecutive numbers.\nConstraints:\n\n1<=T<=100\n1<=N<=50.

“TESTCASE_1”: “2\n11\n100 56 5 6 102 58 101 57 7 103 5\n3\n10 100 105\n###—###SEPERATOR—###—\n4\n3”, “TESTCASE_2”: “5\n12\n12 23 85 11 65 22 87 24 10 86 64 63\n5\n1 5 3 2 6\n7\n6 8 1 7 2 5 4\n10\n45 21 74 44 72 20 4 73 5 46\n8\n4 2 9 5 3 7 8 1 \n###—###SEPERATOR—###—\n4\n2\n2\n4\n2”, “TESTCASE_3”: “1\n20\n6 8 1 4 9 25 64 23 24 65 11 10 47 21 67 66 25 5 33 48\n###—###SEPERATOR—###—\n9”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

import java.io.*;
import java.util.*;
class TestClass {
 
    // Returns count of subsets with consecutive numbers
    static int numofsubset(int arr[], int n)
    {
        
        Arrays.sort(arr);
         
        // Initialize result
        int count = 1;
        for (int i = 0; i < n-1; i++)
        {
           
            if (arr[i] + 1 != arr[i+1])
                count++;
        }
     
        return count;
    }
     
    // Driven Program
    public static void main(String[] args)
    {
      Scanner sc=new Scanner(System.in);
      int t=sc.nextInt();
      while(t!=0)
      {
        int n=sc.nextInt();
        int arr[]=new int[n];
        for(int i=0;i<n;i++)
          arr[i]=sc.nextInt();
        System.out.println(numofsubset(arr,n));
        t--;
      }
    }
}
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.