Posts

Search

N 501 - Trick or Treat!

Halloween is around and Ted Mosby ( who loves kids ) wants to give away candies. Ted has N bags of candies, each bag has Candies equal to A[i] stored in an array A[N]. There are M kids and each kid wants a specific amount of candy C[i] stored in an array C[M].

For every kid i, you are to print "Happy Halloween!" if C[i] is present in the array A[N]. If C[i] is not present in the array, print "Tricky!".

Hint1 : You can use binary search to find out whether an element is present in the array or not.

INPUT

First line contains the number N(1 <= N <= 10^5), size of array A[N]. Second line contains N space separated integers, denoting the elements of the array A. (1 <= A[i] <= 10^9) Third line contains the number M(1 <= M <= 10^5), size of array C[M]. Fourth line contains M space separated integers, denoting the elements of the array C. (1 <= C[i] <= 10^9)

OUTPUT

Print M lines of output. ith line being "Happy Halloween!" if C[i] is present in A[N] and "Tricky!" otherwise.

Sample Input 0

5
2 4 6 8 10
5
5 4 3 2 1

Sample Output 0

Tricky!
Happy Halloween!
Tricky!
Happy Halloween!
Tricky!


Solution:

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

public class Solution {
     public static int binarySearch(int arr[], int first, int last, int key){  
   int mid = (first + last)/2;  
   while( first <= last ){  
      if ( arr[mid] < key ){  
        first = mid + 1;     
      }else if ( arr[mid] == key )
      {  
          return 1;
      }else{  
         last = mid - 1;  
      }  
      mid = (first + last)/2;  
   }  
   if ( first > last ){  
       return 0;
        }
         return -1;
 }  

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
         Scanner sc=new Scanner(System.in);
        int a= sc.nextInt();
        int ar[] = new int[a];
         for(int i=0;i<a;i++)
        {
             ar[i]= sc.nextInt();
         }
        int b= sc.nextInt();
        int ar1[] = new int[b];
         for(int i=0;i<a;i++)
        {
             ar1[i]= sc.nextInt();
         }
        for(int i=0;i<b;i++)
        {
            int temp = ar1[i];
            int flag = binarySearch(ar,0,a-1,temp);  
            if(flag==1)
            {
                System.out.println("Happy Halloween!");
                
            }
            else 
            {
                System.out.println("Tricky!");
            }
        }
    }
}
Posted by