# 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 22 , hence the answer is 2.

Input Format

The first and only line of input contains string s .

Constraints :

1 <= n <= 105

Output Format

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

Sample Input : 0011

Sample output : 2

Explanation : We can cyclically shift the string  2 times to get “1100” which is divisible by  22 hence the answer is 2.

Sample Input : 111

Sample Output : 0

Explanation : The string will remain same even after any number of cyclic shifts, and the given string in decimal is 7 , which is divisible 20 by  hence the answer is 0.

### 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();
trail = countTrailingZero(ch);
for(char c : ch) {
if(c == '0') {
curr++;
max = Math.max(curr, max);
}
else {
curr = 0;
}
}

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

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 nth 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 xi (1 <= i <= n)  stones from the ith pile, then

• x1 + x3 + x5 + …. = x2 + x4 + x6 + …
• 0 <= xi <= ai

For example, if  n = 3 and a = [2,3,2], you can pick the stones as [1,2,1] because x1 + x3 = 2  and x2 = 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 ai, where ith the  integer denoted the number of stones in ith pile.

Constraints

• 2 <= n <= 105
• 1 <= ai <=103

Output Format : Print a single integer denoting the maximum total number of stones you can pick.

Sample Input

4

5 1 1 4

Sample Output : 10

Explanation : Let x= [4, 1, 1, 4] . hence x1 + x3= x2 + x4  and total number of stones picked is 10. It can be checked that its not possible to pick any greater number of stones.

Sample Input

3

2 1 2

Sample Output : 2

Explanation : Let x = [0, 1, 1] . Hence x1 + x3= x2, and the total number of stones picked is 2.

### 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 Ai, denoting the array elements.

Constraints

• 1 <=T <= 10
• 1 <= N <= 105
• 1 <= Ai <=109

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++) {
}
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 (ri, bi, gi). You can make new colors by mixing a subset of these colors. So, if you mix the colors  (r1, b1, g1), (r2, b2, g2),…, (rk, bk, gk) you would get a color having respective intensities of red, blue and green as (max(r1, r2, … rk), max(b1, b2, … bk), max(g1, g2, … gk)).

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 ri, bi, gi and  denoting the respective intensities of red, blue and green in the ith 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 <= 105
• 0 <=  ri, bi, gi,x,y,z <=105

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 :

2 2

1 3 5

5 3 1

5 3 5

3 3 3

Sample Output :

YES

NO

Explanation : For the first query, we can mix both the given colors to get (5, 3, 5). For the second query, there’s no way to achieve the given color.

### 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<>());
Set<List<Integer>> bs = bmap.getOrDefault(b, new HashSet<>());
Set<List<Integer>> gs = gmap.getOrDefault(g, new HashSet<>());

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)
else