Chef and Ballons

Chef and Ballons

Today a plane was hijacked by a maniac. All the passengers of the flight are taken as hostage. Chef is also one of them.

He invited one of the passengers to play a game with him. If he loses the game, he will release all the passengers, otherwise he will kill all of them. A high risk affair it is.

Chef volunteered for this tough task. He was blindfolded by Hijacker. Hijacker brought a big black bag from his pockets. The contents of the bag is not visible. He tells Chef that the bag contains R red, G green and B blue colored balloons.

Hijacker now asked Chef to take out some balloons from the box such that there are at least K balloons of the same color and hand him over. If the taken out balloons does not contain at least K balloons of the same color, then the hijacker will shoot everybody. Chef is very scared and wants to leave this game as soon as possible, so he will draw the minimum number of balloons so as to save the passengers. Can you please help scared Chef to find out the minimum number of balloons he should take out.
Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a three space-separated integers R, G and B.
The second line contains only one integer K.
Output

For each test case, output a single line containing one integer - the minimum number of balloons Chef need to take out from the bag.
Constraints

    1 ≤ T ≤ 1000
    1 ≤ R, G, B ≤ 109
    1 ≤ K ≤ max{R, G, B}

Subtasks

    Subtask 1 (44 points): 1 ≤ R, G, B ≤ 10
    Subtask 2 (56 points): No additional constraints

Example

Input:
2
3 3 3
1
3 3 3
2

Output:
1
4

Explanation

Example case 2. In the worst-case scenario first three balloons will be of the three different colors and only after fourth balloon Chef will have two balloons of the same color. So, Chef might need to fetch 4 balloons

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

#include<iostream> using namespace std; int main(){ int testcases; cin>>testcases; testcases=0; while(testcases){ unsigned long red,green,blue,goal,total; cin>>red>>green>>blue; cin>>goal; total=1; if(red<goal) total+=red; else total+=goal-1; if(green<goal) total+=green; else total+=goal-1; if(blue<goal) total+=blue; else total+=goal-1; cout<<total<<endl; testcases--; } return 0; }

Chef And Coloring

Chef And Coloring

After a long time, Chef has finally decided to renovate his house. Chef's house has N rooms in it numbered from 1 to N. Each room is currently painted in one of the red, blue or green colors. Your are given configuration of colors of his house by a string S consisting of N characters. In this string, color red will be denoted by 'R', green by 'G' and blue by 'B'.

Chef does not like current painting configuration that much and would like to repaint the house such that each room has same color.

For painting, Chef has all the 3 color paints available and mixing any 2 color paints will result into 3rd color paint i.e

    R + B = G
    B + G = R
    G + R = B

For example, painting a room having red color before with green color paint will make the color of room blue.

Also, Chef has many buckets of paint of each color. Simply put, you can assume that he will not run out of paint.

Being extraordinary lazy, our little chef does not want to work much and therefore, he has asked you to find the minimum number of rooms he has to repaint (possibly zero) in order to have all the rooms with same color. Can you please help him?
Input

First line of input contains a single integer T denoting the number of test cases. First line of each test case contains an integer N denoting the number of rooms in the chef's house. Next line of each test case contains a string S denoting the current color configuration of rooms.
Output

For each test case, Print the minimum number of rooms need to be painted in order to have all the rooms painted with same color i.e either red, blue or green.
Constraints

    1 ≤ T ≤ 10


    1 ≤ N ≤ 105


    Si = {'R','G','B'}

Scoring

    Subtask 1 (40 points) : 1 ≤ N ≤ 10
    Subtask 2 (60 points) : original constraints

Example

Input

3
3
RGR
3
RRR
3
RGB

Output

1
0
2

Explanation:

    Test 1: Chef prefers to paint room 2 with blue color such that the resulting color will be red and all the rooms have same color i.e red.
    Test 2: Given configuration has all the rooms painted with red color and therefore, chef does not need to do painting work at all.
    Test 3: One possible way of renovation is to paint room 1 with green color, room 2 with red color such that all rooms have same color i.e blue.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include<iostream> using namespace std; int main () { int testcases; cin>>testcases; char color; while(testcases) { int number_of_houses; cin>>number_of_houses; int red=0,green=0,blue=0,max=0; for(int i=0;i<number_of_houses;i++){ cin>>color; if(color =='R') red++; else if(color=='B') blue++; else green++; } if(red>blue){ if(red>green) max = red; else max = green; } else { if(blue>green) max = blue; else max = green; } cout<<(number_of_houses-max)<<endl; testcases--; } return 0; }

Look and say sequence algorithm

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
 public static String looksay(String s){
  String a = "";
  int count = 0;
  for(int i=0;i<s.length();i++){
   char current = s.charAt(i);
   if(i==0){
    count++;
   }
   else {
    char prev = s.charAt(i-1);
    if(prev == current){
     count++;
    }else {
     a+=count;
     a=a+prev;
     count=1;
     prev=current;
    }
   }
  }
        a+=count;
        a=a+(char)s.charAt(s.length()-1);
  return a;
 }
 
 public static void main (String[] args) throws java.lang.Exception
 {
     String s="1";
     for(int i=0;i<100;i++){
         s=looksay(s);
         System.out.println(s);
     }
 }
}

Check if a permutation of a string can become a palindrome.

Check if a permutation of a string can become a palindrome.  

 public class HelloWorld{  
    public static void main(String []args){  
     String s="maallyaam";  
     int [] arr= new int[26];  
     int odd=0;  
     for(int i=0;i<s.length();i++){  
       int index = s.charAt(i)-'a';  
       System.out.println(index);  
       if(arr[index]%2==0){  
         odd++;  
       } else {  
         odd--;  
       }  
       arr[index]++;  
     }  
     if(odd>1)  
       System.out.println("Cannot form palindrome!");  
     else  
       System.out.println("Can form palindrome!");  
    }  
 }  

Maximize a number by deleting a repeated number.

For eg:

Question : 223336226

Answer: 23336226

Other removal of numbers possible: 22336226, 22333626

Code:

int solution(int X){ 
   int max=1,val=X; 
   while(val/10!=0){ 
     max*=10; 
     val/=10; 
   } 
   boolean del=true; 
   int pos=-1,cur=-1,rep=0,max1=max; 
   val=X; 
   while(del && max!=0){ 
     int new_cur=val/max; 
     if(rep==1 && new_cur > cur){ 
       pos=max*10; 
       del=false; 
     } 
     else if(new_cur==cur){ 
       pos=max; 
     } 
     if(new_cur==cur) 
       rep = 1; 
     else 
       rep = 0; 
     val=val%max; 
     max=max/10; 
     cur=new_cur; 
   } 
   int new_num=0,max_new=max1/10; 
   val=X; 
   while(max1!=0){ 
     if(max1==pos){ 
       max1/=10; 
       continue; 
     } 
     int num=(val/max1)%10; 
     new_num+=max_new*num; 
     max_new/=10; 
     max1/=10; 
   } 
   return new_num; 
} 

Prisoners and hats puzzle

According to the story, four prisoners are arrested for a crime, but the jail is full and the jailor has nowhere to put them. He eventually comes up with the solution of giving them a puzzle so if they succeed they can go free but if they fail they are executed.

The jailor puts three of the men sitting in a line. The fourth man is put behind a screen (or in a separate room). He gives all four men party hats. The jailor explains that there are two black hats, and two white hats; that each prisoner is wearing one of the hats; and that each of the prisoners only see the hats in front of him but not on himself or behind him. The fourth man behind the screen can't see or be seen by any other prisoner. No communication among the prisoners is allowed.

If any prisoner can figure out and say to the jailor what color hat he has on his head with 100% certainty (without guessing) all four prisoners go free. If any prisoner suggests an incorrect answer, all four prisoners are executed. The puzzle is to find how the prisoners can escape, regardless of how the jailer distributes the hats.

import java.util.ArrayList;

public class Solution {

 public static void main(String[] args) {
  int members = 10;
  ArrayList<String> list = new ArrayList<String>();
  int blackCount = 0;
  for (int i = 1; i <= members; i++) {
   String val = (getRandom(1, 2) == 1) ? "white" : "black";
   list.add(val);
   if (val.equals("black"))
    blackCount++;
  }
  if (list.get(members - 1).equals("black"))
   blackCount--;
  System.out.println(list);

  int prevC = blackCount;
  String prevB = printStatus(blackCount % 2 != 0);

  for (int i = 8; i >= 0; i--) {
   if (list.get(i).equals("black"))
    blackCount--;
   boolean prevOdd;
   prevOdd = (prevB.equals("white")) ? (prevC == blackCount) ? true
     : false
     : (prevB.equals("black") && prevC == blackCount) ? true
       : false;
   prevB = printStatus(prevOdd);
   prevC = blackCount;
  }
 }

 private static String printStatus(boolean prevOdd) {
  String prevB;
  if (prevOdd) {
   System.out.print("white ");
   prevB = "white";
  } else {
   System.out.print("black ");
   prevB = "black";
  }
  return prevB;
 }

 public static int getRandom(int minimum, int maximum) {
  return minimum + (int) (Math.random() * maximum);
 }

}

Result:
From 1 to N: [white, white, black, black, black, white, white, white, white, white]
Last person to first telling their colors: white white white white white black black black white white 

Median of Medians Java implementation, kth element in array

Median of Median algorithm implementation in Java. It also provides Kth element in array after sorting. This algorithm runs in O(n) time.

Please leave comments below for more questions and remarks.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution {
 public static void main(String[] args) {
  Solution s = new Solution();
  List<Integer> a = Arrays.asList(88, 30, 11, 17, 22, 16, 39, 8, 31, 55,
    29, 63, 77, 69, 99, 90, 81, 2, 20, 53, 62, 5, 88, 33, 44, 6);
  System.out.println(s.findKthElement(a, 18));
  Collections.sort(a);
  System.out.println(a);
  System.out.println(a.get(18));
 }

 public int findKthElement(List<Integer> a, int k) {
  if (a.size() < 10) {
   Collections.sort(a);
   return a.get(k);
  }
  ArrayList<Integer> medians = new ArrayList<Integer>();
  for (int i = 0; i < a.size() - a.size() % 5; i = i + 5)
   medians.add(getMedian(a.subList(i, i + 5)));
  int v = getMedian(medians);

  ArrayList<Integer> left = getPartition(a, v, true);
  ArrayList<Integer> right = getPartition(a, v, false);

  return (left.size() + 1 == k) ? v : (left.size() > k) ? findKthElement(
    left, k) : findKthElement(right, k - left.size());
 }

 public int getMedian(List<Integer> a) {
  Collections.sort(a);
  return a.get(a.size() / 2);
 }

 public ArrayList<Integer> getPartition(List<Integer> a, int v,
   boolean isLessThan) {
  ArrayList<Integer> res = new ArrayList<Integer>();
  for (int val : a)
   if (isLessThan && val < v)
    res.add(val);
   else if (!isLessThan && val >= v)
    res.add(val);
  return res;
 }
}

Output:
62 ( value returned from algorithm)
[2, 5, 6, 8, 11, 16, 17, 20, 22, 29, 30, 31, 33, 39, 44, 53, 55, 62, 63, 69, 77, 81, 88, 88, 90, 99]
62 (kth value after sorting)

Arrangements/Combination of a elements in n positions

This method helps in arranging any type of objects in given number of positions. It is brut-force method of getting all type of combinations.

Please leave comments below for more questions and remarks.

public class Solution {
    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(1, 2);
        System.out.println(getArrangements(a, 4));
    }
    public static <T> List<List<T>> getArrangements
               (List<T> numbers, int n) {
        List<List<T>> result = new ArrayList<List<T>>();
        int itr = (int) Math.pow(n, numbers.size());
        for (int i = 0; i < itr; i++) {
            List<T> comb = new ArrayList<T>();
            for (int j = 0; j < n; j++) {
                int pos = (int) Math.pow(numbers.size(),
      (n - j - 1));
                int element = (i / pos) % (numbers.size());
                comb.add(numbers.get(element));
            }
            result.add(comb);
        }
        return result;
    }
}

Results:

Input1:[ 'A','B','C','D'] & 2 positions
output1: [[A, A], [A, B], [A, C], [A, D], [B, A], [B, B], [B, C], [B, D], [C, A], [C, B], [C, C], [C, D], [D, A], [D, B], [D, C], [D, D]]


Input2: [1,2] & 4 positions

[[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 1, 2, 2], [1, 2, 1, 1], [1, 2, 1, 2], [1, 2, 2, 1], [1, 2, 2, 2], [2, 1, 1, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 1, 2, 2], [2, 2, 1, 1], [2, 2, 1, 2], [2, 2, 2, 1], [2, 2, 2, 2]]

Palindrome

Palindrome problem:

Given : string

Output: An integer

Give product of lengths of two non overlapping palindromes from the string.

For ex:

"abcadad"

String1: "aba"
String2: "dad"

Product : 9

Good resources for preparation for coding interview

1. https://sites.google.com/site/mytechnicalcollection/algorithms/data-structures

2. hackerrank.com

3. codility.com

4. codefights.com