HackerRank Hackfest-2020

Cyclic Binary String

Problem Statement

Given a binary string of length , you can cyclically shift this string any number of times. For example, consecutively applying cyclic shift operation to the binary string “1011010” you will get “0101101”, “1010110” and so on.

Let X be the decimal representation of string . Find the greatest power of 2 with which X can be divisible with, if it can be divisible with arbitrarily large power print “-1”.

For the result, you are required to print a single integer denoting the maximum power of by which can be divisible with.

For example if string “1001”, we can cyclically shift time to get string “1100” which in decimal is and is divisible with 2² , hence the answer is 2.

Input Format

The first and only line of input contains string s .

Constraints :

1 <= n <= 10⁵

Output Format

Print a single integer denoting the maximum power of 2 by which X can be divisible with .

Solution

Intuition : Count the maximum number of contiguous 0’s that appear after 1.

Case 1 : String contains all zeros

In this case answer is -1

Case 2 : There is only 1 “1” in the String

In this case answer is straightforward length-1 as the string can be shifted to form 1 followed by 0’s.

Case 3 : There are leading and trailing zeros in the String.

in this case we need to count leading and trailing zeros too. So the answer is Max(max_zeros_in_the_string, lead_zeros + trail_zeros)

class Result {

    /*
     * Complete the 'maximumPower' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts STRING s as parameter.
     */

    public static int maximumPower(String s) {
        int lead = 0, trail = 0, curr = 0, max = 0;
        char ch[] = s.toCharArray();
        lead = countLeadingZero(ch);
        trail = countTrailingZero(ch);
        for(char c : ch) {
            if(c == '0') {
                curr++;
                max = Math.max(curr, max);
            }
            else {
                curr = 0;
            }
        }

        if(lead == ch.length) return -1;
        if(lead + trail == ch.length - 1) return ch.length - 1;
        return Math.max(max, lead+trail);
    }

    public static int countLeadingZero(char[] ch) {
        int res = 0; 
        for(char c : ch) {
            if(c == '0')
                res++;
            else 
                return res;
        }
        return res;
    }

    public static int countTrailingZero(char[] ch) {
        int res = 0; 
        for(int i = ch.length - 1; i >= 0; i--) {
            if(ch[i] == '0')
                res++;
            else 
                return res;
        }
        return res;
    }
}

Game of Maximization

Problem Statement

There are n piles of stones, where the n^th pile has  stones. You need to collect the maximum number of stones from these piles, but you must fulfill the following condition:

Let’s say you pick x_i (1 <= i <= n)  stones from the i^th pile, then

• x₁ + x₃ + x₅ + …. = x₂ + x₄ + x₆ + …
• 0 <= x_i <= a_i

For example, if  n = 3 and a = [2,3,2], you can pick the stones as [1,2,1] because x₁ + x₃ = 2  and x₂ = 2

Find the maximum total number of stones you can pick.

Input Format : The first line of input contains a single integer  n denoting the number of piles.

The second line of input contains n space separated integers a_i, where i^th the  integer denoted the number of stones in i^th pile.

Solution

Intuition : Find the minimum of sum of even and odd indexes, say min. We can pick min even and min odd stones.

class Result {

    /*
     * Complete the 'maximumStones' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY arr as parameter.
     */

    public static int maximumStones(List<Integer> arr) {
        int n = arr.size();
        int oddSum = 0, evenSum = 0; 
        for(int i = 0; i < n; i++) {
            if(i%2==0)
                evenSum+=arr.get(i);
            else
                oddSum+=arr.get(i);
        }
        return Math.min(evenSum, oddSum)*2;
    }
}

Strictly Increasing Sequence

Problem Statement

In a new numbers game, players are given an integer array of length N.

The players take turns, in each turn the current player does the following:

1. If a player can reorder the array elements to form a strictly increasing sequence, they win the game.
2. Otherwise the player can choose any element and remove it from the array.

Determine which player wins the game if both players play optimally and the first player plays first.

Input Format

The first line contains an integer T, denoting the number of test cases.

Then, the description of T test cases follow. Each test case is given in two consecutive lines.

The first line of each test case contains an integer N, denoting the number of elements in the array.

The second line of each test case contains N space-separated integers A_i, denoting the array elements.

Constraints

• 1 <=T <= 10
• 1 <= N <= 10⁵
• 1 <= Ai <=10⁹

Output Format

For each test case, print a single line contains “First” (without the quotes) if the first player wins the game or “Second” (without the quotes) otherwise.

Sample Input

1

3

1 2 3

Sample Output : First

Explanation : Here the given sequence is strictly increasing. So, the first player wins.

Sample Input

2

4

1 2 2 3

5

3 1 2 5 4

Sample Output

Second

First

Explanation : In the first test case:

The given sequence is not strictly increasing. So, the first player has to remove an element. If the player removes any 2, this will lead to a winning state for the second player. So, it would be better if 1 or 3 is removed.

Let’s assume the player removes 1. The second player can not reorder the elements and win. So, the second player has to remove an element. If the player removes any 2, this will lead to a winning state for the first player. So, it would be better if 3 is removed.

The remaining sequence is 2 2 . Which is not a strictly increasing sequence. So, the first player has to remove an element.

The second player wins since the remaining element is 2 and it is considered a strictly increasing sequence.

Solution

Intuition : If all the numbers are distinct, first player can reorder the numbers and win. Else, there will always be a chance for the last one to win by not removing the repeated numbers till the end.

class Result {

    /*
     * Complete the 'whoIsTheWinner' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts INTEGER_ARRAY arr as parameter.
     */

    public static String whoIsTheWinner(List<Integer> arr) {
        int size = arr.size();
        Set<Integer> s = new HashSet<>()
        for(int i = 0; i < size; i++) {            
            s.add(arr.get(i));
        }
        if(s.size() == size)
            return "First";
        else {
            if(size % 2 == 0)
                return "Second";
            else
                return "First";
        }   
    }
}

RBG Queries

Problem Statement

A RBG color is formed by adding different intensities of Red, Blue and Green Colors. So, any RBG color can be represented in the form of a triplet(r, b, g)  where r is intensity of red color, b denotes is of blue color and g is intensity of green color.

You have been given n colors, where each color has the intensities of red, blue and green color as (r_i, b_i, g_i). You can make new colors by mixing a subset of these colors. So, if you mix the colors  (r₁, b₁, g₁), (r₂, b₂, g₂),…, (r_k, b_k, g_k) you would get a color having respective intensities of red, blue and green as (max(r₁, r₂, … r_k), max(b₁, b₂, … b_k), max(g₁, g₂, … g_k)).

For example, mixing colors (4, 2, 3), (5, 1, 1) and (0, 0, 6) would give color (5, 2, 6).

You have been asked q queries, where in each query you need to answer whether is it possible to obtain a color (x, y, z) by mixing the given colors.

Note: that you may mix any number of colors (possibly one) to make the required color.

Input Format

The first line of input contains two space separated integers n and q.

The next n lines of input contains three space separated integers r_i, b_i, g_i and  denoting the respective intensities of red, blue and green in the i^th color.

The next q lines of input contains three space separated integers x, y and z denoting the respective intensities of red, blue and green color required.

Constraints

• 1 <= n, q <= 10⁵
• 0 <=  r_i, b_i, g_i,x,y,z <=10⁵

Output Format

For each query print a single line containing “YES” if it is possible to obtain the given color, else print “NO”.

Sample Input :

Solution

Intuition : Take 3 maps Map<Integer, Set<List<Integer>>> and add an entry for r. b. g data in each map with r, b and g as key respectively and the other 2 as list of values.

For each query, firstly check if all the r, b an g are present as key in map. If yes, there is a possibility of creating the desired color. Otherwise, add “NO” in result for this query.

Now, while checking the possibility of creating desired color, get the entry from map against desiredR, desiredB and desiredG (Set<List<Integer>>)

Take a flag, initially false.

For r, check if there exists a combination where there is b <= desiredB and g <= desiredG. If found, set flag as true and break this loop and check same for other 2 colors.

If the flag is true, check for B, while starting the loop don’t forget to flip flag to false, so that it gives true only when the data exists.

If at the end flag is still true, add “YES” in result list, otherwise, “NO”.

class Result {

    /*
     * Complete the 'mixColors' function below.
     *
     * The function is expected to return a STRING_ARRAY.
     * The function accepts following parameters:
     *  1. 2D_INTEGER_ARRAY colors
     *  2. 2D_INTEGER_ARRAY queries
     */

    public static List<String> mixColors(List<List<Integer>> colors, List<List<Integer>> queries) {
        Map<Integer, Set<List<Integer>>> rmap = new HashMap<>();
        Map<Integer, Set<List<Integer>>> bmap = new HashMap<>();
        Map<Integer, Set<List<Integer>>> gmap = new HashMap<>();
        
        for(List<Integer> color : colors) {
            int r = color.get(0);
            int b = color.get(1);
            int g = color.get(2);
            Set<List<Integer>> rs = rmap.getOrDefault(r, new HashSet<>());
            rs.add(new ArrayList<Integer>(Arrays.asList(b,g)));
            Set<List<Integer>> bs = bmap.getOrDefault(b, new HashSet<>());
            bs.add(new ArrayList<Integer>(Arrays.asList(r,g)));
            Set<List<Integer>> gs = gmap.getOrDefault(g, new HashSet<>());
            gs.add(new ArrayList<Integer>(Arrays.asList(r,b)));
            
            rmap.put(r, rs);
            bmap.put(b, bs);
            gmap.put(g, gs);
        }
        
        List<String> result = new ArrayList<>();
        for(List<Integer> q : queries) {
            int r = q.get(0);
            int b = q.get(1);
            int g = q.get(2);

            if(rmap.containsKey(r) && bmap.containsKey(b) && gmap.containsKey(g)) {
                Set<List<Integer>> rs = rmap.get(r);
                Set<List<Integer>> bs = bmap.get(b);
                Set<List<Integer>> gs = gmap.get(g);
                boolean flag = false;                            
                for(List<Integer> col : rs) {
                    if(col.get(0) <= b && col.get(1) <= g){
                        flag = true;
                        break;
                    }
                }
                if(flag) {
                    flag = false; 
                    for(List<Integer> col : bs) {
                        if(col.get(0) <= r && col.get(1) <= g){
                            flag = true;
                            break;
                        }
                    }
                }      
                if(flag) {
                    flag = false; 
                    for(List<Integer> col : gs) {
                        if(col.get(0) <= r && col.get(1) <= b){
                            flag = true;
                            break;
                        }
                    }
                } 
                if(flag)
                    result.add("YES");
                else 
                    result.add("NO"); 
            }
            else{
                result.add("NO");
            }
        }
        return result;
    }
}

Challenge Link : https://www.hackerrank.com/contests/hackerrank-hackfest-2020/challenges