HackerearthGeneral Programming
1. Challenge: Solve Me First
Complete the function solveMeFirst to compute the sum of two integers.
Function prototype:
int solveMeFirst(int a, int b);
where,
 a is the first integer input.
 b is the second integer input
Return values
 sum of the above two integers
Sample Input
a = 2
b = 3
Sample Output
5
Solution:
public class SolveMeFirst {
static int solveMeFirst(int a, int b) {
return a+b;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a;
a = in.nextInt();
int b;
b = in.nextInt();
int sum;
sum = solveMeFirst(a, b);
System.out.println(sum);
in.close();
}
}
2. Challenge: Staircase
Consider a staircase of size :
#
##
###
####
Observe that its base and height are both equal to n, and the image is drawn using #
symbols and spaces. The last line is not preceded by any spaces.
Write a program that prints a staircase of size n .
Function Description
Complete the staircase function in the editor below. It should print a staircase as described above.
staircase has the following parameter(s):
 n: an integer
Input Format
A single integer,n , denoting the size of the staircase.
Constraints
0 < n ≤ 100
Output Format
Print a staircase of size n using #
symbols and spaces.
Note: The last line must have 0 spaces in it.
Sample Input
6
Sample Output
#
##
###
####
#####
######
Solution:
public class Staircase {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String str = "#";
for (int i = 0; i < n; i++) {
System.out.printf("%" + (n) + "s \n", str);
str += "#";
}
in.close();
}
}
3. Challenge: Plus Minus
Given an array of integers, calculate the fractions of its elements that are positive, negative, and are zeros. Print the decimal value of each fraction on a new line.
Note: This challenge introduces precision problems. The test cases are scaled to six decimal places, though answers with absolute error of upto 10^{4} are acceptable.
For example, given the array arr = [1,1,0,1,1] there are 5 elements, two positive, two negative and one zero. Their ratios would be 2/5 = 0.400000 , 2/5 = 0.400000 and 1/5 = 0.200000 . It should be printed as
0.400000
0.400000
0.200000
Function Description
Complete the plusMinus function in the editor below. It should print out the ratio of positive, negative and zero items in the array, each on a separate line rounded to six decimals.
plusMinus has the following parameter(s):
 arr: an array of integers
Input Format
The first line contains an integer,n , denoting the size of the array.
The second line contains n spaceseparated integers describing an array of numbers arr(arr[0], arr[1], arr[2], … , arr[n1]).
Constraints
0 < n ≤ 100
100 ≤ arr[i] ≤ 100
Output Format
You must print the following 3 lines:
 A decimal representing of the fraction of positive numbers in the array compared to its size.
 A decimal representing of the fraction of negative numbers in the array compared to its size.
 A decimal representing of the fraction of zeros in the array compared to its size.
Sample Input
6
4 3 9 0 4 1
Sample Output
0.500000
0.333333
0.166667
Solution:
public class PlusMinus {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int arr[] = new int[n];
float countPositive = 0;
float countNegetive = 0;
float countZero = 0;
for (int arr_i = 0; arr_i < n; arr_i++) {
arr[arr_i] = in.nextInt();
if (arr[arr_i] < 0) {
countNegetive++;
}
if (arr[arr_i] > 0) {
countPositive++;
}
if (arr[arr_i] == 0) {
countZero++;
}
}
System.out.printf("%1.6f \n", countPositive / n);
System.out.printf("%1.6f \n", countNegetive / n);
System.out.printf("%1.6f \n", countZero / n);
in.close();
}
}
4. Challenge: Diagonal Difference
Given a square matrix, calculate the absolute difference between the sums of its diagonals.
For example, the square matrix arr is shown below:
1 2 3
4 5 6
9 8 9
The lefttoright diagonal = 1+5+9=15. The right to left diagonal = 3+5+9=17. Their absolute difference is 1517=2.
Function description
Complete the diagonalDifference function in the editor below. It must return an integer representing the absolute diagonal difference.
diagonalDifference takes the following parameter:
 arr: an array of integers .
Input Format
The first line contains a single integer ,n , the number of rows and columns in the matrix arr .
Each of the next n lines describes a row, arr[i], and consists of n spaceseparated integers arr[i][j].
Constraints
 100 ≤ arr[i][j] ≤ 100
Output Format
Print the absolute difference between the sums of the matrix’s two diagonals as a single integer.
Sample Input
3
11 2 4
4 5 6
10 8 12
Sample Output
15
public class DiagonalDifference {
static int diagonalDifference(int[][] arr) {
int leftSum = 0, rightSum = 0;
int n = arr.length;
for (int i = 0; i < n; i++) {
leftSum += arr[i][i];
rightSum += arr[i][n  1  i];
}
return (Math.abs(leftSum  rightSum));
}
}
5.Challenge: A Very Big Sum
Calculate and print the sum of the elements in an array, keeping in mind that some of those integers may be quite large.
Function Description
Complete the aVeryBigSum function in the editor below. It must return the sum of all array elements.
aVeryBigSum has the following parameter(s):
 ar: an array of integers .
Input Format
The first line of the input consists of an integer n .
The next line contains n spaceseparated integers contained in the array.
Output Format
Print the integer sum of the elements in the array.
Constraints
1 ≤ 10 ≤ n
0 ≤ ar[i] ≤ 10^{10}
Sample Input
5
1000000001 1000000002 1000000003 1000000004 1000000005
Output
5000000015
public class AVeryBigSum {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long sum = 0;
for (int arr_i = 0; arr_i < n; arr_i++) {
sum += in.nextLong();
}
System.out.println(sum);
in.close();
}
}
6. Challenge: Simple Array Sum
Given an array of integers, find the sum of its elements.
For example, if the array ar = [1,2,3],1+2+3=6 , so return 6 .
Function Description
Complete the simpleArraySum function in the editor below. It must return the sum of the array elements as an integer.
simpleArraySum has the following parameter(s):
 ar: an array of integers
Input Format
The first line contains an integer, , denoting the size of the array.
The second line contains spaceseparated integers representing the array’s elements.
Constraints
0 < n , ar[i] ≤ 1000
Output Format
Print the sum of the array’s elements as a single integer.
Sample Input
6
1 2 3 4 10 11
Sample Output
31
public class SimpleArraySum {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int noOfElements = sc.nextInt();
int sum = 0;
for (int i = 0; i < noOfElements; i++) {
sum = sum + sc.nextInt();
}
System.out.println(sum);
sc.close();
}
}
7. Challenge: Compare the Triplets
Alice and Bob each created one problem for HackerRank. A reviewer rates the two challenges, awarding points on a scale from 1 to 100 for three categories: problem clarity, originality, and difficulty.
We define the rating for Alice’s challenge to be the triplet a = (a[0],a[1],a[2]), and the rating for Bob’s challenge to be the triplet b = (b[0],b[1],b[2]).
Your task is to find their comparison points by comparing a[0] with b[0], a[1] with b[1], and a[2] with b[2].
 If a[i] > b[i], then Alice is awarded point.
 If a[i] < b[i], then Bob is awarded point.
 If a[i] = b[i], then neither person receives a point.
Comparison points is the total points a person earned.
Given a and b, determine their respective comparison points.
For example, a = [1,2,3] and b = [3,2,1]. For elements 0, Bob is awarded a point because a[0] < b[0]. For the equal elements a[1] and b[1], no points are earned. Finally, for elements 2,a[2] > b[2] so Alice receives a point. Your return array would be [1,1] with Alice’s score first and Bob’s second.
Function Description
Complete the function compareTriplets in the editor below. It must return an array of two integers, the first being Alice’s score and the second being Bob’s.
compareTriplets has the following parameter(s):
 a: an array of integers representing Alice’s challenge rating
 b: an array of integers representing Bob’s challenge rating
Input Format
The first line contains 3 spaceseparated integers, a[0],a[1] , and a[2], describing the respective values in triplet a.
The second line contains 3 spaceseparated integers, b[0],b[1] , and b[2], describing the respective values in triplet b.
Constraints

1 ≤ a[i] ≤ 100
 1 ≤ b[i] ≤ 100
Output Format
Return an array of two integers denoting the respective comparison points earned by Alice and Bob.
Sample Input 0
5 6 7 3 6 10
Sample Output 0
1 1
Solution:
public class CompareTheTriplets {
static List<Integer> compareTriplets(List<Integer> a, List<Integer> b) {
int aliceTotalScore = 0, bobTotalScore = 0;
for (int i = 0; i < 3; i++) {
int aliceScore = a.get(i);
int bobScore = b.get(i);
if (aliceScore != bobScore) {
int temp = aliceScore > bobScore ? aliceTotalScore++ : bobTotalScore++;
}
}
List<Integer> result = new ArrayList<>();
result.add(aliceTotalScore);
result.add(bobTotalScore);
return result;
}
}
8. Challenge: Divisible Sum Pairs
You are given an array of n integers, ar = [ar[0], ar[1], … , ar[n1] , and a positive integer, k . Find and print the number of (i,j) pairs where i < j and ar[i] + ar[j] is divisible by k.
For example, ar = [1,2,3,4,5,6] and k = 5. Our three pairs meeting the criteria are [1,4],[2,3] and [4,6].
Function Description
Complete the divisibleSumPairs function in the editor below. It should return the integer count of pairs meeting the criteria.
divisibleSumPairs has the following parameter(s):
 n: the integer length of array
 ar: an array of integers
 k: the integer to divide the pair sum by
Input Format
The first line contains 2 spaceseparated integers, n and k.
The second line contains n spaceseparated integers describing the values of ar[ar[o],ar[1],…ar[n1]].
Constraints

2 ≤ n ≤ 100

1 ≤ k ≤ 100
 1 ≤ ar[i] ≤ 100
Output Format
Print the number of (i,j) pairs where i<j and a[i] + a[j] is evenly divisible by .
Sample Input
6 3
1 3 2 6 1 2
Sample Output
5
Solution:
public class DivisibleSumPairs {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();
int a[] = new int[M];
for (int i = 0; i < M; i++) {
a[i] = sc.nextInt();
}
int count = 0;
for (int i = 0; i < M; i++) {
for (int j = i + 1; j < M; j++) {
if ((a[i] + a[j]) % N == 0) {
count++;
}
}
}
System.out.println(count);
sc.close();
}
}
9. Challenge: Kangaroo
You are choreographing a circus show with various animals. For one act, you are given two kangaroos on a number line ready to jump in the positive direction (i.e, toward positive infinity).
 The first kangaroo starts at location x1 and moves at a rate of v1 meters per jump.
 The second kangaroo starts at location x2 and moves at a rate of v2 meters per jump.
You have to figure out a way to get both kangaroos at the same location at the same time as part of the show. If it is possible, return YES
, otherwise return NO
.
For example, kangaroo 1 starts at x1 = 2 with a jump distance v1 = 1 and kangaroo 2 starts at x2 = 1 with a jump distance of v2 = 2. After one jump, they are both at x = 3, (x1 + v1 = 2 + 1, x2 + v2 = 1 + 2), so our answer is YES
.
Function Description
Complete the function kangaroo in the editor below. It should return YES
if they reach the same position at the same time, or NO
if they don’t.
kangaroo has the following parameter(s):
 x1, v1: integers, starting position and jump distance for kangaroo 1
 x2, v2: integers, starting position and jump distance for kangaroo 2
Input Format
A single line of four spaceseparated integers denoting the respective values of x1, v1, x2, and v2.
Constraints

0 ≤ x1 < x2 ≤ 10000

1 ≤ v1 ≤ 10000
 1 ≤ v2 ≤ 10000
Output Format
Print YES
if they can land on the same location at the same time; otherwise, print NO
.
Note: The two kangaroos must land at the same location after making the same number of jumps.
Sample Input 0
0 3 4 2
Sample Output 0
Yes
Solution:
public class Kangaroo {
static String kangaroo(int x1, int v1, int x2, int v2) {
if (v1 > v2) {
int remainder = (x1  x2) % (v2  v1);
if (remainder == 0) {
return "YES";
}
}
return "NO";
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int x1 = in.nextInt();
int v1 = in.nextInt();
int x2 = in.nextInt();
int v2 = in.nextInt();
System.out.println(kangaroo(x1, v1, x2, v2));
in.close();
}
}
10. Challenge: Drawing Book
Brie’s Drawing teacher asks her class to open their books to a page number. Brie can either start turning pages from the front of the book or from the back of the book. She always turns pages one at a time. When she opens the book,1 page is always on the right side:
When she flips page 1, she sees pages 2 and 3. Each page except the last page will always be printed on both sides. The last page may only be printed on the front, given the length of the book. If the book is n pages long, and she wants to turn to page p, what is the minimum number of pages she will turn? She can start at the beginning or the end of the book.
Given n and p, find and print the minimum number of pages Brie must turn in order to arrive at page p.
Function Description
Complete the pageCount function in the editor below. It should return the minimum number of pages Brie must turn.
pageCount has the following parameter(s):
 n: the number of pages in the book
 p: the page number to turn to
Input Format
The first line contains an integer n, the number of pages in the book.
The second line contains an integer, p, the page that Brie’s teacher wants her to turn to.
Constraints

1 ≤ n ≤ 10^{5}
 1 ≤ p ≤ n
Output Format
Print an integer denoting the minimum number of pages Brie must turn to get to page .
Sample Input 0
6
2
Sample Output 0
1
Solution:
public class DrawingBook {
static int pageCount(int n, int p) {
int totalPageTurnCountFromFront = n / 2;
int targetPageTurnCountFromFront = p / 2;
int targetPageTurnCountFromBack = totalPageTurnCountFromFront  targetPageTurnCountFromFront;
return Math.min(targetPageTurnCountFromFront, targetPageTurnCountFromBack);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int p = in.nextInt();
System.out.println(pageCount(n, p));
in.close();
}
}
11. Challenge: Birthday Cake Candles
You are in charge of the cake for your niece’s birthday and have decided the cake will have one candle for each year of her total age. When she blows out the candles, she’ll only be able to blow out the tallest ones. Your task is to find out how many candles she can successfully blow out.
For example, if your niece is turning 4 years old, and the cake will have 4 candles of height 4,4 ,1 ,3 , she will be able to blow out 2 candles successfully, since the tallest candles are of height 4 and there are 2 such candles.
Function Description
Complete the function birthdayCakeCandles
in the editor below. It must return an integer representing the number of candles she can blow out.
birthdayCakeCandles has the following parameter(s):
 ar: an array of integers representing candle heights
Input Format
The first line contains a single integer,n , denoting the number of candles on the cake.
The second line contains n spaceseparated integers, where each integer i describes the height of candle i.
Constraints

1 ≤ n ≤ 10^{5}

1 ≤ ar[i] ≤ 10^{7}
Output Format
Print the number of candles that can be blown out on a new line.
Sample Input 0
4
3 2 1 3
Sample Output 0
2
Solution:
public class BirthdayCakeCandles {
static int birthdayCakeCandles(int[] ar) {
int maxCandleHeight = Integer.MIN_VALUE;
int maxCandleFreqCount = 0;
for (int i = 0; i < ar.length; i++) {
if (ar[i] == maxCandleHeight) {
maxCandleFreqCount++;
}
if (ar[i] > maxCandleHeight) {
maxCandleHeight = ar[i];
maxCandleFreqCount = 1;
}
}
return maxCandleFreqCount;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int a[] = new int[M];
for (int i = 0; i < M; i++) {
a[i] = sc.nextInt();
}
System.out.println(birthdayCakeCandles(a));
sc.close();
}
}
12. Challenge: Bon Appetit
Anna and Brian are sharing a meal at a restuarant and they agree to split the bill equally. Brian wants to order something that Anna is allergic to though, and they agree that Anna won’t pay for that item. Brian gets the check and calculates Anna’s portion. You must determine if his calculation is correct.
For example, assume the bill has the following prices: bill = [2,4,2]. Anna declines to eat item k = bill[2] which costs 6. If Brian calculates the bill correctly, Anna will pay (2 + 4)/2 = 3. If he includes the cost of bill[2], he will calculate (2 + 4 + 6)/2 = 6. In the second case, he should refund 3 to Anna.
Function Description
Complete the bonAppetit function in the editor below. It should print Bon Appetit
if the bill is fairly split. Otherwise, it should print the integer amount of money that Brian owes Anna.
bonAppetit has the following parameter(s):
 bill: an array of integers representing the cost of each item ordered
 k: an integer representing the zerobased index of the item Anna doesn’t eat
 b: the amount of money that Anna contributed to the bill
Input Format
The first line contains two spaceseparated integers n and k, the number of items ordered and the 0based index of the item that Anna did not eat.
The second line contains n spaceseparated integers bill[i] where 0 ≤ i < n.
The third line contains an integer, b, the amount of money that Brian charged Anna for her share of the bill.
Constraints
 2 ≤ n ≤ 10^{5}

0 ≤ k < n

0 ≤ bill[i] ≤ 10^{4}

0 ≤ b ≤
 The amount of money due Anna will always be an integer
Output Format
If Brian did not overcharge Anna, print Bon Appetit
on a new line; otherwise, print the difference
(i.e.,b_{charged }– b_{actual}) that Brian must refund to Anna. This will always be an integer.
Sample Input 0
4 1
3 10 2 9
12
Sample Output 0
5
Solution:
public class BonAppétit {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int bCharged = 0, sum = 0, bActual = 0;
for (int i = 0; i < n; i++) {
int cost = sc.nextInt();
if (k != i)
sum += cost;
}
bActual = sum / 2;
bCharged = sc.nextInt();
if (bActual == bCharged) {
System.out.println("Bon Appetit");
} else {
System.out.println(bCharged  bActual);
}
sc.close();
}
}
13. Challenge: Sock Merchant
John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.
For example, there are n =7 socks with colors ar = [1,2,1,2,1,3,2]. There is one pair of color 1 and one of color 2. There are three odd socks left, one of each color. The number of pairs is 2.
Function Description
Complete the sockMerchant function in the editor below. It must return an integer representing the number of matching pairs of socks that are available.
sockMerchant has the following parameter(s):
 n: the number of socks in the pile
 ar: the colors of each sock
Input Format
The first line contains an integer n, the number of socks represented in ar.
The second line contains n spaceseparated integers describing the colors ar[i] of the socks in the pile.
Constraints

1≤ n ≤ 100

1 ≤ ar[i] ≤ 100 where 0 ≤ i < n
 where
Output Format
Return the total number of matching pairs of socks that John can sell.
Sample Input
9
10 20 20 10 10 30 50 10 20
Sample Output
3
Solution:
public class SockMerchant {
static int sockMerchant(int n, int[] ar) {
HashSet<Integer> set = new HashSet<Integer>();
int count = 0;
for (int i = 0; i < n; i++) {
int element = ar[i];
if (set.contains(element)) {
set.remove(element);
count++;
} else {
set.add(element);
}
}
return count;
}
}
14. Challenge: Apple and Orange
Sam’s house has an apple tree and an orange tree that yield an abundance of fruit. In the diagram below, the red region denotes his house, where s is the start point, and t is the endpoint. The apple tree is to the left of his house, and the orange tree is to its right. You can assume the trees are located on a single point, where the apple tree is at point a, and the orange tree is at point b.
When a fruit falls from its tree, it lands d units of distance from its tree of origin along the xaxis. A negative value of d means the fruit fell d units to the tree’s left, and a positive value of d means it falls d units to the tree’s right.
Given the value of for d apples and n oranges, determine how many apples and oranges will fall on Sam’s house (i.e., in the inclusive range [s,t])?
For example, Sam’s house is between s = 7 and t = 10. The apple tree is located at a = 4 and the orange at b = 12. There are m = 3 apples and n = 3 oranges. Apples are thrown apples = [2,3,4] units distance from a, and oranges = [3,2,4] units distance. Adding each apple distance to the position of the tree, they land at [4 + 2, 4 + 3, 4 + 4] = [6,7,0]. Oranges land at [12 + 3, 12 + 2,12 + 4] = [15,10,8] . One apple and two oranges land in the inclusive range 7 – 10 so we print
1
2
Function Description
Complete the countApplesAndOranges function in the editor below. It should print the number of apples and oranges that land on Sam’s house, each on a separate line.
countApplesAndOranges has the following parameter(s):
 s: integer, starting point of Sam’s house location.
 t: integer, ending location of Sam’s house location.
 a: integer, location of the Apple tree.
 b: integer, location of the Orange tree.
 apples: integer array, distances at which each apple falls from the tree.
 oranges: integer array, distances at which each orange falls from the tree.
Input Format
The first line contains two spaceseparated integers denoting the respective values of s and t.
The second line contains two spaceseparated integers denoting the respective values of a and b.
The third line contains two spaceseparated integers denoting the respective values of m and n.
The fourth line contains spaceseparated integers denoting the respective distances that each apple falls from point a.
The fifth line contains spaceseparated integers denoting the respective distances that each orange falls from point b.
Constraints

1 ≤ s,t,a,b,m,n≤ 10^{5}

10^{5} ≤ d ≤ 10^{5}
 a < s < t < b
Output Format
Print two integers on two different lines:
 The first integer: the number of apples that fall on Sam’s house.
 The second integer: the number of oranges that fall on Sam’s house.
Sample Input 0
7 11
5 15
3 2
2 2 1
5 6
Sample Output 0
1 1
Solution:
public class AppleAndOrange {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int s = sc.nextInt();
int t = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
int m = sc.nextInt();
int n = sc.nextInt();
int aCount = 0, oCount = 0;
for (int i = 0; i < m; i++) {
int temp = sc.nextInt();
if ((a + temp) >= s && (a + temp) <= t) {
aCount++;
}
}
for (int i = 0; i < n; i++) {
int temp = sc.nextInt();
if ((b + temp) >= s && (b + temp) <= t) {
oCount++;
}
}
System.out.println(aCount);
System.out.println(oCount);
sc.close();
}
}
15. Challenge: Between two Sets
You will be given two arrays of integers and asked to determine all integers that satisfy the following two conditions:
 The elements of the first array are all factors of the integer being considered
 The integer being considered is a factor of all elements of the second array
These numbers are referred to as being between the two arrays. You must determine how many such numbers exist.
For example, given the arrays a = [2,6] and b = [24,36], there are two numbers between them: 6 and 12.
6%2 = 0, 6%6 = 0 , 24%6 = 0 and 36%6 = 0 for the first value. Similarly, 12%2 = 0, 12%6 = 0 and 24%12 = 0, 36%12 = 0.
Function Description
Complete the getTotalX function in the editor below. It should return the number of integers that are betwen the sets.
getTotalX has the following parameter(s):
 a: an array of integers
 b: an array of integers
Input Format
The first line contains two spaceseparated integers, n and m, the number of elements in array a and the number of elements in array b.
The second line contains n distinct spaceseparated integers describing a[i] where 0 ≤ i ≤ n.
The third line contains distinct spaceseparated integers describing b[j] where 0 ≤ j ≤ m.
Constraints

1 ≤ n, m ≤ 10

1 ≤ a[j] ≤ 100

1 ≤ b[j] ≤ 100
Output Format
Print the number of integers that are considered to be between a and b.
Sample Input
2 3
2 4
16 32 96
Sample Output
3
Solution:
public class BetweenTwoSets {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int gcd = 0;
int a[] = new int[n];
int b[] = new int[m];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int lcm = a[0];
for (int i = 0; i < m; i++) {
b[i] = sc.nextInt();
gcd = findGCD(b[i], gcd);
}
for (int i = 0; i < n  1; i++) {
lcm = (lcm * a[i + 1]) / findGCD(a[i + 1], lcm);
}
int count = 0, t = 0;
for (int i = 1; i <= gcd && t <= gcd; i++) {
t = lcm * i;
if (gcd % (lcm * i) == 0) {
count++;
}
}
System.out.println(count);
sc.close();
}
private static int findGCD(int a, int b) {
return b == 0 ? a : findGCD(b, a % b);
}
}
16. Challenge: MiniMax Sum
Given five positive integers, find the minimum and maximum values that can be calculated by summing exactly four of the five integers. Then print the respective minimum and maximum values as a single line of two spaceseparated long integers.
For example, arr = [1,3,5,7,9] . Our minimum sum is 1 + 3 + 5 + 7 = 16 and our maximum sum is 3 + 5 + 7 + 9 = 24. We would print
16 24
Function Description
Complete the miniMaxSum function in the editor below. It should print two spaceseparated integers on one line: the minimum sum and the maximum sum of 4 of 5 elements.
miniMaxSum has the following parameter(s):
 arr: an array of 5 integers
Input Format
A single line of five spaceseparated integers.
Constraints
1 ≤ arr[i] ≤ 10^{9}
Output Format
Print two spaceseparated long integers denoting the respective minimum and maximum values that can be calculated by summing exactly four of the five integers. (The output can be greater than a 32 bit integer.)
Sample Input
1 2 3 4 5
Sample Output
10 14
Solution:
public class MiniMaxSum {
static void miniMaxSum(int[] arr) {
long min = 0, max = 0, sum = 0;
min = arr[0];
max = min;
sum = min;
for (int i = 1; i < arr.length; i++) {
sum += arr[i];
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
System.out.print((sum  max) + " " + (sum  min));
}
}
17. Challenge: Grading Students
HackerLand University has the following grading policy:
 Every student receives a grade in the inclusive range from 0 to 100.
 Any grade less than 40 is a failing grade.
Sam is a professor at the university and likes to round each student’s grade according to these rules:
 If the difference between the grade and the next multiple of 5 is less than 3, round up to the next multiple of 5.
 If the value of grade is less than 38, no rounding occurs as the result will still be a failing grade.
For example, grade = 84 will be rounded to 85 but 29 will not be rounded because the rounding would result in a number that is less than 40.
Given the initial value of grade for each of Sam’s n students, write code to automate the rounding process.
Function Description
Complete the function gradingStudents in the editor below. It should return an integer array consisting of rounded grades.
gradingStudents has the following parameter(s):
 grades: an array of integers representing grades before rounding
Input Format
The first line contains a single integer, n, the number of students.
Each line i of the n subsequent lines contains a single integer, grade[i], denoting student i‘s grade.
Constraints

1 ≤ n ≤ 60

0≤ grades[i] ≤ 100
Output Format
For each grades[i], print the rounded grade on a new line.
Sample Input 0
4
73
67
38
33
Sample Output 0
75 67 40 33
Solution:
public class GradingStudents {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int a0 = 0; a0 < n; a0++) {
int grade = in.nextInt();
System.out.println(grade < 38  grade % 5 < 3 ? grade : grade + (5  grade % 5));
in.close();
}
}
}
18. Challenge: Breaking the Records
Maria plays college basketball and wants to go pro. Each season she maintains a record of her play. She tabulates the number of times she breaks her season record for most points and least points in a game. Points scored in the first game establish her record for the season, and she begins counting from there.
For example, assume her scores for the season are represented in the array scores = [12,24,10,24]. Scores are in the same order as the games played. She would tabulate her results as follows:
Count
Game Score Minimum Maximum Min Max
0 12 12 12 0 0
1 24 12 24 0 1
2 10 10 24 1 1
3 24 10 24 1 1
Given Maria’s scores for a season, find and print the number of times she breaks her records for most and least points scored during the season.
Function Description
Complete the breakingRecords function in the editor below. It must return an integer array containing the numbers of times she broke her records. Index 0 is for breaking most points records, and index 1 is for breaking least points records.
breakingRecords has the following parameter(s):
 scores: an array of integers
Input Format
The first line contains an integer n, the number of games.
The second line contains n spaceseparated integers describing the respective values of Score_{0}, Score_{1,, }Score_{n1}.
Constraints

1 ≤ n ≤ 1000

1 ≤ score[i] ≤ 10^{8}
Output Format
Print two spaceseperated integers describing the respective numbers of times her best (highest) score increased and her worst (lowest) score decreased.
Sample Input 0
9
10 5 20 20 4 5 2 25 1
Sample Output 0
2 4
Solution:
public class BreakingTheRecords {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] score = new int[n];
int baseScore = in.nextInt();
int bestScoreCount = 0, leastScoreCount = 0;
int baseBestScore = baseScore, baseLeastScore = baseScore;
for (int score_i = 1; score_i < n; score_i++) {
score[score_i] = in.nextInt();
if (score[score_i] < baseLeastScore) {
baseLeastScore = score[score_i];
leastScoreCount++;
}
if (score[score_i] > baseBestScore) {
baseBestScore = score[score_i];
bestScoreCount++;
}
}
System.out.println(bestScoreCount + " " + leastScoreCount);
in.close();
}
}
19. Challenge: Migratory Birds
You have been asked to help study the population of birds migrating across the continent. Each type of bird you are interested in will be identified by an integer value. Each time a particular kind of bird is spotted, its id number will be added to your array of sightings. You would like to be able to find out which type of bird is most common given a list of sightings. Your task is to print the type number of that bird and if two or more types of birds are equally common, choose the type with the smallest ID number.
For example, assume your bird sightings are of types arr = [1,1,2,2,3]. There are two each of types 1 and 2, and one sighting of type 3. Pick the lower of the two types seen twice: type 1.
Function Description
Complete the migratoryBirds function in the editor below. It should return the lowest type number of the most frequently sighted bird.
migratoryBirds has the following parameter(s):
 arr: an array of integers representing types of birds sighted
Input Format
The first line contains an integer denoting n, the number of birds sighted and reported in the array arr.
The second line describes arr as n spaceseparated integers representing the type numbers of each bird sighted.
Constraints

5≤ n ≤ 2 x 10^{5}
 It is guaranteed that each type is 1,2 ,3 ,4 , or 5.
Output Format
Print the type number of the most common bird; if two or more types of birds are equally common, choose the type with the smallest ID number.
Sample Input 0
6
1 4 4 4 5 3
Sample Output 0
4
Solution:
public class MigratoryBirds {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] types = new int[n];
int maxFreqValue = 0, freqId = 0;
for (int types_i = 0; types_i < n; types_i++) {
int index = in.nextInt();
types[index  1]++;
}
for (int i = 0; i < n; i++) {
if (types[i] > maxFreqValue) {
maxFreqValue = types[i];
freqId = i + 1;
}
}
System.out.println(freqId);
in.close();
}
}
20. Challenge: Birthday Chocolate
Lily has a chocolate bar that she wants to share it with Ron for his birthday. Each of the squares has an integer on it. She decides to share a contiguous segment of the bar selected such that the length of the segment matches Ron’s birth month and the sum of the integers on the squares is equal to his birth day. You must determine how many ways she can divide the chocolate.
Consider the chocolate bar as an array of squares,s = [2,2,1,3,2] . She wants to find segments summing to Ron’s birth day, d =4 with a length equalling his birth month, m=2. In this case, there are two segments meeting her criteria: [2,2] and [1,3].
Function Description
Complete the birthday function in the editor below. It should return an integer denoting the number of ways Lily can divide the chocolate bar.
birthday has the following parameter(s):
 s: an array of integers, the numbers on each of the squares of chocolate
 d: an integer, Ron’s birth day
 m: an integer, Ron’s birth month
Input Format
The first line contains an integer n, the number of squares in the chocolate bar.
The second line contains n spaceseparated integers s[i], the numbers on the chocolate squares where 0 ≤ i < n.
The third line contains two spaceseparated integers, d and m, Ron’s birth day and his birth month.
Constraints

1 ≤ n ≤ 100

1 ≤ s[i] ≤ 5, where (o ≤ i ≤ n)

1 ≤ d ≤ 31

1 ≤ m ≤ 12
Output Format
Print an integer denoting the total number of ways that Lily can portion her chocolate bar to share with Ron.
Sample Input 0
5
1 2 1 3 2
3 2
Sample Output 0
2
Solution:
public class BirthdayChocolate {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int a[] = new int[M];
for (int i = 0; i < M; i++) {
a[i] = sc.nextInt();
}
int d = sc.nextInt();
int m = sc.nextInt();
int sum = 0, count = 0;
if (M <= m) {
for (int j = 0; j < M; j++) {
sum += a[j];
if (sum == d) {
count++;
}
}
} else {
for (int i = 0; i <= M  m; i++) {
for (int j = i; j < i + m; j++) {
sum += a[j];
}
if (sum == d) {
count++;
}
sum = 0;
}
}
System.out.println(count);
sc.close();
}
}
21. Challenge: Time Conversion
Given a time in 12hour AM/PM format, convert it to military (24hour) time.
Note: Midnight is 12:00:00AM on a 12hour clock, and 00:00:00 on a 24hour clock. Noon is 12:00:00PM on a 12hour clock, and 12:00:00 on a 24hour clock.
Function Description
Complete the timeConversion function in the editor below. It should return a new string representing the input time in 24 hour format.
timeConversion has the following parameter(s):
 s: a string representing time in 12 hour format
Input Format
A single string s containing a time in 12hour clock format (i.e.: hh:mm:ssAM or hh:mm:ssPM ), where
01 ≤ hh ≤ 12 and 00 ≤ mm, ss ≤ 59
.
Constraints
 All input times are valid
Output Format
Convert and print the given time in 24hour format, where 00 ≤ hh ≤ 23.
Sample Input 0
07:05:45PM
Sample Output 0
19:05:45
Solution:
public class TimeConversion {
static String timeConversion(String s) {
String[] str = s.split(":");
int hour = Integer.parseInt(str[0]);
String min = str[1];
String secPeriod = str[2];
String sec = str[2].substring(0, secPeriod.length()  2);
String period = str[2].substring(secPeriod.length()  2, secPeriod.length());
String newTimeINString = "";
if ((0 <= hour && hour < 12) && (period.equalsIgnoreCase("AM"))) {
newTimeINString = String.format("%02d", hour) + ":" + min + ":" + sec;
} else if ((0 <= hour && hour < 12) && period.equalsIgnoreCase("PM")) {
newTimeINString = (12 + hour) + ":" + min + ":" + sec;
} else if ((hour == 12) && (period.equalsIgnoreCase("AM"))) {
newTimeINString = "00" + ":" + min + ":" + sec;
} else if ((hour == 12) && (period.equalsIgnoreCase("PM"))) {
newTimeINString = hour + ":" + min + ":" + sec;
}
return newTimeINString;
}
}
22. Challenge: Library Fine
Your local library needs your help! Given the expected and actual return dates for a library book, create a program that calculates the fine (if any). The fee structure is as follows:
 If the book is returned on or before the expected return date, no fine will be charged (i.e.: fine = 0).
 If the book is returned after the expected return day but still within the same calendar month and year as the expected return date, fine = 15 Hackos x (the number of days late).
 If the book is returned after the expected return month but still within the same calendar year as the expected return date, the fine = 500 Hackos x (the number of months late)
 If the book is returned after the calendar year in which it was expected, there is a fixed fine of 10000 Hackos.
Charges are based only on the least precise measure of lateness. For example, whether a book is due January 1, 2017 or December 31, 2017, if it is returned January 1, 2018, that is a year late and the fine would be 10,000 Hackos.
Function Description
Complete the libraryFine function in the editor below. It must return an integer representing the fine due.
libraryFine has the following parameter(s):
 d1, m1, y1: returned date day, month and year
 d2, m2, y2: due date day, month and year
Input Format
The first line contains 3 spaceseparated integers, d1,m1,y1 denoting the respective day,month, and year on which the book was returned.
The second line contains 3 spaceseparated integers, d2,m2,y2 denoting the respective day,month, and year on which the book was due to be returned.
Constraints

1≤ d1, d2 ≤ 31

1≤ m1, m2≤ 12

1≤ y1, y2 ≤ 3000
 It is guaranteed that the dates will be valid Georgian calendar date.
Output Format
Print a single integer denoting the library fine for the book received as input.
Sample Input
9 6 2015
6 6 2015
Sample Output
45
Solution:
public class LibraryFine {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String d1 = sc.nextLine();
String d2 = sc.nextLine();
String[] aDate = d1.split(" ");
String[] eDate = d2.split(" ");
int ad = Integer.parseInt(aDate[0]);
int am = Integer.parseInt(aDate[1]);
int ay = Integer.parseInt(aDate[2]);
int ed = Integer.parseInt(eDate[0]);
int em = Integer.parseInt(eDate[1]);
int ey = Integer.parseInt(eDate[2]);
int fine = 0;
if (ay > ey) {
fine = 10000;
} else {
if (ay == ey && am > em) {
fine = 500 * (am  em);
} else {
if (ay == ey && am == em && ad > ed) {
fine = 15 * (ad  ed);
}
}
}
System.out.println(fine);
sc.close();
}
}
23. Challenge: Save the Prisoner!
A jail has a number of prisoners and a number of treats to pass out to them. Their jailer decides the fairest way to divide the treats is to seat the prisoners around a circular table in sequentially numbered chairs. A chair number will be drawn from a hat. Beginning with the prisoner in that chair, one candy will be handed to each prisoner sequentially around the table until all have been distributed.
The jailer is playing a little joke, though. The last piece of candy looks like all the others, but it tastes awful. Determine the chair number occupied by the prisoner who will receive that candy.
For example, there are 4 prisoners and 6 pieces of candy. The prisoners arrange themselves in seats numbered 1 to 4. Let’s suppose two is drawn from the hat. Prisoners receive candy at positions 2,3,4,1,2,3. The prisoner to be warned sits in chair number 3.
Function Description
Complete the saveThePrisoner function in the editor below. It should return an integer representing the chair number of the prisoner to warn.
saveThePrisoner has the following parameter(s):
 n: an integer, the number of prisoners
 m: an integer, the number of sweets
 s: an integer, the chair number to begin passing out sweets from
Input Format
The first line contains an integer, t, denoting the number of test cases.
The next t lines each contain 3 spaceseparated integers:
– n: the number of prisoners
– m: the number of sweets
– s: the chair number to start passing out treats at
Constraints

1≤ t ≤ 100

1 ≤ n ≤ 10^{9}

1 ≤ m ≤ 10^{9}

1 ≤ s ≤ n
Output Format
For each test case, print the chair number of the prisoner who receives the awful treat on a new line.
Sample Input 0
2
5 2 1
5 2 2
Sample Output 0
2
3
Explanation 0
In first query, there are prisoners and sweets. Distribution starts at seat number . Prisoners in seats numbered and get sweets. Warn prisoner .
In the second query, distribution starts at seat so prisoners in seats and get sweets. Warn prisoner .
Sample Input 1
2
7 19 2
3 7 3
Sample Output 1
6 3
Solution:
public class SaveThePrisoner {
static int saveThePrisoner(int n, int m, int s) {
int r = m % n;
if ((r + s  1) % n == 0) {
return n;
} else {
return ((r + s  1) % n);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int k = 0; k < T; k++) {
int N = sc.nextInt();
int M = sc.nextInt();
int S = sc.nextInt();
System.out.println(saveThePrisoner(N, M, S));
}
sc.close();
}
}
24. Challenge: Jumping on the Clouds: Revisited
Aerith is playing a cloud hopping game. In this game, there are sequentially numbered clouds that can be thunderheads or cumulus clouds. Her character must jump from cloud to cloud until it reaches the start again.
To play, Aerith is given an array of clouds, c and an energy level e = 100. She starts from c[0] and uses 1 unit of energy to make a jump of size k to cloud c[(i + k) % n]. If Aerith lands on a thundercloud, c[i] = 1, her energy (e) decreases by 2 additional units. The game ends when Aerith lands back on cloud 0.
Given the values of n, k, and the configuration of the clouds as an array , can you determine the final value of e after the game ends?
For example, give c = [0,0,1,0] and k = 2, the indices of her path are 0 > 2 > 0. Her energy level reduces by 1 for each jump to 98. She landed on one thunderhead at an additional cost of 2 energy units. Her final energy level is 96.
Note: Recall that % refers to the modulo operation. In this case, it serves to make the route circular. If Aerith is at c[n1] and jumps 1, she will arrive at c[0].
Function Description
Complete the jumpingOnClouds function in the editor below. It should return an integer representing the energy level remaining after the game.
jumpingOnClouds has the following parameter(s):
 c: an array of integers representing cloud types
 k: an integer representing the length of one jump
Input Format
The first line contains two spaceseparated integers, n and k, the number of clouds and the jump distance.
The second line contains n spaceseparated integers c[i] where 0 ≤ i ≤ n. Each cloud is described as follows:
 If ,c[i] = 0 then cloud i is a cumulus cloud.
 If ,c[i] = 1 then cloud i is a thunderhead.
Constraints

2 ≤ n ≤ 25

1≤ k ≤ n
 n % k = 0
 c[i] ε {0,1}
Output Format
Print the final value of e on a new line.
Sample Input
8 2
0 0 1 0 0 1 1 0
Sample Output
92
Solution:
public class JumpingOnTheCloudsRevisited {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int E = 100;
int k = sc.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
if (k == n) {
E = E  3;
} else {
if (a[k] == 1) {
E = E  3;
} else {
E = E  1;
}
for (int i = k; (i + k) % n != 0; i = (i + k)) {
if (a[(i + k) % n] == 1) {
E = E  3;
} else if (a[(i + k) % n] == 0) {
E = E  1;
}
}
if (a[0] == 1) {
E = E  3;
} else {
E = E  1;
}
}
System.out.println(E);
sc.close();
}
}
25. Challenge: Counting Valleys
Gary is an avid hiker. He tracks his hikes meticulously, paying close attention to small details like topography. During his last hike he took exactly n steps. For every step he took, he noted if it was an uphill, U, or a downhill, D step. Gary’s hikes start and end at sea level and each step up or down represents a 1 unit change in altitude. We define the following terms:
 A mountain is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level.
 A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.
Given Gary’s sequence of up and down steps during his last hike, find and print the number of valleys he walked through.
For example, if Gary’s path is s = [DDUUUUDD], he first enters a valley 2 units deep. Then he climbs out an up onto a mountain 2 units high. Finally, he returns to sea level and ends his hike.
Function Description
Complete the countingValleys function in the editor below. It must return an integer that denotes the number of valleys Gary traversed.
countingValleys has the following parameter(s):
 n: the number of steps Gary takes
 s: a string describing his path
The first line contains an integer n, the number of steps in Gary’s hike.
The second line contains a single string s, of n characters that describe his path.
Constraints

2≤ n ≤ 10^{6}
 s[i] ε {UD}
Output Format
Print a single integer that denotes the number of valleys Gary walked through during his hike.
Sample Input
8
UDDDUDUU
Sample Output
1
Solution:
public class CountingValleys {
static int countingValleys(int n, String s) {
int valleyCounter = 0, altitude = 0;
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (ch == 'U') {
altitude++;
if (altitude == 0) {
valleyCounter++;
}
} else {
altitude;
}
}
return valleyCounter;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String str = sc.next();
System.out.println(countingValleys(n, str));
sc.close();
}
}
26. Challenge: Viral Advertising
HackerLand Enterprise is adopting a new viral advertising strategy. When they launch a new product, they advertise it to exactly people on social media.
On the first day, half of those 5 people (i.e., floor(5/2)=2) like the advertisement and each shares it with 3 of their friends. At the beginning of the second day, floor(5/2) x 3 = 6 people receive the advertisement.
Each day, floor(recipients/2) of the recipients like the advertisement and will share it with 3 friends on the following day. Assuming nobody receives the advertisement twice, determine how many people have liked the ad by the end of a given day, beginning with launch day as day 1.
For example, assume you want to know how many have liked the ad by the end of the 5^{th }day.
Day Shared Liked Cumulative
1 5 2 2
2 6 3 5
3 9 4 9
4 12 6 15
5 18 9 24
The cumulative number of likes is 24.
Function Description
Complete the viralAdvertising function in the editor below. It should return the cumulative number of people who have liked the ad at a given time.
viralAdvertising has the following parameter(s):
 n: the integer number of days
Input Format
A single integer,n , denoting a number of days.
Constraints

1 ≤ n ≤ 50
Output Format
Print the number of people who liked the advertisement during the first days.
Sample Input
3
Sample Output
9
Solution:
public class ViralAdvertising {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum = 0;
int p = 5;
for (int i = 0; i < n; i++) {
p = (int) Math.floor(p / 2);
sum += p;
p = p * 3;
}
System.out.println(sum);
sc.close();
}
}
27. Challenge: Beautiful Days at the Movies
Lily likes to play games with integers. She has created a new game where she determines the difference between a number and its reverse. For instance, given the number 12, its reverse is 21. Their difference is 9. The number 120 reversed is 21, and their difference is 99.
She decides to apply her game to decision making. She will look at a numbered range of days and will only go to a movie on a beautiful day.
Given a range of numbered days, [i…j] and a number k, determine the number of days in the range that are beautiful. Beautiful numbers are defined as numbers where i – reverse(i) is evenly divisible by k. If a day’s value is a beautiful number, it is a beautiful day. Print the number of beautiful days in the range.
Function Description
Complete the beautifulDays function in the editor below. It must return the number of beautiful days in the range.
beautifulDays has the following parameter(s):
 i: the starting day number
 j: the ending day number
 k: the divisor
Input Format
A single line of three spaceseparated integers describing the respective values of i, j, and k.
Constraints

1 ≤ i ≤ j ≤ 2 x 10^{6}

1 ≤ k ≤ 2 x 10^{9}
Output Format
Print the number of beautiful days in the inclusive range between i and j.
Sample Input
20 23 6
Sample Output
2
public class BeautifulDaysAtTheMovies {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int i = sc.nextInt();
int j = sc.nextInt();
int k = sc.nextInt();
int count = 0;
for (int m = i; m < j; m++) {
int reversedString = getReversed(m);
if ((reversedString  m) % k == 0) {
count++;
}
}
System.out.println(count);
sc.close();
}
private static int getReversed(int i) {
String str = i + "";
String newValue = "";
for (int k = str.length()  1; k >= 0; k) {
newValue = newValue + str.charAt(k);
}
return Integer.parseInt(newValue);
}
}
28. Challenge: Electronics Shop
Monica wants to buy a keyboard and a USB drive from her favorite electronics store. The store has several models of each. Monica wants to spend as much as possible for the 2 items, given her budget.
Given the price lists for the store’s keyboards and USB drives, and Monica’s budget, find and print the amount of money Monica will spend. If she doesn’t have enough money to both a keyboard and a USB drive, print 1
instead. She will buy only the two required items.
For example, suppose she has b = 60 to spend. Three types of keyboards cost keyboards = [40,50,60]. Two USB drives cost drives= [5,8,12]. She could purchase a 40 keyboards + 12 drives = 52, or a 50 keyboards + 8 drives = 58. She chooses the latter. She can’t buy more than 2 items so she can’t spend exactly 60.
Function Description
Complete the getMoneySpent function in the editor below. It should return the maximum total price for the two items within Monica’s budget, or 1 if she cannot afford both items.
getMoneySpent has the following parameter(s):
 keyboards: an array of integers representing keyboard prices
 drives: an array of integers representing drive prices
 b: the units of currency in Monica’s budget
Input Format
The first line contains three spaceseparated integers b, n, and m, her budget, the number of keyboard models and the number of USB drive models.
The second line contains n spaceseparated integers keyboard[i], the prices of each keyboard model.
The third line contains m spaceseparated integers drives, the prices of the USB drives.
Constraints

1≤ n, m≤ 1000

1 ≤ b ≤ 10^{6}
 The price of each item is in the inclusive range [1, 10^{6}].
Output Format
Print a single integer denoting the amount of money Monica will spend. If she doesn’t have enough money to buy one keyboard and one USB drive, print 1
instead.
Sample Input 0
10 2 3
3 1
5 2 8
Sample Output 0
9
Solution:
public class ElectronicsShop {
static int getMoneySpent(int[] keyboards, int[] drives, int s) {
int max = 0;
int kb = 0, mo = 0;
for (int i = 0; i < keyboards.length; i++) {
for (int j = 0; j < drives.length; j++) {
int tmp = keyboards[i] + drives[j];
if (tmp >= max && tmp <= s) {
kb = i;
mo = j;
max = tmp;
}
}
}
return ((kb == 0 && mo == 0) ? 1 : max);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int s = in.nextInt();
int n = in.nextInt();
int m = in.nextInt();
int[] keyboards = new int[n];
for (int keyboards_i = 0; keyboards_i < n; keyboards_i++) {
keyboards[keyboards_i] = in.nextInt();
}
int[] drives = new int[m];
for (int drives_i = 0; drives_i < m; drives_i++) {
drives[drives_i] = in.nextInt();
}
// The maximum amount of money she can spend on a keyboard and USB drive, or 1
// if she can't purchase both items
int moneySpent = getMoneySpent(keyboards, drives, s);
System.out.println(moneySpent);
in.close();
}
}
29. Challenge: Cats and a Mouse
Two cats and a mouse are at various positions on a line. You will be given their starting positions. Your task is to determine which cat will reach the mouse first, assuming the mouse doesn’t move and the cats travel at equal speed. If the cats arrive at the same time, the mouse will be allowed to move and it will escape while they fight.
You are given q queries in the form of x, y, and z representing the respective positions for cats A and B, and for mouse C. Complete the function catAndMouse to return the appropriate answer to each query, which will be printed on a new line.
 If cat A catches the mouse first, print
Cat A
.  If cat B catches the mouse first, print
Cat B
.  If both cats reach the mouse at the same time, print
Mouse C
as the two cats fight and mouse escapes.
For example, cat A is at position x = 2 and cat B is at y = 5. If mouse C is at position z = 4, it is 2 units from cat A and 1 unit from cat B. Cat B will catch the mouse.
Function Description
Complete the catAndMouse function in the editor below. It should return one of the three strings as described.
catAndMouse has the following parameter(s):
 x: an integer, Cat A‘s position
 y: an integer, Cat B‘s position
 z: an integer, Mouse C‘s position
Input Format
The first line contains a single integer, q, denoting the number of queries.
Each of the q subsequent lines contains three spaceseparated integers describing the respective values of x (cat A‘s location), y (cat B‘s location), and z (mouse C‘s location).
Constraints

1≤ q ≤ 100

1≤ x,y,z ≤ 100
Output Format
For each query, return Cat A
if cat catches the mouse first, Cat B
if cat catches the mouse first, or Mouse C
if the mouse escapes.
Sample Input 0
2
1 2 3
1 3 2
Sample Output 0
Cat B Mouse C
Solution:
public class CatsAndAMouse {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int q = in.nextInt();
for (int a0 = 0; a0 < q; a0++) {
int x = in.nextInt();
int y = in.nextInt();
int z = in.nextInt();
int a = Math.abs(x  z);
int b = Math.abs(y  z);
if (a == b) {
System.out.println("Mouse C");
} else if (a > b) {
System.out.println("Cat B");
} else if (a < b) {
System.out.println("Cat A");
}
}
in.close();
}
}
30. Challenge: Day of the Programmer
Marie invented a Time Machine and wants to test it by timetraveling to visit Russia on the Day of the Programmer (the 256^{th }day of the year) during a year in the inclusive range from 1700 to 2700.
From 1700 to 1917, Russia’s official calendar was the Julian calendar; since 1919 they used the Gregorian calendar system. The transition from the Julian to Gregorian calendar system occurred in 1918, when the next day after January 31^{st }was February 14^{th}. This means that in 1918, February 14^{th} was the 32^{nd} day of the year in Russia.
In both calendar systems, February is the only month with a variable amount of days; it has 29 days during a leap year, and 28 days during all other years. In the Julian calendar, leap years are divisible by 4; in the Gregorian calendar, leap years are either of the following:
 Divisible by 400.
 Divisible by 4 and not divisible by 100.
Given a year, y, find the date of the 256^{th} day of that year according to the official Russian calendar during that year. Then print it in the format dd.mm.yyyy
, where dd
is the twodigit day, mm
is the twodigit month, and yyyy
is y.
For example, the given year = 1984. 1984 is divisible by 4, so it is a leap year. The 256^{th} day of a leap year after 1918 is September 12, so the answer is 12.09.1984.
Function Description
Complete the dayOfProgrammer function in the editor below. It should return a string representing the date of the 256^{th} day of the year given.
dayOfProgrammer has the following parameter(s):
 year: an integer
Input Format
A single integer denoting year y.
Constraints

1700 ≤ y ≤ 2700
Output Format
Print the full date of Day of the Programmer during year y in the format dd.mm.yyyy
, where dd
is the twodigit day, mm
is the twodigit month, and yyyy
is y.
Sample Input 0
2017
Sample Output 0
13.09.2017
Solution:
public class DayOfTheProgrammer {
public static void main(String[] args) throws ParseException {
Scanner sc = new Scanner(System.in);
int y = sc.nextInt();
SimpleDateFormat sdf = new SimpleDateFormat("dd.MM.yyyy");
int d = 243;
if (y >= 1700 && y <= 1917) {
if (y % 4 == 0) {
d = 244;
}
} else if (y >= 1919 && y <= 2700) {
if (y % 400 == 0  (y % 100 != 0 && y % 4 == 0)) {
d = 244;
}
} else if (y == 1918) {
d = 230;
}
int r = 256  d;
String date = r + "." + 9 + "." + y;
System.out.println(sdf.format(sdf.parse(date)));
sc.close();
}
}
31. Challenge: The Hurdle Race
Dan is playing a video game in which his character competes in a hurdle race. Hurdles are of varying heights, and Dan has a maximum height he can jump. There is a magic potion he can take that will increase his maximum height by 1 unit for each dose. How many doses of the potion must he take to be able to jump all of the hurdles.
Given an array of hurdle heights height, and an initial maximum height Dan can jump, k, determine the minimum number of doses Dan must take to be able to clear all the hurdles in the race.
For example, if height = [1,2,3,3,2] and Dan can jump 1 unit high naturally, he must take 3 – 1 = 2 doses of potion to be able to jump all of the hurdles.
Function Description
Complete the hurdleRace function in the editor below. It should return the minimum units of potion Dan needs to drink to jump all of the hurdles.
hurdleRace has the following parameter(s):
 k: an integer denoting the height Dan can jump naturally
 height: an array of integers denoting the heights of each hurdle
Input Format
The first line contains two spaceseparated integers n and k, the number of hurdles and the maximum height Dan can jump naturally.
The second line contains n spaceseparated integers height[i] where 0 ≤ i < n.
Constraints

1 ≤ n, k≤ 100

1 ≤ height[i], k ≤ 100
Output Format
Print an integer denoting the minimum doses of magic potion Dan must drink to complete the hurdle race.
Sample Input 0
5 4
1 6 3 5 2
Sample Output 0
2
Solution:
public class TheHurdleRace {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int sum = 0;
for (int height_i = 0; height_i < n; height_i++) {
int temp = in.nextInt();
if (temp > k) {
sum += (temp  k);
k = temp;
}
}
System.out.println(sum);
in.close();
}
}
32. Challenge: Utopian Tree
The Utopian Tree goes through 2 cycles of growth every year. Each spring, it doubles in height. Each summer, its height increases by 1 meter.
Laura plants a Utopian Tree sapling with a height of 1 meter at the onset of spring. How tall will her tree be after growth cycles?
For example, if the number of growth cycles is n = 5, the calculations are as follows:
Period Height
0 1
1 2
2 3
3 6
4 7
5 14
Function Description
Complete the utopianTree function in the editor below. It should return the integer height of the tree after the input number of growth cycles.
utopianTree has the following parameter(s):
 n: an integer, the number of growth cycles to simulate
Input Format
The first line contains an integer, t, the number of test cases.
t subsequent lines each contain an integer, n, denoting the number of cycles for that test case.
Constraints
1 ≤ t ≤ 10
0 ≤ n ≤ 60
Output Format
For each test case, print the height of the Utopian Tree after cycles. Each height must be printed on a new line.
Sample Input
3
1
4
Sample Output
1 2 7
Solution:
public class UtopianTree {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
int height = 1;
for (int i = 0; i < T; i++) {
int c = sc.nextInt();
for (int j = 1; j <= c; j++) {
if ((j & 1) == 1) {
height *= 2;
} else {
height++;
}
}
System.out.println(height);
height = 1;
}
sc.close();
}
}
33. Challenge: Service Lane
Calvin is driving his favorite vehicle on the 101 freeway. He notices that the check engine light of his vehicle is on, and he wants to service it immediately to avoid any risks. Luckily, a service lane runs parallel to the highway. The service lane varies in width along its length.
You will be given an array of widths at points along the road (indices), then a list of the indices of entry and exit points. Considering each entry and exit point pair, calculate the maximum size vehicle that can travel that segment of the service lane safely.
For example, n = 4 there are measurements yielding width = [2,3,2,1]. If our entry index, i = 1 and our exit, j = 2, there are two segment widths of 2 and 3 respectively. The widest vehicle that can fit through both is 2. If i = 2 and j = 4, our widths are [3,2,1] which limits vehicle width to 1.
Function Description
Complete the serviceLane function in the editor below. It should return an array of integers representing the maximum width vehicle that can pass through each segment of the highway described.
serviceLane has the following parameter(s):
 n: an integer denoting the size of the array
 cases: a two dimensional array of integers where each element is an array of two integers representing starting and ending indices for a segment to consider .
Input Format
The first line of input contains two integers, n and t, where n denotes the number of width measurements you will receive and t the number of test cases. The next line has n spaceseparated integers which represent the array width[w_{0, }w_{1},…,w_{n1}].
The next t lines contain two integers, i and j, where i is the start index and j is the end index of the segment being considered.
Constraints

2 ≤ n ≤ 100000

1 ≤ t ≤ 1000

0 ≤ i < j < n

2 ≤ j – i + 1 ≤ min(n,1000)

1 ≤ width[k] ≤ 3 where 0 ≤ k ≤ n
Output Format
For each test case, print the number that represents the largest vehicle type that can pass through the entire segment of the service lane between indexes i and j inclusive.
Sample Input
8 5
2 3 1 2 3 2 3 3
0 3
4 6
6 7
3 5
0 7
Sample Output
1 2 3 2 1
Solution:
public class ServiceLane {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int q = sc.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
for (int i = 0; i < q; i++) {
int b = sc.nextInt();
int c = sc.nextInt();
int min = Integer.MAX_VALUE;
for (int k = b; k <= c; k++) {
min = Math.min(min, a[k]);
}
System.out.println(min);
}
sc.close();
}
}
34. Challenge: Circular Array Rotation
John Watson knows of an operation called a right circular rotation on an array of integers. One rotation operation moves the last array element to the first position and shifts all remaining elements right one. To test Sherlock’s abilities, Watson provides Sherlock with an array of integers. Sherlock is to perform the rotation operation a number of times then determine the value of the element at a given position.
For each array, perform a number of right circular rotations and return the value of the element at a given index.
For example, array a = [3,4,5], number of rotations, k = 2 and indices to check, m = [1,2] .
First we perform the two rotations:
[3,4,5] > [5,3,4] > [4,5,3]
Now return the values from the zerobased indices and as indicated in the array.
a[1] = 5
a[2] = 3
Function Description
Complete the circularArrayRotation function in the editor below. It should return an array of integers representing the values at the specified indices.
circularArrayRotation has the following parameter(s):
 a: an array of integers to rotate
 k: an integer, the rotation count
 queries: an array of integers, the indices to report
Input Format
The first line contains 3 spaceseparated integers, n, k, and q, the number of elements in the integer array, the rotation count and the number of queries.
The second line contains n spaceseparated integers, where each integer i describes array element a[i] (where o ≤ i ≤ n).
Each of the q subsequent lines contains a single integer denoting m, the index of the element to return from a.
Constraints

1 ≤ n ≤ 10^{5}

1 ≤ a[i] ≤ 10^{5}

1 ≤ k ≤ 10^{5}

1 ≤ q ≤ 500

0 ≤ m ≤ n
Output Format
For each query, print the value of the element at index m of the rotated array on a new line.
Sample Input 0
3 2 3
1 2 3
0
1
2
Sample Output 0
2 3 1
Solution:
public class CircularArrayRotation {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int q = sc.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
rotateArray(a, k);
for (int i = 0; i < q; i++) {
System.out.println(a[sc.nextInt()]);
}
sc.close();
}
private static void rotateArray(int[] a, int k) {
if (a.length == 0  a == null  k < 0) {
return;
}
k = k > a.length ? k % a.length : k;
int l = a.length  k;
reverse(a, 0, l  1);
reverse(a, l, a.length  1);
reverse(a, 0, a.length  1);
}
private static void reverse(int[] a, int i, int j) {
while (i <= j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j;
}
}
}
35. Challenge: Sherlock and Squares
Watson likes to challenge Sherlock’s math ability. He will provide a starting and ending value describing a range of integers. Sherlock must determine the number of square integers within that range, inclusive of the endpoints.
Note: A square integer is an integer which is the square of an integer, e.g. 1,4,9,16,25.
For example, the range is a = 24 and b = 49, inclusive. There are three square integers in the range: 25, 36 and 49.
Function Description
Complete the squares function in the editor below. It should return an integer representing the number of square integers in the inclusive range from a to b.
squares has the following parameter(s):
 a: an integer, the lower range boundary
 b: an integer, the uppere range boundary
Input Format
The first line contains q, the number of test cases.
Each of the next q lines contains two spaceseparated integers denoting a and b, the starting and ending integers in the ranges.
Constraints
1≤ q ≤ 100
1 ≤ a ≤ b ≤ 10^{9}
Output Format
For each test case, print the number of square integers in the range on a new line.
Sample Input
2
3 9
17 24
Sample Output
2 0
Solution:
public class SherlockAndSquares {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int A = sc.nextInt();
int B = sc.nextInt();
int count = 0;
count = (int) Math.floor(Math.sqrt(B))  (int) Math.ceil(Math.sqrt(A)) + 1;
System.out.println(count);
}
sc.close();
}
}
36. Challenge: Angry Professor
A Discrete Mathematics professor has a class of students. Frustrated with their lack of discipline, he decides to cancel class if fewer than some number of students are present when class starts. Arrival times go from on time (arrivalTime ≤ 0) to arrived late (arrivalTime > 0).
Given the arrival time of each student and a threshhold number of attendees, determine if the class is canceled.
Input Format
The first line of input contains t, the number of test cases.
Each test case consists of two lines.
The first line has two spaceseparated integers, n and k, the number of students (size of a) and the cancellation threshold.
The second line contains n spaceseparated integers (a[1],a[2],…,a[n]) describing the arrival times for each student.
Note: Nonpositive arrival times (a[i] ≤ 0) indicate the student arrived early or on time; positive arrival times (a[i] > 0) indicate the student arrived minutes late.
For example, there are n = 6 students who arrive at times a = [1,1,0,0,1,1]. Four are there on time, and two arrive late. If there must be k = 4 for class to go on, in this case the class will continue. If there must be k = 5, then class is cancelled.
Function Description
Complete the angryProfessor function in the editor below. It must return YES
if class is cancelled, or NO
otherwise.
angryProfessor has the following parameter(s):
 k: the threshold number of students
 a: an array of integers representing arrival times
Constraints

1≤ t ≤ 10

1≤ n ≤ 1000

1≤ k ≤ n

100≤ a[i] ≤ 100, where i ε [1,…n]
Output Format
For each test case, print the word YES
if the class is canceled or NO
if it is not.
Note
If a student arrives exactly on time (ai = 0), the student is considered to have entered before the class started.
Sample Input
2
4 3
1 3 4 2
4 2
0 1 2 1
Sample Output
YES NO
Solution:
public class AngryProfessor {
static String angryProfessor(int k, int[] a) {
int count = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] <= 0) {
count++;
}
}
return ((count >= k) ? "NO" : "YES");
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for (int a0 = 0; a0 < t; a0++) {
int n = in.nextInt();
int k = in.nextInt();
int a[] = new int[n];
for (int a_i = 0; a_i < n; a_i++) {
a[a_i] = in.nextInt();
}
System.out.println(angryProfessor(k, a));
}
in.close();
}
}
37. Challenge: Extra Long Factorials
The factorial of the integer n, written n!, is defined as:
Calculate and print the factorial of a given integer.
For example, if n = 30, we calculate 30 x 29 x 28 x … x 2 x 1 and get .
Function Description
Complete the extraLongFactorials function in the editor below. It should print the result and return.
extraLongFactorials has the following parameter(s):
 n: an integer
Note: Factorials of n > 20 can’t be stored even in a 64 – bit long long variable. Big integers must be used for such calculations. Languages like Java, Python, Ruby etc. can handle big integers, but we need to write additional code in C/C++ to handle huge values.
We recommend solving this challenge using BigIntegers.
Input Format
Input consists of a single integer n
Constraints
1≤ n ≤ 100
Output Format
Print the factorial of n.
Sample Input
Sample Output
15511210043330985984000000
Solution:
public class ExtraLongFactorials {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
BigInteger b = BigInteger.ONE;
while (n >= 1) {
b = b.multiply(new BigInteger(n + ""));
n;
}
System.out.println(b);
in.close();
}
}
38. Challenge: Minimum Distances
We define the distance between two array values as the number of indices between the two values. Given a, find the minimum distance between any pair of equal elements in the array. If no such value exists, print 1.
For example, if a = [3,2,1,2,3], there are two matching pairs of values: 3 and 2. The indices of the 3‘s are i = 0 and j = 4, so their distance is d[i,j] = [j – i] = 4. The indices of the 2‘s are i =1 and j = 3, so their distance is d[i,j] = [j – i] = 2.
Function Description
Complete the minimumDistances function in the editor below. It should return the minimum distance between any two matching elements.
minimumDistances has the following parameter(s):
 a: an array of integers
Input Format
The first line contains an integer n, the size of array a.
The second line contains n spaceseparated integers a[i].
Constraints

1 ≤ n ≤ 10^{3}

1 ≤ a[i] ≤ 10^{5}
Output Format
Print a single integer denoting the minimum d[i,j] in a. If no such value exists, print 1.
Sample Input
6
7 1 3 4 1 7
Sample Output
3
Solution:
public class MinimumDistances {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
HashMap<Integer, Integer> hmap = new HashMap<>();
int min = Integer.MAX_VALUE, si = 0, ei = 0;
for (int i = 0; i < n; i++) {
if (hmap.containsKey(a[i])) {
ei = i;
si = hmap.get(a[i]);
if (min > (ei  si)) {
min = ei  si;
}
} else {
hmap.put(a[i], i);
}
}
System.out.println(min == Integer.MAX_VALUE ? 1 : min);
sc.close();
}
}
39. Challenge: NonDivisible Subset
Given a set of distinct integers, print the size of a maximal subset of S where the sum of any 2 numbers in S’ is not evenly divisible by k.
For example, the array S = [19,10,12,10,24,25,22] and k = 4. One of the arrays that can be created is S'[0] = [10,12,25]. Another is S'[1] = [19,22,24]. After testing all permutations, the maximum length solution array has 3 elements.
Function Description
Complete the nonDivisibleSubset function in the editor below. It should return an integer representing the length of the longest subset of S meeting the criteria.
nonDivisibleSubset has the following parameter(s):
 S: an array of integers
 k: an integer
Input Format
The first line contains 2 spaceseparated integers, n and k, the number of values in S and the non factor.
The second line contains n spaceseparated integers describing S[i], the unique values of the set.
Constraints

1 ≤ n ≤ 10^{5}

1 ≤ k ≤ 100

1 ≤ S[i] ≤ 10^{9}
 All of the given numbers are distinct.
Output Format
Print the size of the largest possible subset (S’).
Sample Input
4 3
1 7 2 4
Sample Output
3
Solution:
public class NonDivisibleSubset {
static int nonDivisibleSubset(int k, int[] arr) {
int reminders[] = new int[k];
for (int i = 0; i < arr.length; i++) {
int num = arr[i];
int index = num % k;
reminders[index]++;
}
int size = 0;
for (int i = 1; i <= k / 2; i++) {
if (i * 2 == k) {
size++;
} else {
size += Math.max(reminders[i], reminders[k  i]);
}
}
return reminders[0] != 0 ? size + 1 : size;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int[] arr = new int[n];
for (int arr_i = 0; arr_i < n; arr_i++) {
arr[arr_i] = in.nextInt();
}
int result = nonDivisibleSubset(k, arr);
System.out.println(result);
in.close();
}
}
40. Challenge: Beautiful Triplets
Given a sequence of integers a, a triplet(a[i],a[j],a[k]) is beautiful if:
 i<j<k
 a[j] – a[i] = a[k] – a[j] = d
Given an increasing sequenc of integers and the value of , count the number of beautiful triplets in the sequence.
For example, the sequence arr = [2,2,3,4,5] and d = 1. There are three beautiful triplets, by index: [i,j,k] = [0,2,3],[1,2,3],[2,3,4] . To test the first triplet, arr[j] – arr[i] = 3 – 2 = 1 and arr[k] – arr[j] = 4 – 3 = 1.
Function Description
Complete the beautifulTriplets function in the editor below. It must return an integer that represents the number of beautiful triplets in the sequence.
beautifulTriplets has the following parameters:
 d: an integer
 arr: an array of integers, sorted ascending
Input Format
The first line contains 2 spaceseparated integers n and d, the length of the sequence and the beautiful difference.
The second line contains n spaceseparated integers arr[i].
Constraints

1 ≤ n ≤ 10^{4}

1 ≤ d ≤ 20

0 ≤ arr[i] ≤ 2 x 10^{4}

arr[i] > arr[i – 1]
Output Format
Print a single line denoting the number of beautiful triplets in the sequence.
Sample Input
7 3
1 2 4 5 7 8 10
Sample Output
3
Solution:
public class ExtraLongFactorials {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
BigInteger b = BigInteger.ONE;
while (n >= 1) {
b = b.multiply(new BigInteger(n + ""));
n;
}
System.out.println(b);
in.close();
}
}
41. Challenge: Jumping on the Clouds
Emma is playing a new mobile game that starts with consecutively numbered clouds. Some of the clouds are thunderheads and others are cumulus. She can jump on any cumulus cloud having a number that is equal to the number of the current cloud plus 1 or 2. She must avoid the thunderheads. Determine the minimum number of jumps it will take Emma to jump from her starting postion to the last cloud. It is always possible to win the game.
For each game, Emma will get an array of clouds numbered 0 if they are safe or 1 if they must be avoided. For example,c = [0,1,0,0,0,1,0] indexed from 0…6. The number on each cloud is its index in the list so she must avoid the clouds at indexes 1 and 5. She could follow the following two paths: 0 > 2 > 4 > 6 or 0 > 2 >3>4>6. The first path takes 3 jumps while the second takes 4.
Function Description
Complete the jumpingOnClouds function in the editor below. It should return the minimum number of jumps required, as an integer.
jumpingOnClouds has the following parameter(s):
 c: an array of binary integers
Input Format
The first line contains an integer n, the total number of clouds. The second line contains n spaceseparated binary integers describing clouds c[i] where 0 ≤ i ≤ n .
Constraints

2 ≤ n ≤ 100

c[i] ε {0,1}
 c[0] = c[n1] = 0
Output Format
Print the minimum number of jumps needed to win the game.
Sample Input 0
7
0 0 1 0 0 1 0
Sample Output 0
4
Solution:
public class JumpingOnTheClouds {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n + 2];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int count = 0;
for (int i = 0; i < n  1;) {
if (a[i + 2] != 1) {
i++;
}
i++;
count++;
}
System.out.println(count);
sc.close();
}
}
42. Challenge: Equalize the Array
Karl has an array of integers. He wants to reduce the array until all remaining elements are equal. Determine the minimum number of elements to delete to reach his goal.
For example, if his array is arr = [1,2,2,3], we see that he can delete the 2 elements 1 and 3 leaving arr = [2,2]. He could also delete both twos and either the 1 or the 3, but that would take 3 deletions. The minimum number of deletions is 2.
Function Description
Complete the equalizeArray function in the editor below. It must return an integer that denotes the minimum number of deletions required.
equalizeArray has the following parameter(s):
 arr: an array of integers
Input Format
The first line contains an integer n, the number of elements in arr.
The next line contains n spaceseparated integers arr[i].
Constraints

1≤ n ≤ 100

1≤ arr[i] ≤ 100
Output Format
Print a single integer that denotes the minimum number of elements Karl must delete for all elements in the array to be equal.
Sample Input
5
3 3 2 1 3
Sample Output
2
Soution:
public class EqualizeTheArray {
static int equalizeArray(int[] arr) {
int len = arr.length;
int aux[] = new int[101];
for (int i = 0; i < len; i++) {
int index = arr[i];
aux[index]++;
}
int maxFreqCount = getMaxFreqCount(aux);
return len  maxFreqCount;
}
private static int getMaxFreqCount(int[] aux) {
int maxFreqCount = Integer.MIN_VALUE;
for (int freqCount : aux) {
if (freqCount > maxFreqCount) {
maxFreqCount = freqCount;
}
}
return maxFreqCount;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
System.out.println(equalizeArray(a));
sc.close();
}
}
43. Challenge: Designer of PDF Viewers
When you select a contiguous block of text in a PDF viewer, the selection is highlighted with a blue rectangle. In this PDF viewer, each word is highlighted independently. For example:
In this challenge, you will be given a list of letter heights in the alphabet and a string. Using the letter heights given, determine the area of the rectangle highlight in mm^{2}
assuming all letters are 1mm wide.
For example, the highlighted word = torn. Assume the heights of the letters are t = 2, o = 1, r = 1 and n = 1. The tallest letter is 2 high and there are 4 letters. The hightlighted area will be 2*4 = 8mm^{2} so the answer is 8.
Function Description
Complete the designerPdfViewer function in the editor below. It should return an integer representing the size of the highlighted area.
designerPdfViewer has the following parameter(s):
 h: an array of integers representing the heights of each letter
 word: a string
Input Format
The first line contains 26 spaceseparated integers describing the respective heights of each consecutive lowercase English letter, ascii[az].
The second line contains a single word, consisting of lowercase English alphabetic letters.
Constraints
 1 ≤ h[?] ≤ 7, where ? is an English lowercase letter.
 word contains no more than 10 letters.
Output Format
Print a single integer denoting the area in mm^{2} of highlighted rectangle when the given word is selected. Do not print units of measure.
Sample Input 0
1 3 1 3 1 4 1 3 2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
abc
Sample Output 0
9
Solution:
public class DesignerPDFViewer {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a[] = new int[26];
for (int i = 0; i < 26; i++) {
a[i] = sc.nextInt();
}
int maxHeight = 0;
String word = sc.next();
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i)  'a';
if (a[index] > maxHeight) {
maxHeight = a[index];
}
}
System.out.println(maxHeight * word.length());
sc.close();
}
}
44. Challenge: Forming a Magic Square
We define a magic square to be an n x n matrix of distinct positive integers from 1 to n^{2} where the sum of any row, column, or diagonal of length n is always equal to the same number: the magic constant.
You will be given a 3 x 3 matrix s of integers in the inclusive range [1,9]. We can convert any digit a to any other digit b in the range [1,9] at cost of a – b. Given s, convert it into a magic square at minimal cost. Print this cost on a new line.
Note: The resulting magic square must contain distinct integers in the inclusive range [1,9].
For example, we start with the following matrix s:
5 3 4
1 5 8
6 4 2
We can convert it to the following magic square:
8 3 4
1 5 9
6 7 2
This took three replacements at a cost of 5 – 8 + 8 – 9 + 4 – 7 = 7.
Function Description
Complete the formingMagicSquare function in the editor below. It should return an integer that represents the minimal total cost of converting the input square to a magic square.
formingMagicSquare has the following parameter(s):
 s: a 3 x 3 array of integers
Input Format
Each of the lines contains three spaceseparated integers of row s[i].
Constraints
 s[i][j] ε [1,9]
Output Format
Print an integer denoting the minimum cost of turning matrix into a magic square.
Sample Input 0
4 9 2
3 5 7
8 1 5
Sample Output 0
1
Soution:
public class FormingAMagicSquare {
static int formingMagicSquare(int[][] s) {
int[][][] magicSquareCombinations={ {{4,9,2},{3,5,7},{8,1,6}},
{{8,3,4},{1,5,9},{6,7,2}},
{{6,1,8},{7,5,3},{2,9,4}},
{{2,7,6},{9,5,1},{4,3,8}},
{{2,9,4},{7,5,3},{6,1,8}},
{{8,1,6},{3,5,7},{4,9,2}},
{{6,7,2},{1,5,9},{8,3,4}},
{{4,3,8},{9,5,1},{2,7,6}}};
int minCost = Integer.MAX_VALUE;
for (int i = 0; i < magicSquareCombinations.length; i++) {
int modifyCost = 0;
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
modifyCost += Math.abs(s[j][k]  magicSquareCombinations[i][j][k]);
}
}
minCost = Math.min(modifyCost, minCost);
}
return minCost;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[][] s = new int[3][3];
for(int s_i = 0; s_i < 3; s_i++){
for(int s_j = 0; s_j < 3; s_j++){
s[s_i][s_j] = in.nextInt();
}
}
int result = formingMagicSquare(s);
System.out.println(result);
in.close();
}
}
45. Challenge: Repeated String
Lilah has a string, s, of lowercase English letters that she repeated infinitely many times.
Given an integer, n, find and print the number of letter a
‘s in the first n letters of Lilah’s infinite string.
For example, if the string s = ‘abcac’ and n = 10, the substring we consider is abcacabcac, the first 10 characters of her infinite string. There are 4 occurrences of a
in the substring.
Function Description
Complete the repeatedString function in the editor below. It should return an integer representing the number of occurrences of a
in the prefix of length in the infinitely repeating string.
repeatedString has the following parameter(s):
 s: a string to repeat
 n: the number of characters to consider
Input Format
The first line contains a single string, s.
The second line contains an integer, n.
Constraints

1 ≤ s ≤ 100

1 ≤ n ≤ 10^{12}
 For 25% of the test cases, n ≤ 10^{6}.
Output Format
Print a single integer denoting the number of letter a
‘s in the first n letters of the infinite string created by repeating s infinitely many times.
Sample Input 0
aba
10
Sample Output 0
7
Solution:
public class RepeatedString {
public static long getLetterCount(String word, long length) {
long count = 0;
for (int i = 0; i < length; i++) {
if (word.charAt(i) == 'a')
count++;
}
return count;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String word = sc.next();
int l = word.length();
long freq = sc.nextLong();
long q = 0, r = 0;
q = freq / l;
r = freq % l;
long length = (r == 0) ? 0 : r;
long aCount = q * getLetterCount(word, word.length()) + getLetterCount(word, length);
System.out.println(aCount);
sc.close();
}
}
46. Challenge: Bitwise AND
Given set S = {1,2,3,…,N}. Find two integers, A and B (where A < B), from set S such that the value of A&B is the maximum possible and also less than a given integer, K. In this case, & represents the bitwise AND operator.
Input Format
The first line contains an integer, T, the number of test cases.
Each of the T subsequent lines defines a test case as 2 spaceseparated integers, N and K, respectively.
Constraints

1 ≤ T ≤ 10^{3}

2≤ N ≤ 10^{3}

2≤ K ≤ N
Output Format
For each test case, print the maximum possible value of b A&B on a new line.
Sample Input
3
5 2
8 5
2 2
Sample Output
1 4 0
Solution:
public class BitwiseAND {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int i = 0; i < T; i++) {
int N = sc.nextInt();
int K = sc.nextInt();
int result = getMaxValue(N, K);
System.out.println(result);
}
sc.close();
}
/**
* @param n
* @return
*/
private static int getMaxValue(int n, int k) {
if (((k  1)  k) <= n)
return k  1;
return k  2;
}
}
47. Challenge: Divisible Pairs Sum
You are given an array of n integers, a_{0,}a_{1},…,a_{n1}, and a positive integer, k. Find and print the number of (i,j) pairs where i < j and a_{i }+ a_{j} is evenly divisible by k.
Input Format
The first line contains 2 spaceseparated integers, n and k, respectively.
The second line contains n spaceseparated integers describing the respective values of .a_{0,}a_{1},…,a_{n1}
Constraints

2 ≤ n ≤ 100

1≤ k ≤ 100

1≤ a_{i} ≤ 100
Output Format
Print the number of (i,j) pairs where i < j and a_{i} + a_{j} is evenly divisible by k.
Sample Input
6 3
1 3 2 6 1 2
Sample Output
5
Solution:
public class DivisiblePairsSum {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();
int a[] = new int[M];
for (int i = 0; i < M; i++) {
a[i] = sc.nextInt();
}
int count = 0;
for (int i = 0; i < M; i++) {
for (int j = i + 1; j < M; j++) {
if ((a[i] + a[j]) % N == 0) {
count++;
}
}
}
System.out.println(count);
sc.close();
}
}
48. Challenge: Append and Delete
You have a string of lowercase English alphabetic letters. You can perform two types of operations on the string:
 Append a lowercase English alphabetic letter to the end of the string.
 Delete the last character in the string. Performing this operation on an empty string results in an empty string.
Given an integer, k , and two strings, s and t, determine whether or not you can convert s to t by performing exactly k of the above operations on s. If it’s possible, print Yes
. Otherwise, print No
.
For example, strings s = [a,b,c] and t = [d,e,f]. Our number of moves, k = 6. To convert s to t, we first delete all of the characters in 3 moves. Next we add each of the characters of t in order. On the 6^{th} move, you will have the matching string. If there had been more moves available, they could have been eliminated by performing multiple deletions on an empty string. If there were fewer than 6 moves, we would not have succeeded in creating the new string.
Function Description
Complete the appendAndDelete function in the editor below. It should return a string, either Yes
or No
.
appendAndDelete has the following parameter(s):
 s: the initial string
 t: the desired string
 k: an integer that represents the number of operations
Input Format
The first line contains a string s, the initial string.
The second line contains a string t, the desired final string.
The third line contains an integer k, the number of operations.
Constraints

1≤ s ≤ 100

1≤ t ≤ 100

1≤ k ≤ 100
 s and t consist of lowercase English alphabetic letters, ascii [az].
Output Format
Print Yes
if you can obtain string t by performing exactly k operations on s. Otherwise, print No
.
Sample Input 0
hackerhappy
hackerrank
9
Sample Output 0
Yes
Solution:
public class AppendAndDelete {
static String appendAndDelete(String s, String t, int k) {
String result = "No";
int sLength = s.length();
int tlength = t.length();
int len = sLength > tlength ? tlength : sLength;
int matchCharCount = 0;
for (int i = 0; i < len; i++) {
if (s.charAt(i) == t.charAt(i)) {
matchCharCount++;
} else {
break;
}
}
int minOpRequired = sLength + tlength  2 * matchCharCount;
if (k == minOpRequired) {
return result = "Yes";
} else if (k > minOpRequired && (k  minOpRequired) % 2 == 0  k >= (sLength + tlength)) {
result = "Yes";
}
return result;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.next();
String t = in.next();
int k = in.nextInt();
String result = appendAndDelete(s, t, k);
System.out.println(result);
in.close();
}
}
49. Challenge: Picking Numbers
Given an array of integers, find and print the maximum number of integers you can select from the array such that the absolute difference between any two of the chosen integers is less than or equal to 1. For example, if your array is a = [1,1,2,2,4,4,5,5,5], you can create two subarrays meeting the criterion: [1,1,2,2] and [4,4,5,5,5]. The maximum length subarray has 5 elements.
Function Description
Complete the pickingNumbers function in the editor below. It should return an integer that represents the length of the longest array that can be created.
pickingNumbers has the following parameter(s):
 a: an array of integers
Input Format
The first line contains a single integer n, the size of the array a.
The second line contains n spaceseparated integers a[i].
Constraints

2 ≤ n ≤ 100

0≤ a[i] < 100
 The answer will be > 2.
Output Format
A single integer denoting the maximum number of integers you can choose from the array such that the absolute difference between any two of the chosen integers is ≤ 1.
Sample Input 0
6
4 6 5 3 3 1
Sample Output 0
3
Solution:
public class PickingNumbers {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Map<Integer, Integer> hmap = new HashMap<Integer, Integer>();
int n = sc.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
if (hmap.containsKey(a[i])) {
hmap.put(a[i], hmap.get(a[i]) + 1);
} else {
hmap.put(a[i], 1);
}
}
Set<Entry<Integer, Integer>> s = hmap.entrySet();
List<Entry<Integer, Integer>> list = new ArrayList<Entry<Integer, Integer>>(s);
Collections.sort(list, new Comparator<Entry<Integer, Integer>>() {
@Override
public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
return o2.getValue()  o1.getValue();
}
});
int ksum = 0;
for (int i = 0; i < list.size(); i++) {
int key1 = list.get(i).getKey();
int value1 = list.get(i).getValue();
int key2 = hmap.containsKey(key1  1) ? hmap.get(key1  1) : 0;
int key3 = hmap.containsKey(key1 + 1) ? hmap.get(key1 + 1) : 0;
int count = key2 > key3 ? key2 : key3;
int tmp = value1 + count;
if (ksum < tmp) {
ksum = tmp;
}
}
System.out.println(ksum);
sc.close();
}
}
50. Challenge: Climbing the Leaderboard
Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. The game uses Dense Ranking, so its leaderboard works like this:
 The player with the highest score is ranked number 1 on the leaderboard.
 Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number.
For example, the four players on the leaderboard have high scores of 100, 90 , 90and 80. Those players will have ranks 1, 2, 2, and 3, respectively. If Alice’s scores are 70, 80 and 105, her rankings after each game are 4^{th} , 3^{rd} and 1^{st}.
Function Description
Complete the climbingLeaderboard function in the editor below. It should return an integer array where each element represents Alice’s rank after the j^{th} game.
climbingLeaderboard has the following parameter(s):
 scores: an array of integers that represent leaderboard scores
 alice: an array of integers that represent Alice’s scores
Input Format
The first line contains an integer n, the number of players on the leaderboard.
The next line contains n spaceseparated integers scores[i], the leaderboard scores in decreasing order.
The next line contains an integer, m, denoting the number games Alice plays.
The last line contains m spaceseparated integers alice[j], the game scores.
Constraints

1 ≤ n ≤ 2 x 10^{5}

1 ≤ m ≤ 2 x 10^{5}

0 ≤ scores[i] ≤ 10^{9 }for 0 ≤ i ≤ n

0 ≤ alice[j] ≤ 10^{9 }for 0 ≤ j ≤ m
 The existing leaderboard, scores, is in descending order.
 Alice’s scores, alice, are in ascending order.
Subtask
For 60% of the maximum score:

1 ≤ n ≤ 200

1 ≤ m ≤ 200
Output Format
Print m integers. The j^{th} integer should indicate Alice’s rank after playing the j^{th} game.
Sample Input 1
100 100 50 40 40 20 10
4
5 25 50 120
Sample Output 1
4
2
1
public class ClimbingTheLeaderboard {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] scores = new int[n];
scores[0] = in.nextInt();
int k = 1, counter = 0;
for (int scores_i = 1; scores_i < n; scores_i++) {
int temp = in.nextInt();
if (temp != scores[k  1]) {
scores[k++] = temp;
} else {
counter++;
}
}
for (int i = scores.length  1; i >= 0 && counter > 0; i) {
counter;
scores[i] = Integer.MIN_VALUE;
}
int m = in.nextInt();
for (int alice_i = 0; alice_i < m; alice_i++) {
int tmp = in.nextInt();
if (tmp > scores[0]) {
System.out.println(1);
} else if (tmp < scores[scores.length  1]) {
System.out.println(scores.length + 1);
} else {
System.out.println(binarySearch(scores, tmp) + 1);
}
}
in.close();
}
private static int binarySearch(int[] a, int key) {
int lo = 0;
int hi = a.length  1;
while (lo <= hi) {
int mid = lo + (hi  lo) / 2;
if (a[mid] == key) {
return mid;
} else if (a[mid] < key && key < a[mid  1]) {
return mid;
} else if (a[mid] > key && key >= a[mid + 1]) {
return mid + 1;
} else if (a[mid] < key) {
hi = mid  1;
} else if (a[mid] > key) {
lo = mid + 1;
}
}
return 1;
}
}
51. Challenge: Sequence Equation
Given a sequence of n integers, p(1),p(2),…,p(n) where each element is distinct and satisfies 1 ≤ p(x) ≤ n. For each x where 1≤ x ≤ n, find any integer y such that p(p(y)) = x and print the value of y on a new line.
For example, assume the sequence p = [5,2,1,3,4]. Each value of x between 1 and 5, the length of the sequence, is analyzed as follows:
 x = 1 = p[3],p[4] = 3, so p[p[4]] = 1
 x = 2= p[2,p[2] = 2, so p[p[2]] = 2
 x = 1 = p[4],p[5] = 4, so p[p[5]] = 3
 x = 1 = p[5],p[1] = 5, so p[p[1]] = 4
 x = 1 = p[1],p[3] = 1, so p[p[3]] = 5
The values for y are [4,2,5,1,3] .
Function Description
Complete the permutationEquation function in the editor below. It should return an array of integers that represent the values of y.
permutationEquation has the following parameter(s):
 p: an array of integers
Input Format
The first line contains an integer n, the number of elements in the sequence.
The second line contains n spaceseparated integers p[i] where 1 ≤ i ≤ n.
Constraints

1 ≤ n ≤ 50

1 ≤ p[i] ≤ 50, where 1 ≤ i ≤ n.
 Each element in the sequence is distinct.
Output Format
For each x from 1 to n, print an integer denoting any valid y satisfying the equation p(p(y)) = x on a new line.
Sample Input 0
3
2 3 1
Sample Output 0
2 3 1
Solution:
public class SequenceEquation {
public static int getIndexOfIndex(int a[], int key, int j) {
if (j <= 0) {
return key;
} else {
for (int i = 0; i < a.length; i++) {
if (a[i] == key) {
return getIndexOfIndex(a, i, j);
}
}
}
return 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
for (int i = 1; i <= n; i++) {
System.out.println(getIndexOfIndex(a, i, 2));
}
sc.close();
}
}
52. Challenge: Find Digits
An integer d is a divisor of an integer n if the remainder of n / d = 0.
Given an integer, for each digit that makes up the integer determine whether it is a divisor. Count the number of divisors occurring within the integer.
Note: Each digit is considered to be unique, so each occurrence of the same digit should be counted (e.g. for n = 111, 1 is a divisor of 111 each time it occurs so the answer is 3).
Function Description
Complete the findDigits function in the editor below. It should return an integer representing the number of digits of d that are divisors of d.
findDigits has the following parameter(s):
 n: an integer to analyze
Input Format
The first line is an integer, t, indicating the number of test cases.
The t subsequent lines each contain an integer, n.
Constraints
1≤ t ≤ 15
0 < n < 10^{9}
Output Format
For every test case, count the number of digits in that are divisors of . Print each answer on a new line.
Sample Input
2
12
1012
Sample Output
2 3
Solution:
public class FindDigits {
static int findDigits(int n) {
int count = 0;
int num = n;
while (n > 0) {
int r = n % 10;
if (r != 0 && num % r == 0)
count++;
n = n / 10;
}
return count;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int input = sc.nextInt();
System.out.println(findDigits(input));
}
sc.close();
}
}
53. Challenge: Chocolate Feast
Little Bobby loves chocolate. He frequently goes to his favorite 5 & 10 store, Penny Auntie, to buy them. They are having a promotion at Penny Auntie. If Bobby saves enough wrappers, he can turn them in for a free chocolate.
For example, Bobby has n = 15 to spend on bars of chocolate that cost c = 3 each. He can turn in m = 2 wrappers to receive another bar. Initially, he buys 5 bars and has 5 wrappers after eating them. He turns in 4 of them, leaving him with 1, for 2 more bars. After eating those two, he has 3 wrappers, turns in 2 leaving him with 1 wrapper and his new bar. Once he eats that one, he has 2 wrappers and turns them in for another bar. After eating that one, he only has 1 wrapper, and his feast ends. Overall, he has eaten 5 + 2 + 1 + 1 = 9 bars.
Function Description
Complete the chocolateFeast function in the editor below. It must return the number of chocolates Bobby can eat after taking full advantage of the promotion.
chocolateFeast has the following parameter(s):
 n: an integer representing Bobby’s initial amount of money
 c: an integer representing the cost of a chocolate bar
 m: an integer representing the number of wrappers he can turn in for a free bar
Note: Little Bobby will always turn in his wrappers if he has enough to get a free chocolate.
Input Format
The first line contains an integer, t, denoting the number of test cases to analyze.
Each of the next t lines contains three spaceseparated integers: n, c, and m. They represent money to spend, cost of a chocolate, and the number of wrappers he can turn in for a free chocolate.
Constraints

1≤ t ≤ 1000

2 ≤ n ≤ 10^{5}

2 ≤ c ≤ n

2 ≤ m ≤ n
Output Format
For each trip to Penny Auntie, print the total number of chocolates Bobby eats on a new line.
Sample Input
3
10 2 5
12 4 4
6 2 2
Sample Output
6 3 5
Solution:
public class ChocolateFeast {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
int n = sc.nextInt();
int c = sc.nextInt();
int m = sc.nextInt();
int q = n / c;
int sum = 0;
sum = q;
while (q >= m) {
int w = q / m;
int r = q % m;
sum += w;
q = w + r;
}
System.out.println(sum);
}
sc.close();
}
}
54. Challenge: Cut the Sticks
You are given a number of sticks of varying lengths. You will iteratively cut the sticks into smaller sticks, discarding the shortest pieces until there are none left. At each iteration you will determine the length of the shortest stick remaining, cut that length from each of the longer sticks and then discard all the pieces of that shortest length. When all the remaining sticks are the same length, they cannot be shortened so discard them.
Given the lengths of n sticks, print the number of sticks that are left before each iteration until there are none left.
For example, there are n = 3 sticks of lengths arr = [1,2,3]. The shortest stick length is 1, so we cut that length from the longer two and discard the pieces of length 1. Now our lengths are arr = [1,2]. Again, the shortest stick is of length 1, so we cut that amount from the longer stick and discard those pieces. There is only one stick left, arr = [1], so we discard that stick. Our lengths are answer = [3,2,1].
Function Description
Complete the cutTheSticks function in the editor below. It should return an array of integers representing the number of sticks before each cut operation is performed.
cutTheSticks has the following parameter(s):
 arr: an array of integers representing the length of each stick
Input Format
The first line contains a single integer n, the size of arr.
The next line contains n spaceseparated integers, each an arr[i] where each value represents the length of the i^{th }stick.
Output Format
For each operation, print the number of sticks that are present before the operation on separate lines.
Constraints

1 ≤ n≤ 1000

1 ≤ arr[i] ≤ 1000
Sample Input 0
6
5 4 4 2 2 8
Sample Output 0
6 4 2 1
Solution:
public class CutTheSticks {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int tSum = 1;
while (tSum != 0) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (min > a[i] && a[i] != 0) {
min = a[i];
}
}
int count = 0;
tSum = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= min) {
a[i] = a[i]  min;
count++;
}
tSum += +a[i];
}
System.out.println(count);
}
sc.close();
}
}
55. Challenge: ACM ICPC
There are a number of people who will be attending ACMICPC World Finals. Each of them may be well versed in a number of topics. Given a list of topics known by each attendee, you must determine the maximum number of topics a 2person team can know. Also find out how many ways a team can be formed to know that many topics. Lists will be in the form of bit strings, where each string represents an attendee and each position in that string represents a field of knowledge, 1 if its a known field or 0 if not.
For example, given three attendees’ data as follows:
10101
11110
00010
These are all possible teams that can be formed:
Members Subjects
(1,2) [1,2,3,4,5]
(1,3) [1,3,4,5]
(2,3) [1,2,3,4]
In this case, the first team will know all 5 subjects. They are the only team that can be created knowing that many subjects.
Function Description
Complete the acmTeam function in the editor below. It should return an integer array with two elements: the maximum number of topics any team can know and the number of teams that can be formed that know that maximum number of topics.
acmTeam has the following parameter(s):
 topic: a string of binary digits
Input Format
The first line contains two spaceseparated integers n and m, where n represents the number of attendees and m represents the number of topics.
Each of the next n lines contains a binary string of length m. If the i^{th} line’s j^{th} character is 1, then the i^{th} person knows the j^{th}topic.
Constraints
2 ≤ n ≤ 500
1 ≤ m ≤ 500
Output Format
On the first line, print the maximum number of topics a 2person team can know.
On the second line, print the number of ways to form a 2person team that knows the maximum number of topics.
Sample Input
4 5
10101
11100
11010
00101
Sample Output
5 2
Solution:
public class ACMICPCTeam {
static int[] acmTeam(String[] topic) {
int teamCount = 0, maxTopic = 0;
int size = topic.length;
BitSet[] bitset = new BitSet[size];
for (int i = 0; i < size; i++) {
BigInteger b1 = new BigInteger(topic[i], 2);
bitset[i] = BitSet.valueOf(b1.toByteArray());
}
for (int i = 0; i < size  1; i++) {
BitSet bitset1 = bitset[i];
for (int j = i + 1; j < size; j++) {
BitSet bitset2 = bitset[j];
BitSet tmpset = new BitSet();
tmpset.or(bitset1);
tmpset.or(bitset2);
if (tmpset.cardinality() > maxTopic) {
maxTopic = tmpset.cardinality();
teamCount = 1;
} else if (maxTopic == tmpset.cardinality()) {
teamCount++;
}
}
}
int result[] = { maxTopic, teamCount };
return result;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
String[] topic = new String[n];
for (int topic_i = 0; topic_i < n; topic_i++) {
topic[topic_i] = in.next();
}
int[] result = acmTeam(topic);
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + (i != result.length  1 ? "\n" : ""));
}
System.out.println("");
in.close();
}
}
56. Challenge: Taum and B’day
Taum is planning to celebrate the birthday of his friend, Diksha. There are two types of gifts that Diksha wants from Taum: one is black and the other is white. To make her happy, Taum has to buy b black gifts and w white gifts.
 The cost of each black gift is bc units.
 The cost of every white gift is wc units.
 The cost of converting each black gift into white gift or vice versa is z units.
Help Taum by deducing the minimum amount he needs to spend on Diksha’s gifts.
For example, if Taum wants to buy b = 3 black gifts and w = 5 white gifts at a cost of bc = 3, wc = 4 and conversion cost z = 1, we see that he can buy a black gift for 3 and convert it to a white gift for 1, making the total cost of each white gift 4. That matches the cost of a white gift, so he can do that or just buy black gifts and white gifts. Either way, the overall cost is 3 * 3 + 5 * 4 = 29.
Function Description
Complete the function taumBday in the editor below. It should return the minimal cost of obtaining the desired gifts.
taumBday has the following parameter(s):
 b: the number of black gifts
 w: the number of white gifts
 bc: the cost of a black gift
 wc: the cost of a white gift
 z: the cost to convert one color gift to the other color
Input Format
The first line will contain an integer t, the number of test cases.
The next t pairs of lines are as follows:
– The first line contains the values of integers b and w.
– The next line contains the values of integers bc, wc, and z.
Constraints
1 ≤ t ≤ 10
0 ≤ b, w, bc, wc, z ≤ 10^{9}
Output Format
t lines, each containing an integer: the minimum amount of units Taum needs to spend on gifts.
Sample Input
5
10 10
1 1 1
5 9
2 3 4
3 6
9 1 1
7 7
4 2 1
3 3
1 9 2
Sample Output
20 37 12 35 12
Solution:
public class TaumAndBday {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for (int a0 = 0; a0 < t; a0++) {
long b = in.nextLong();
long w = in.nextLong();
long x = in.nextLong();
long y = in.nextLong();
long z = in.nextLong();
long cost = 0;
if (x > y + z) {
cost = b * (y + z) + w * y;
} else if (y > x + z) {
cost = b * x + w * (x + z);
} else {
cost = x * b + y * w;
}
System.out.println(cost);
}
in.close();
}
}
57. Challenge: The Time in Words
Given the time in numerals we may convert it into words, as shown below:
Function Description
Complete the timeInWords function in the editor below. It should return a time string as described.
timeInWords has the following parameter(s):
 h: an integer representing hour of the day
 m: an integer representing minutes after the hour
Input Format
The first line contains h, the hours portion The second line contains m, the minutes portion
Constraints

1≤ h ≤ 12

0≤ m ≤ 60
Output Format
Print the time in words as described.
Sample Input 0
5
47
Sample Output 0
thirteen minutes to six
Solution:
public class TheTimeInWords {
public static void main(String[] args) {
String[] words = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten",
"eleven", "twelve", "thirteen", "fourteen", "fiveten", "sixten", "seventen", "eighten", "ninten",
"twenty" };
Scanner in = new Scanner(System.in);
int h = in.nextInt();
int m = in.nextInt();
String str = m < 10 ? "minute" : "minutes";
if (m == 0) {
System.out.println(words[h] + " o' clock");
} else if (m == 15) {
System.out.println("quarter past " + words[h]);
} else if (m == 30) {
System.out.println("half past " + words[h]);
} else if (m > 0 && m < 30) {
String tmp = m <= 20 ? words[m] : words[20] + " " + words[m % 10];
System.out.println(tmp + " " + str + " past " + words[h]);
} else if (m == 45) {
System.out.println("quarter to " + words[++h]);
} else if (m > 30 && m < 60) {
m = 60  m;
String tmp = m <= 20 ? words[m] : words[20] + " " + words[m % 10];
System.out.println(tmp + " " + str + " to " + words[++h]);
}
in.close();
}
}
58. Challenge: Flatland Space Stations
Flatland is a country with a number of cities, some of which have space stations. Cities are numbered consecutively and each has a road of 1km length connecting it to the next city. It is not a circular route, so the first city doesn’t connect with the last city. Determine the maximum distance from any city to it’s nearest space station.
For example, there are n = 3 cities and m =1 of them has a space station, city 1. They occur consecutively along a route. City 2 is 2 – 1 =1 unit away and city 3 is 3 1 = 2 units away. City 1 is 0 units from its nearest space station as one is located there. The maximum distance is 2.
Function Description
Complete the flatlandSpaceStations function in the editor below. It should return an integer that represents the maximum distance any city is from a space station.
flatlandSpaceStations has the following parameter(s):
 n: the number of cities
 c: an integer array that contains the indices of cities with a space station, based indexing
Input Format
The first line consists of two spaceseparated integers, n and m.
The second line contains m spaceseparated integers, the indices of each city having a spacestation. These values are unordered and unique.
Constraints

1 ≤ n ≤ 10^{5}

1 ≤ m ≤ n
 There will be at least 1 city with a space station.
 No city has more than one space station.
Output Format
Print an integer denoting the maximum distance that an astronaut in a Flatland city would need to travel to reach the nearest space station.
Sample Input 0
5 2
0 4
Sample Output 0
1
Solution:
public class FlatlandSpaceStations {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
boolean spaceStations[] = new boolean[n];
for (int i = 0; i < m; i++) {
int index = sc.nextInt();
spaceStations[index] = true;
}
int result = getFlatLandStations(spaceStations);
System.out.println(n == m ? 0 : result);
sc.close();
}
/**
*
*
*/
private static int getFlatLandStations(boolean[] spaceStations) {
int n = spaceStations.length;
int maxDistance = 0;
int start = 0, end = n  1, distance = 0;
boolean firstFound = false;
for (int i = 0; i < n; i++) {
if (spaceStations[i]) {
if (!firstFound) {
maxDistance = Math.abs(start  i);
firstFound = true;
start = i;
} else {
distance = Math.abs(i  start) / 2;
start = i;
}
maxDistance = Math.max(distance, maxDistance);
}
}
if (end  start > 1) {
distance = Math.abs(start  end);
}
maxDistance = Math.max(distance, maxDistance);
return maxDistance;
}
}
59. Challenge: Lisa’s Workbook
Lisa just got a new math workbook. A workbook contains exercise problems, grouped into chapters. Lisa believes a problem to be special if its index (within a chapter) is the same as the page number where it’s located. The format of Lisa’s book is as follows:
 There are n chapters in Lisa’s workbook, numbered from 1 to n.
 The i^{th }chapter has arr[i] problems, numbered from 1 to arr[i].
 Each page can hold up to k problems. Only a chapter’s last page of exercises may contain fewer than k problems.
 Each new chapter starts on a new page, so a page will never contain problems from more than one chapter.
 The page number indexing starts at 1.
Given the details for Lisa’s workbook, can you count its number of special problems?
For example, Lisa’s workbook contains arr[1]=4 problems for chapter 1, and arr[2] = 2 problems for chapter 2. Each page can hold k = 3 problems. The first page will hold 3 problems for chapter 1. Problem 1 is on page 1, so it is special. Page 2 contains only Chapter 1, Problem 4, so no special problem is on page 2. Chapter 2 problems start on page 3 and there are 2 problems. Since there is no problem 3 on page 3, there is no special problem on that page either. There is 1 special problem in her workbook.
Note: See the diagram in the Explanation section for more details.
Function Description
Complete the workbook function in the editor below. It should return an integer that represents the number of special problems in the workbook.
workbook has the following parameter(s):
 n: an integer that denotes the number of chapters
 k: an integer that denotes the maximum number of problems per page
 arr: an array of integers that denote the number of problems in each chapter
Input Format
The first line contains two integers n and k, the number of chapters and the maximum number of problems per page.
The second line contains n spaceseparated integers arr[i] where arr[i] denotes the number of problems in the i^{th} chapter.
Constraints

1≤ n,k,arr[i] ≤ 100
Output Format
Print the number of special problems in Lisa’s workbook.
Sample Input
5 3
4 2 6 1 10
Sample Output
4
Solution:
public class LisasWorkbook {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int a[] = new int[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
int result = getSepcialProblemCount(n, k, a);
System.out.println(result);
sc.close();
}
/**
* @param n
* @param k
* @param a
* @return
*/
private static int getSepcialProblemCount(int n, int k, int[] a) {
int pageNumber = 1, specialProblems = 0, problemNumber = 1;
for (int chapterNumber = 1; chapterNumber <= n;) {
int problemPerPage = (problemNumber + k  1) < a[chapterNumber1] ? problemNumber + k  1 : a[chapterNumber1];
if (problemNumber <= pageNumber && pageNumber <= problemPerPage) {
specialProblems++;
}
pageNumber++;
problemNumber += k;
if (problemNumber > a[chapterNumber1]) {
problemNumber = 1;
chapterNumber++;
}
}
return specialProblems;
}
}
60. Challenge: Fair Rations
You are the benevolent ruler of Rankhacker Castle, and today you’re distributing bread. Your subjects are in a line, and some of them already have some loaves. Times are hard and your castle’s food stocks are dwindling, so you must distribute as few loaves as possible according to the following rules:
 Every time you give a loaf of bread to some person i, you must also give a loaf of bread to the person immediately in front of or behind them in the line (i.e., persons i + 1 or i – 1).
 After all the bread is distributed, each person must have an even number of loaves.
Given the number of loaves already held by each citizen, find and print the minimum number of loaves you must distribute to satisfy the two rules above. If this is not possible, print NO
.
For example, the people in line have loaves B = [4,5,6,7]. We can first give a loaf to i = 3 and i = 4 so B = [4,5,7,8]. Next we give a loaf to i = 2 and i = 3 and have B = [4,6,8,8] which satisfies our conditions. We had to distribute 4 loaves.
Function Description
Complete the fairRations function in the editor below. It should return an integer that represents the minimum number of loaves required.
fairRations has the following parameter(s):
 B: an array of integers that represent the number of loaves each persons starts with .
Input Format
The first line contains an integer N, the number of subjects in the bread line.
The second line contains N spaceseparated integers B[i].
Constraints

2 ≤ N ≤ 1000

1≤ B[i] ≤ 100, where 1 ≤ i ≤ N
Output Format
Print a single integer taht denotes the minimum number of loaves that must be distributed so that every person has an even number of loaves. If it’s not possible to do this, print NO
.
Sample Input 0
5
2 3 4 5 6
Sample Output 0
4
Solution:
public class FairRations {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int B[] = new int[N];
for (int i = 0; i < N; i++) {
B[i] = sc.nextInt();
}
int result = getMinLoaveCount(B);
System.out.println(result != 1 ? result : "NO");
sc.close();
}
/**
* @return
*/
private static int getMinLoaveCount(int B[]) {
int minLovesCount = 0, sum = 0;
for (int i = 0; i < B.length; i++) {
sum += B[i];
if (sum % 2 == 1) {
minLovesCount += 2;
}
}
return ((sum & 1) == 1) ? 1 : minLovesCount;
}
}
61. Challenge: Manasa and Stones
Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that any two consecutive stones’ numbers differ by one of two values. Legend has it that there is a treasure trove at the end of the trail. If Manasa can guess the value of the last stone, the treasure will be hers.
For example, assume she finds 2 stones and their differences are a = 2 or b = 3. We know she starts with a 0 stone not included in her count. The permutations of differences for the two stones would be [2,2], [2,3], [3,2] or [3,3]. Looking at each scenario, stones might have [2,4], [2,5], [3,5] or [3,6] on them. The last stone might have any of 4, 5 or 6 on its face.
Compute all possible numbers that might occur on the last stone given a starting stone with a 0 on it, a number of additional stones found, and the possible differences between consecutive stones. Order the list ascending.
Function Description
Complete the stones function in the editor below. It should return an array of integers representing all possible values of the last stone, sorted ascending.
stones has the following parameter(s):
 n: an integer, the number of nonzero stones
 a: one possible integer difference
 b: another possible integer difference
Input Format
The first line contains an integer T, the number of test cases.
Each test case contains 3 lines:
– The first line contains n, the number of nonzero stones found.
– The second line contains a, one possible difference
– The third line contains b, the other possible difference.
Constraints

1≤ T ≤ 10

1 ≤ n,a,b ≤ 10^{3}
Output Format
Spaceseparated list of numbers which are the possible values of the last stone in increasing order.
Sample Input
2
3
1
2
4
10
100
Sample Output
2 3 4 30 120 210 300
Solution:
public class ManasaAndStones {
static int[] stones(int n, int a, int b) {
if (a == b) {
int c[] = { a * (n  1) };
return c;
}
int output[] = new int[n];
if (b < a) {
int tmp = a;
a = b;
b = tmp;
}
output[0] = a * (n  1);
int diff = Math.abs(b  a);
for (int i = 1; i < n; i++) {
output[i] = diff + output[i  1];
}
return output;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int a0 = 0; a0 < T; a0++) {
int n = in.nextInt();
int a = in.nextInt();
int b = in.nextInt();
int[] result = stones(n, a, b);
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + (i != result.length  1 ? " " : ""));
}
System.out.println("");
}
in.close();
}
}
62. Challenge: Cavity Map
You are given a square map as a matrix of integer strings. Each cell of the map has a value denoting its depth. We will call a cell of the map a cavity if and only if this cell is not on the border of the map and each cell adjacent to it has strictly smaller depth. Two cells are adjacent if they have a common side, or edge.
Find all the cavities on the map and replace their depths with the uppercase character X.
For example, given a matrix:
989
191
111
You should return:
989
1X1
111
The center cell was deeper than those on its edges: [8,1,1,1]. The deep cells in the top two corners don’t share an edge with the center cell.
Function Description
Complete the cavityMap function in the editor below. It should return an array of strings, each representing a line of the completed map.
cavityMap has the following parameter(s):
 grid: an array of strings, each representing a row of the grid
Input Format
The first line contains an integer n, the number of rows and columns in the map.
Each of the following n lines (rows) contains n positive digits without spaces (columns) representing depth at map[row, column].
Constraints
1≤ n ≤ 100
Output Format
Output n lines, denoting the resulting map. Each cavity should be replaced with the character X
.
Sample Input
4
1112
1912
1892
1234
Sample Output
1112 1X12 18X2 1234
Solution:
public class CavityMap {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String[] grid = new String[n];
for (int i = 0; i < n; i++) {
grid[i] = in.next();
}
for (int i = 1; i < grid.length  1; i++) {
String str = grid[i];
for (int j = 1; j < grid.length  1; j++) {
if (str.charAt(j  1) < str.charAt(j) && str.charAt(j) > str.charAt(j + 1)
&& grid[i  1].charAt(j) < str.charAt(j) && str.charAt(j) > grid[i + 1].charAt(j)) {
grid[i] = grid[i].substring(0, j) + "X" + grid[i].substring(j + 1);
}
}
}
printArray(grid);
in.close();
}
/**
* @param grid
*/
private static void printArray(String[] grid) {
int n = grid.length;
for (int grid_i = 0; grid_i < n; grid_i++) {
System.out.println(grid[grid_i]);
}
}
}
63. Challenge: The Grid Search
Given a 2D array of digits or grid, try to find the occurrence of a given 2D pattern of digits. For example, consider the following grid:
1234567890 0987654321 1111111111 1111111111 2222222222
Assume we need to look for the following 2D pattern array:
876543 111111 111111
The 2D pattern begins at the second row and the third column of the grid. The pattern is said to be present in the grid.
Function Description
Complete the gridSearch function in the editor below. It should return YES
if the pattern exists in the grid, or NO
otherwise.
gridSearch has the following parameter(s):
 G: the grid to search, an array of strings
 P: the pattern to search for, an array of strings
Input Format
The first line contains an integer t, the number of test cases.
Each of the t test cases is represented as follows:
The first line contains two spaceseparated integers R and C, indicating the number of rows and columns in the grid G.
This is followed by R lines, each with a string of C digits representing the grid G.
The following line contains two spaceseparated integers, r and c, indicating the number of rows and columns in the pattern grid P.
This is followed by r lines, each with a string of c digits representing the pattern P.
Constraints
1 ≤ t ≤ 5
1 ≤ R, r, C, c ≤ 1000
1≤ r ≤ R
1≤ c ≤ C
Output Format
Display YES
or NO
, depending on whether P is present in G.
Sample Input
2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99
Sample Output
YES NO
Solution:
public class TheGridSearch {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for (int a0 = 0; a0 < t; a0++) {
int R = in.nextInt();
int C = in.nextInt();
String[] G = new String[R];
for (int G_i = 0; G_i < R; G_i++) {
G[G_i] = in.next();
}
int r = in.nextInt();
int c = in.nextInt();
String[] P = new String[r];
for (int P_i = 0; P_i < r; P_i++) {
P[P_i] = in.next();
}
System.out.println(patternExist(R, G, P) ? "YES" : "NO");
}
in.close();
}
/**
* @param n
* @param grid
* @param pattern
*/
private static boolean patternExist(int n, String[] grid, String[] pattern) {
int pLen = pattern.length;
int gLen = grid.length;
if (pLen > gLen)
return false;
for (int gRow = 0; gRow < gLen  pLen + 1; gRow++) {
String p = pattern[0];
String text = grid[gRow];
for (int gCol = 0; gCol < grid[gRow].length()  p.length() + 1; gCol++) {
int index = text.indexOf(p, gCol);
if (index != 1) {
if (validateStringRecursivelly(grid, pattern, index, p.length(), gRow, 0)) {
return true;
}
} else {
break;
}
}
}
return false;
}
/**
* @param grid
* @param pattern
* @param index
* @param length
* @return
*/
private static boolean validateStringRecursivelly(String[] grid, String[] pattern, int index, int length, int gRow,
int pRow) {
if (!grid[gRow].substring(index, index + length).equals(pattern[pRow]))
return false;
if (pattern.length  1 == pRow)
return true;
return validateStringRecursivelly(grid, pattern, index, length, gRow + 1, pRow + 1);
}
}
64. Challenge: Happy Ladybugs
Happy Ladybugs is a board game having the following properties:
 The board is represented by a string, b, of length n. The i^{th} character of the string, b[i], denotes the i^{th} cell of the board.
 If b[i] is an underscore (i.e.,
_
), it means the i^{th} cell of the board is empty.  If b[i] is an uppercase English alphabetic letter (ascii[AZ]), it means the i^{th} cell contains a ladybug of color b[i].
 String b will not contain any other characters.
 If b[i] is an underscore (i.e.,
 A ladybug is happy only when its left or right adjacent cell (i.e., b[i ± 1]) is occupied by another ladybug having the same color.
 In a single move, you can move a ladybug from its current position to any empty cell.
Given the values of n and b for g games of Happy Ladybugs, determine if it’s possible to make all the ladybugs happy. For each game, print YES
on a new line if all the ladybugs can be made happy through some number of moves. Otherwise, print NO
.
As an example, b = [YYR_B_BR]. You can move the rightmost B and R to make b = [YYRRBB__] and all the ladybugs are happy.
Function Description
Complete the happyLadybugs function in the editor below. It should return an array of strings, either ‘YES’ or ‘NO’, one for each test string.
happyLadybugs has the following parameters:
 b: an array of strings that represents the initial positions and colors of the ladybugs
Input Format
The first line contains an integer G, the number of games.
The next G pairs of lines are in the following format:
 The first line contains an integer n, the number of cells on the board.
 The second line contains a string b describing the n cells of the board.
Constraints

1 ≤ g, n ≤ 100

b[i] ∈ {_,ascii[A – Z]}
Output Format
For each game, print YES
on a new line if it is possible to make all the ladybugs happy. Otherwise, print NO
.
Sample Input 0
4
7
RBY_YBR
6
X_Y__X
2
__
6
B_RRBR
Sample Output 0
YES NO YES YES
Solution:
public class HappyLadybugs {
public static void main(String[] args) {
HashMap<Character, Integer> hmap = new HashMap<Character, Integer>();
Scanner sc = new Scanner(System.in);
int g = sc.nextInt();
for (int i = 0; i < g; i++) {
int n = sc.nextInt();
String b = sc.next();
hmap.put(b.charAt(0), 1);
boolean needAdjust = false;
for (int j = 1; j < b.length(); j++) {
char ch = b.charAt(j);
if (hmap.containsKey(ch)) {
if ((j == b.length()  1 && b.charAt(j) != b.charAt(j  1))
 b.charAt(j) != b.charAt(j  1) && ((b.charAt(j) != b.charAt(j + 1)))) {
needAdjust = true;
}
hmap.put(ch, hmap.get(ch) + 1);
} else {
hmap.put(ch, 1);
}
}
boolean found = false;
Set<Entry<Character, Integer>> s = hmap.entrySet();
for (Entry<Character, Integer> entry : s) {
int value = entry.getValue();
char key = entry.getKey();
if (value == 1 && key != '_') {
System.out.println("NO");
found = true;
break;
} else if (needAdjust && !hmap.containsKey('_')) {
System.out.println("NO");
found = true;
break;
}
}
if (!found)
System.out.println("YES");
hmap.clear();
}
sc.close();
}
}
65. Challenge: Strange Counter
Bob has a strange counter. At the first second, it displays the number 3. Each second, the number displayed by the counter decrements by 1 until it reaches 1.
The counter counts down in cycles. In next second, the timer resets to 2 x the initial number for the prior cycle and continues counting down. The diagram below shows the counter values for each time t in the first three cycles:
Find and print the value displayed by the counter at time t .
Function Description
Complete the strangeCounter function in the editor below. It should return the integer value displayed by the counter at time t .
strangeCounter has the following parameter(s):
 t: an integer
Input Format
A single integer denoting the value of t .
Constraints

1 ≤ t ≤ 10^{12}
Subtask

1 ≤ t ≤ 10^{5} for 60% of the maximum score.
Output Format
Print the value displayed by the strange counter at the given time t.
Sample Input
4
Sample Output
6
Solution:
public class StrangeCounter {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long i = 0;
long lValue = (long) (3 * Math.pow(2, i))  2;
long hValue = 2 * lValue + 1;
while (hValue < n) {
lValue = (long) (3 * Math.pow(2, ++i))  2;
hValue = 2 * lValue + 1;
}
System.out.println(hValue + 1  n);
sc.close();
}
}
66. Challenge:Consecutive 1’s in Binary Numbers
Given a base10 integer, n, convert it to binary (base2). Then find and print the base10 integer denoting the maximum number of consecutive 1‘s in n‘s binary representation.
Input Format
A single integer, n.
Constraints

1 ≤ n ≤ 10^{6}
Output Format
Print a single base10 integer denoting the maximum number of consecutive 1‘s in the binary representation of n.
Sample Input 1
5
Sample Output 1
1
Sample Input 2
13
Sample Output 2
2
Solution:
public class Consecutive1sInBinaryNumbers {
public static int countConsecutive1sInBinary(int number) {
int count = 0;
while (number > 0) {
number = number & (number << 1);
count++;
}
return count;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int number = sc.nextInt();
int result = countConsecutive1sInBinary(number);
System.out.println(result);
sc.close();
}
}
Responses