Hackerearth-General 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 positivenegative, 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 space-separated integers describing an array of numbers arr(arr[0], arr[1], arr[2], … , arr[n-1]).

Constraints

0 < n ≤ 100

-100 ≤ arr[i] ≤ 100

Output Format

You must print the following 3 lines:

  1. A decimal representing of the fraction of positive numbers in the array compared to its size.
  2. A decimal representing of the fraction of negative numbers in the array compared to its size.
  3. 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 left-to-right diagonal = 1+5+9=15. The right to left diagonal = 3+5+9=17. Their absolute difference is |15-17|=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 space-separated 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 space-separated integers contained in the array.

Output Format

Print the integer sum of the elements in the array.

Constraints 
1 ≤ 10 ≤ n

0 ≤ ar[i] ≤ 1010

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  space-separated 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 clarityoriginality, 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 space-separated integers, a[0],a[1] , and a[2], describing the respective values in triplet a
The second line contains 3 space-separated 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[n-1] , 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 space-separated integers, n and k
The second line contains n space-separated integers describing the values of  ar[ar[o],ar[1],…ar[n-1]].

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 space-separated 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:

image

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 ≤ 105

  • 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 space-separated integers, where each integer i describes the height of candle i.

Constraints

  • 1 ≤ n ≤ 105

  • 1 ≤ ar[i] ≤ 107

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 zero-based 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 space-separated integers n and k, the number of items ordered and the 0-based index of the item that Anna did not eat. 
The second line contains n space-separated 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 ≤ 105
  • 0 ≤ k < n

  • 0 ≤ bill[i] ≤ 104

  • 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.,bcharged – bactual) 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 space-separated 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.

Apple and orange(2).png

When a fruit falls from its tree, it lands d units of distance from its tree of origin along the x-axis. 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 space-separated integers denoting the respective values of s and t
The second line contains two space-separated integers denoting the respective values of a and b
The third line contains two space-separated integers denoting the respective values of m and n
The fourth line contains  space-separated integers denoting the respective distances that each apple falls from point a
The fifth line contains  space-separated integers denoting the respective distances that each orange falls from point b.

Constraints

  • 1 ≤ s,t,a,b,m,n≤ 105

  • -105 ≤ d ≤ 105

  • a < s < t < b

Output Format

Print two integers on two different lines:

  1. The first integer: the number of apples that fall on Sam’s house.
  2. 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:

  1. The elements of the first array are all factors of the integer being considered
  2. 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 space-separated 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 space-separated integers describing a[i] where ≤ i ≤ n
The third line contains  distinct space-separated integers describing  b[j] where ≤ 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: Mini-Max 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 space-separated 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 space-separated 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 space-separated integers.

Constraints

1 ≤ arr[i] ≤ 109

Output Format

Print two space-separated 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 space-separated integers describing the respective values of Score0, Score1,, Scoren-1.

Constraints

  • 1 ≤ n ≤ 1000

  • 1 ≤ score[i] ≤ 108

Output Format

Print two space-seperated 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 space-separated integers representing the type numbers of each bird sighted.

Constraints

  • 5≤ n ≤ 2 x 105

  • 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 space-separated integers s[i], the numbers on the chocolate squares where ≤ i < n
The third line contains two space-separated integers, d and m, Ron’s birth day and his birth month.

Constraints

  • 1 ≤ n ≤ 100

  • 1 ≤ s[i] ≤ 5, where (≤ 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 12-hour AM/PM format, convert it to military (24-hour) time.

Note: Midnight is 12:00:00AM on a 12-hour clock, and 00:00:00 on a 24-hour clock. Noon is 12:00:00PM on a 12-hour clock, and 12:00:00 on a 24-hour 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 12-hour 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 24-hour 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:

  1. If the book is returned on or before the expected return date, no fine will be charged (i.e.: fine = 0).
  2. 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).
  3. 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)
  4. 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 space-separated integers, d1,m1,y1 denoting the respective day,month, and  year on which the book was returned. 
The second line contains 3 space-separated 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 space-separated 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 ≤ 109

  • 1 ≤ m ≤ 109

  • 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[n-1] 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 space-separated integers, n and k, the number of clouds and the jump distance. 
The second line contains n space-separated 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:

  • 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.
  • 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
Input Format

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 ≤ 106

  • 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 5th  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 space-separated integers describing the respective values of i, j, and k.

Constraints

  • 1 ≤ i ≤ j ≤ 2 x 106

  • 1 ≤ k ≤ 2 x 109

Output Format

Print the number of beautiful days in the inclusive range between i and j.

Sample Input

20 23 6

Sample Output

2
Solution:
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 space-separated integers b, n, and m, her budget, the number of keyboard models and the number of USB drive models. 
The second line contains n space-separated integers keyboard[i], the prices of each keyboard model. 
The third line contains m space-separated integers drives, the prices of the USB drives.

Constraints

  • 1≤ n, m≤ 1000

  • 1 ≤ b ≤ 106

  • The price of each item is in the inclusive range [1, 106].

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 space-separated 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 time-traveling to visit Russia on the Day of the Programmer (the 256th 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 31st was February 14th. This means that in 1918, February 14th was the 32nd 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 256th 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 two-digit day, mm is the two-digit month, and yyyy is y.

For example, the given year = 1984. 1984 is divisible by 4, so it is a leap year. The 256th 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 256th  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 two-digit day, mm is the two-digit 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 space-separated integers n and k, the number of hurdles and the maximum height Dan can jump naturally. 
The second line contains n space-separated 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.

Paradise Highway

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 space-separated integers which represent the array width[w0, w1,…,wn-1].

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 zero-based 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 space-separated integers, nk, and q, the number of elements in the integer array, the rotation count and the number of queries. 
The second line contains n space-separated 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 ≤ 105

  • 1 ≤ a[i] ≤ 105

  • 1 ≤ k ≤ 105

  • 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 space-separated integers denoting a and b, the starting and ending integers in the ranges.

Constraints

1≤ q ≤ 100

1 ≤ a ≤ b ≤ 109

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 space-separated integers, n and k, the number of students (size of a) and the cancellation threshold. 
The second line contains n space-separated integers (a[1],a[2],…,a[n]) describing the arrival times for each student.

Note: Non-positive 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:

                   n! = n x (n – 1) x ( n – 2) x x 3 x 2 x 1

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

25

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 space-separated integers a[i].

Constraints

  • 1 ≤ n ≤ 103

  • 1 ≤ a[i] ≤ 105

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: Non-Divisible 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 space-separated integers, n and k, the number of values in S and the non factor. 
The second line contains n space-separated integers describing S[i], the unique values of the set.

Constraints

  • 1 ≤ n ≤ 105

  • 1 ≤ k ≤ 100

  • 1 ≤ S[i] ≤ 109

  • 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 space-separated integers n and d, the length of the sequence and the beautiful difference. 
The second line contains n space-separated integers arr[i].

Constraints

  • 1 ≤ n ≤ 104

  • 1 ≤ d ≤ 20

  • 0 ≤ arr[i] ≤ 2 x 104

  • 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 space-separated binary integers describing clouds c[i] where 0 ≤ i ≤ n .

Constraints

  • 2 ≤ n ≤ 100

  • c[i] ε {0,1}

  • c[0] = c[n-1] = 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 space-separated 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:

PDF-highighting.png

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 mm2

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 = 8mm2 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 space-separated integers describing the respective heights of each consecutive lowercase English letter, ascii[a-z]. 
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 mm2  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 n2 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 space-separated 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 ≤ 1012

  • For  25% of the test cases, n ≤ 106.

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 space-separated integers, N and K, respectively.

Constraints

  • 1 ≤ T ≤ 103

  • 2≤ N ≤ 103

  • 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, a0,a1,…,an-1, and a positive integer, k. Find and print the number of (i,j) pairs where i < j and  ai + aj  is evenly divisible by k.

Input Format

The first line contains 2 space-separated integers, n and k, respectively. 
The second line contains n space-separated integers describing the respective values of .a0,a1,…,an-1

Constraints

  • 2 ≤ n ≤ 100

  • 1≤ k ≤ 100

  • 1≤ ai ≤ 100

Output Format

Print the number of (i,j) pairs where i < j and ai + aj  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:

  1. Append a lowercase English alphabetic letter to the end of the string.
  2. 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 6th 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 [a-z].

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 space-separated 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 122, and 3, respectively. If Alice’s scores are 7080 and 105, her rankings after each game are 4th , 3rd   and 1st.

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 jth 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 space-separated 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 space-separated integers alice[j], the game scores.

Constraints

  • 1 ≤ n ≤ 2 x 105

  • 1 ≤ m ≤ 2 x 105

  • 0 ≤ scores[i] ≤ 109 for ≤ i ≤ n

  • 0 ≤ alice[j] ≤ 109 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 jth integer should indicate Alice’s rank after playing the jth game.

Sample Input 1

Array: scores1001005040402010 Array: alice52550120
7
100 100 50 40 40 20 10
4
5 25 50 120

Sample Output 1

6
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:

  1. x = 1 = p[3],p[4] = 3, so p[p[4]]1
  2. x = 2= p[2,p[2] = 2, so p[p[2]]2
  3. x = 1 = p[4],p[5] = 4, so p[p[5]]3
  4. x = 1 = p[5],p[1] = 5, so p[p[1]]4
  5. 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 space-separated 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 < 109

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 space-separated integers: nc, 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 ≤ 105

  • 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 space-separated integers, each an arr[i] where each value represents the length of the ith 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 ACM-ICPC 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 2-person 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 space-separated 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 ith line’s jth character is 1, then the ith person knows the jthtopic.

Constraints

2 ≤ n ≤ 500

1 ≤ m ≤ 500

Output Format

On the first line, print the maximum number of topics a 2-person team can know. 
On the second line, print the number of ways to form a 2-person 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 bcwc, and z.

Constraints

1 ≤ t ≤ 10

0 ≤ b, w, bc, wc, z ≤ 109

 

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:

                               5:00 -> five o’clock
                               5:01 -> one minute past five
                               5:15 -> quarter past five
                               5:30 -> half past five
                               5:45 -> quarter to six
At minutes = 0, use o’ clock. For 1 minutes ≤  30, use past, and for 30 < minutes use to. Note the space between the apostrophe and clock in o’ clock. Write a program which prints the time in words for the input given in the format described.

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 space-separated integers, n and m
The second line contains m space-separated integers, the indices of each city having a space-station. These values are unordered and unique.

Constraints

  • 1 ≤ n ≤ 105

  • 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 ith 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 space-separated integers arr[i] where arr[i] denotes the number of problems in the ith 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[chapterNumber-1] ? problemNumber + k - 1 : a[chapterNumber-1];
			if (problemNumber <= pageNumber && pageNumber <= problemPerPage) {
				specialProblems++;
			}
			pageNumber++;
			problemNumber += k;
			if (problemNumber > a[chapterNumber-1]) {
				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:

  1. 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).
  2. 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 space-separated integers B[i].

Constraints

  • 2 ≤ N ≤ 1000

  • 1≤ B[i] ≤ 100, where ≤ 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 non-zero 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 non-zero 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 ≤ 103

Output Format

Space-separated 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 space-separated 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 space-separated 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 ith character of the string, b[i], denotes the ith cell of the board.
    • If b[i] is an underscore (i.e., _), it means the ith cell of the board is empty.
    • If b[i] is an uppercase English alphabetic letter (ascii[A-Z]), it means the ith cell contains a ladybug of color b[i].
    • String b will not contain any other characters.
  • 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 ≤ 1012

Subtask

  • 1 ≤ t ≤ 105 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 base-10 integer, n, convert it to binary (base-2). Then find and print the base-10 integer denoting the maximum number of consecutive 1‘s in n‘s binary representation.

Input Format

A single integer, n.

Constraints

  • 1 ≤ n ≤ 106

Output Format

Print a single base-10 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();
	}
}

Related Articles

Core Java

1. What are primitive types in Java ? byte, short, int, long, float, double, char, boolean… 2. What are tokens? Name the 5 types of tokens available in Java with an example…

Hackerearth-Java

     1. Challenge : Welcome to Java! Welcome to the world of Java! In this challenge, we practice printing to stdout. The code stubs…

Hackerearth-Algorithm

      1. Challenge: Quicksort 1 – Partition The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with a running…

Responses

Your email address will not be published. Required fields are marked *

KodNest Training New Batch is starting on 21st September 2020. Attend one week free demo classes.Register Now

New Report

Close