Compress the List Codechef Solution

You are given a strictly increasing sequence of integers A1,A2,…,ANA1,A2,…,AN. Your task is to compress this sequence.

The compressed form of this sequence is a sequence of ranges separated by commas (characters ‘,’). A range is either an integer or a pair of integers separated by three dots (the string "..."). When each range a...b in the compressed form is decompressed into the subsequence (a,a+1,…,b)(a,a+1,…,b), we should obtain the (comma-separated) sequence AA again.

For each maximal contiguous subsequence (a,a+1,…,b)(a,a+1,…,b) of AA such that b≥a+2b≥a+2, the compressed form of AA must contain the range a...b; if b≤a+1b≤a+1, such a sequence should not be compressed into a range. A contiguous subsequence is maximal if it cannot be extended by at least one element of AA next to it. It can be proved that the compressed form of any sequence is unique (i.e. well-defined).

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

Output

For each test case, print a single line containing one string ― the compressed form of the given sequence.

Constraints

  • 1≤T≤1001≤T≤100
  • 1≤N≤1001≤N≤100
  • 1≤Ai≤1,0001≤Ai≤1,000 for each valid ii
  • A1<A2<…<ANA1<A2<…<AN

Sample Input 1 

3
12
1 2 3 5 6 8 9 10 11 12 15 17
4
4 5 7 8
1
4

Sample Output 1 

1...3,5,6,8...12,15,17
4,5,7,8
4

Explanation

Example case 1:

  • (1,2,3)(1,2,3) is a contiguous subsequence with length 33, so it is replaced by the string "1...3"
  • (5,6)(5,6) is a contiguous subsequence, but only with length 22, so it is not compressed into a range
  • (8,9,10,11,12)(8,9,10,11,12) is a contiguous subsequence with length 55, so it is replaced by "8...12"
  • the elements 1515, 1717 are unaffected

Compress the List   – CodeChef Solution in JAVA

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		try {
		    Scanner sc=new Scanner(System.in);
		    int t=sc.nextInt();
		    while(t-->0){
		        int n=sc.nextInt();
		        int arr[]=new int[n];
		        arr[0]=sc.nextInt();
		        String s=""+arr[0];
		        int count=0;
		        for(int i=1;i<n;i++){
		            arr[i]=sc.nextInt();
		            if(arr[i]==arr[i-1]+1){
		                count++;
		            }
		            else{
		                if(count>1){
		                    s+="..."+arr[i-1]+","+arr[i];
		                    count=0;
		                }
		                else if(count==1){
		                    s+=","+arr[i-1]+","+arr[i];
		                    count=0;
		                }
		                else{
		                    s+=","+arr[i];
		                }
		            }
		            
		        }
		        if(count==1){
		            s+=","+arr[n-1];
		        }
		        if(count>1){
		             s+="..."+arr[n-1];
		        }
		        System.out.println(s);
		    }
		    
		} catch(Exception e) {
		} finally {
		}
	}
}

Compress the List – CodeChef Solution in CPP

#include<bits/stdc++.h>

using namespace std;
#define ll long long int 
#define ff first
#define ss second 

void solve(){
    int n; cin>>n;
    int a[n]; for(int i=0;i<n;i++) cin>>a[i];

    string s="";

    int i=0,j=0;

    while(i<=j and j<n-1){

        if(a[j+1]-a[j]==1) j++;

        else{

            if(j-i+1>2){
                s+=to_string(a[i]);
                s+="...";
                i=j;
            }
            else{
                j++;
                while(i!=j){
                    s+=to_string(a[i]);
                    s+=",";
                    i++;
                }
            }

        }
    }

    if(j-i+1>2){
        s+=to_string(a[i]);
        s+="...";
        s+=to_string(a[j]);
        i=j;
    }
    else{
        while(i!=j){
        s+=to_string(a[i]);
        s+=",";
        i++;
    }
        s+=to_string(a[i]);

    }
    
        cout<<s<<endl;

}

int  main(){
    int t; cin>>t;
    while(t--){
        solve();
    }
}

Compress the List  -CodeChef Solution in Python

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    b=[a[0]]
    c=''
    for i in range(1,n):
        if(a[i]==a[i-1]+1):
            b+=[a[i]]
        else:
            if(len(b)==1):
                c+=str(b[0])+','
            elif(len(b)==2):
                c+=str(b[0])+','+str(b[1])+','
            else:
                c+=str(b[0])+'...'+str(b[-1])+','
            b=[a[i]]
    if(len(b)==1):
        c+=str(b[0])+','
    elif(len(b)==2):
        c+=str(b[0])+','+str(b[1])+','
    else:
        c+=str(b[0])+'...'+str(b[-1])+','
    print(c[:-1])

Disclaimer: The above Problem (Compress the List) is generated by CodeChef but the solution is provided by Codeworld19.This tutorial is only for Educational and Learning purpose.

Leave a Reply

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