HackerRank Hackfest-2020

HackerRank Hackfest 2020 solutions (archived contest): This article preserves four programming challenges from the 2020 event: Cyclic Binary String, Game of Maximization, Strictly Increasing Sequence, and RBG Queries. The event is historical, not an upcoming competition. Each section includes the problem idea and Java solution; review the original challenge for exact input/output requirements.

Java note: The code snippets are method implementations for HackerRank-style Result classes, not standalone programs with a main method. Add the relevant java.util imports for collections when compiling them independently.

Cyclic Binary String

Problem Statement

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

Interpret each rotated binary string as a nonnegative integer X. Find the largest exponent k such that some rotation is divisible by 2<sup>k</sup>. If every bit is zero, return -1 as specified by this challenge.

Return the maximum such exponent, not the numerical value of the power of two.

For example, rotating 1001 produces 1100 (decimal 12), which is divisible by 2<sup>2</sup> but not by 2<sup>3</sup>; 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 : Find the longest circular run of zeros. In binary, each trailing zero contributes one factor of two; rotating a string can place any circular zero run at the end.

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; pile i contains a<sub>i</sub> 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

Reasoning: Let oddSum and evenSum be the total available stones in the odd- and even-numbered piles (using 1-based pile positions). Because the chosen totals must match, each side can contribute at most the smaller total. The optimum is 2 * min(oddSum, evenSum).

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

An RBG color in this archived problem 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;
    }
}

Original contest archive: HackerRank Hackfest 2020 challenges. Contest availability and judging environments may have changed since 2020.

Common troubleshooting questions

Why does the Java snippet not compile alone? HackerRank supplies a surrounding runner. For local compilation, add imports such as import java.util.*; and a small main method that calls the relevant Result method. Each separate example uses the same class name, so compile them separately or rename the classes.

Why is the cyclic-binary answer -1 for all zeros? Zero is divisible by every positive power of two; the challenge uses -1 as its special sentinel. For nonzero values, the exponent equals the number of trailing binary zeros after the best rotation.

Does the color-mixing operation average colors? No. This problem defines mixing as taking the coordinate-wise maximum. Its rule is a programming abstraction, not a model of physical pigment mixing.

For more Java algorithm practice, see our longest repeated substring walkthrough and in-place string reversal example.

C P Gupta

C P Gupta is a YouTuber and Blogger. He is expert in Microsoft Word, Excel and PowerPoint. His YouTube channel @pickupbrain is very popular and has crossed 9.9 Million Views.