HackerEarth Testing Strings problem solution

In this HackerEarth Testing Strings problem solution Mr X and Mr Y, his friend are programmers and testers respectively working in the same company. So, once they faced the following scenario :

Mr X wrote an application that took as input some user data. The data the application took as input was a string in some strange language. That language consisted of K distinct letters. However, due to some issues, the application got corrupted and one particular String among many was lost.

However, Mr X had seen that String once before it got lost. He remembers some info about it. Particu-larly, he remembers the lost String had length equal to M.

Mr Y, being the chief QA person in his company needs to try and figure out the number of possible different possible candidate Strings for the lost String.

Mr X remembers N pieces of info. For each one, he gives you 2 numbers L and R and a number Z. He remembers for sure that the Zth letter of the language of the string did not occur between positions L and R inclusive of the lost String.

HackerEarth Testing Strings problem solution.

import java.io.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class testing_strings
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
    static Random rnd=new Random();
    static long mod=(long)(1e6+3);
    static ArrayList<Pair>[] al;
    
    @SuppressWarnings("unchecked")
    public static void main(String args[]) throws Exception
    {
        int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt();
        
        char[] a=new char[m];al=new ArrayList[m];
        
        for(int i=0;i<m;i++)
        {
            al[i]=new ArrayList<>();
        }
        
        for(int i=0;i<n;i++)
        {
            int l=sc.nextInt()-1,r=sc.nextInt()-1,x=sc.nextInt()-1;
            
            al[l].add(new Pair(1,x));
            
            if(r+1<m)
            {
                al[r+1].add(new Pair(-1,x));
            }
        }
        
        int[] sum=new int[k];long res=1;long ctr=k;
        
        for(int i=0;i<m;i++)
        {
            for(Pair x:al[i])
            {
                sum[x.val]+=x.add;
                
                if(sum[x.val]==1)
                {
                    ctr--;
                }
                
                if(sum[x.val]==0)
                {
                    ctr++;
                }
            }
            
            res=(res*ctr)%mod;
        }
        
        out.println(res);out.close();
    }
    
    private static class Pair
    {
        int add,val;
        
        public Pair(int add,int val)
        {
            this.add=add;this.val=val;
        }
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
    
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
    
    public String next() throws Exception {
        return nextToken().toString();
    }
    
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}

HackerEarth Testing Strings problem solution

HackerEarth Testing Strings problem solution.

Leave a Reply

Pages

Practice