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

**Input Format**

The first and only line of input contains string s .

**Constraints **:

1 <= n <= 10^{5}

**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 2

^{2}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 2

^{0}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();
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
_{1}+ x_{3}+ x_{5}+ …. = x_{2}+ x_{4}+ x_{6}+ … - 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_{1} + x_{3} = 2 and x_{2} = 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.

**Constraints **

- 2 <= n <= 10
^{5} - 1 <= a
^{i}<=10^{3}

**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 x

_{1}+ x

_{3}= x

_{2}+ x

_{4}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 x

_{1}+ x

_{3}= x

_{2}, 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

*even and*

**min***odd stones.*

**min**```
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:

- If a player can reorder the array elements to form a
**strictly**increasing sequence, they win the game. - 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
^{5} - 1 <= Ai <=10
^{9}

**Output Format**

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

**(without the quotes) otherwise.**

*“Second”***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_{1}, b_{1}, g_{1}), (r_{2}, b_{2}, g_{2}),…, (r_{k}, b_{k}, g_{k}) you would get a color having respective intensities of red, blue and green as (max(r_{1}, r_{2}, … r_{k}), max(b_{1}, b_{2}, … b_{k}), max(g_{1}, g_{2}, … 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
^{5} - 0 <= r
_{i}, b_{i}, g_{i},x,y,z <=10^{5}

**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

*and add an entry for*

**Map<Integer, Set<List<Integer>>>***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

**and break this loop and check same for other 2 colors.**

*true*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