 # Hackerearth – Algorithm

The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with a running time of O(n2). In these next few challenges, we’re covering a divide-and-conquer algorithm called Quicksort (also known as Partition Sort). This challenge is a modified version of the algorithm that only addresses partitioning. It is implemented as follows:

Step 1: Divide
Choose some pivot element, p, and partition your unsorted array, , into three smaller arrays: leftright, and equal, where each element in left < p, each element in right > p, and each element in equal = p.

For example: Assume arr = [5,7,4,3,8]
The pivot is at arr = 5
arr is divided into left = {4,3}equal = {5}, and right = {7,8}
Putting them all together, you get {4,3,5,7,8}. Another valid solution is {3,4,5,8,7}.

Given arr and p = arr, partition arr into leftright, and equal using the Divide instructions above. Then print each element in left followed by each element in equal, followed by each element in right on a single line. Your output should be space-separated and does not have to maintain ordering of the elements within the three categories.

Function Description

Complete the quickSort function in the editor below. It should return an array of integers as described above.

quickSort has the following parameter(s):

• arr: an array of integers where arr is the pivot element

Input Format

The first line contains n, the size of the array arr
The second line contains n space-separated integers describing arr (the unsorted array). The first integer (corresponding to arr) is your pivot element, p.

Constraints

• 1 ≤ n ≤ 1000

• -1000 ≤ arr[i] ≤ 1000 where 0 ≤ i < n

• All elements will be unique.

Output Format

On a single line, print the partitioned numbers (i.e.: the elements in left, then the elements in equal, and then the elements in right). Each integer should be separated by a single space.

Sample Input

5
4 5 3 7 2


Sample Output

3 2 4 5 7

Solution:

public class Quicksort1Partition {

public static void partition(int[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
while (hi > lo) {
while (a[++i] < a[lo])
if (i == hi)
break;
while (a[--j] > a[lo])
if (j == lo)
break;
if (i >= j)
break;
swap(a, i, j);

}
swap(a, lo, j);
printArray(a);
}

private static void swap(int array[], int i, int j) {
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}

public static void printArray(int a[]) {
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
}

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();
}
partition(a, 0, a.length - 1);
sc.close();

}
}

Marc loves cupcakes, but he also likes to stay fit. Each cupcake has a calorie count, and Marc can walk a distance to expend those calories. If Marc has eaten j cupcakes so far, after eating a cupcake with c calories he must walk at least 2x c miles to maintain his weight.

For example, if he eats 3 cupcakes with calorie counts in the following order: [5,10,7], the miles he will need to walk are This is not the minimum, though, so we need to test other orders of consumption. In this case, our minimum miles is calculated as Given the individual calorie counts for each of the cupcakes, determine the minimum number of miles Marc must walk to maintain his weight. Note that he can eat the cupcakes in any order.

Function Description

Complete the marcsCakewalk function in the editor below. It should return a long integer that represents the minimum miles necessary.

marcsCakewalk has the following parameter(s):

• calorie: an integer array that represents calorie count for each cupcake

Input Format

The first line contains an integer n, the number of cupcakes in calorie
The second line contains n space-separated integers calorie[i].

Constraints

• 1 ≤ n ≤ 40

• 1 ≤ c[i] ≤ 1000

Output Format

Print a long integer denoting the minimum number of miles Marc must walk to maintain his weight.

Sample Input 0

3
1 3 2


Sample Output 0

11

Solution:

public class MarcsCakewalk {

public static int[] sort(int a[]) {

for (int i = 1; i < a.length; i++) {
for (int j = i; j > 0; j--) {
if (a[j] < a[j - 1]) {
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
} else
break;
}
}
return a;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] calories = new int[n];
for (int calories_i = 0; calories_i < n; calories_i++) {
calories[calories_i] = in.nextInt();
}
int sortedArray[] = sort(calories);
int j = 0;
long sum = 0;
for (int i = sortedArray.length - 1; i >= 0; i--) {
sum = (sum + sortedArray[i] * (long) Math.pow(2, j++));
}
System.out.println(sum);
in.close();
}
}

Consider an array of integers, arr = [arr, arr,…, arr[n-1]]. We define the absolute difference between two elements, a[i] and a[j] (where i ≠ j), to be the absolute value of a[i] – a[j].

Given an array of integers, find and print the minimum absolute difference between any two elements in the array. For example, given the array arr = [-2,2,4] we can create 3 pairs of numbers: [-2,2], [-2,4] and [2,4]. The absolute differences for these pairs are |(-2) -2| = 4|(-2) -4| = 2 and . The minimum absolute difference is 2.

Function Description

Complete the minimumAbsoluteDifference function in the editor below. It should return an integer that represents the minimum absolute difference between any pair of elements.

minimumAbsoluteDifference has the following parameter(s):

• n: an integer that represents the length of arr
• arr: an array of integers

Input Format

The first line contains a single integer n, the size of arr
The second line contains n space-separated integers arr[i].

Constraints

• 2 ≤ n ≤ 105

• -109≤ arr[i] ≤ 109

Output Format

Print the minimum absolute difference between any two elements in the array.

Sample Input 0

3
3 -7 0


Sample Output 0

3

Solution:

public class MinimumAbsoluteDifferenceInAnArray {
public static void sort(int a[], int lo, int hi) {
if (hi > lo) {
int q = partition(a, lo, hi);
sort(a, lo, q - 1);
sort(a, q + 1, hi);
}

}

public static int partition(int[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
while (hi > lo) {
while (a[++i] < a[lo])
if (i == hi)
break;
while (a[--j] > a[lo])
if (j == lo)
break;

if (i >= j)
break;
swap(a, i, j);
}
swap(a, lo, j);
return j;

}

public static void swap(int a[], int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[n];
for (int a_i = 0; a_i < n; a_i++) {
a[a_i] = in.nextInt();
}
sort(a, 0, a.length - 1);
int min = Integer.MAX_VALUE;
for (int i = 1; i < a.length; i++) {
int diff = a[i] - a[i - 1];
if (diff < min) {
min = diff;
}
}
System.out.println(min);
in.close();
}
}

Lena is preparing for an important coding competition that is preceded by a number of sequential preliminary contests. She believes in “saving luck”, and wants to check her theory. Each contest is described by two integers, L[i] and T[i]:

• L[i] is the amount of luck associated with a contest. If Lena wins the contest, her luck balance will decrease by L[i]; if she loses it, her luck balance will increase by L[i].
• T[i] denotes the contest’s importance rating. It’s equal to 1 if the contest is important, and it’s equal to 0 if it’s unimportant.

If Lena loses no more than k important contests, what is the maximum amount of luck she can have after competing in all the preliminary contests? This value may be negative.

For example, k = 2 and:

Contest		L[i]	T[i]
1		5	1
2		1	1
3		4	0


If Lena loses all of the contests, her will be 5 + 4 – 1 = 8. Since she is allowed to lose  important contests, and there are only  important contests. She can lose all three contests to maximize her luck at . If , she has to win at least  of the important contests. She would choose to win the lowest value important contest worth . Her final luck will be .

Function Description

Complete the luckBalance function in the editor below. It should return an integer that represents the maximum luck balance achievable.

luckBalance has the following parameter(s):

• k: the number of important contests Lena can lose
• contests: a 2D array of integers where each contests[i] contains two integers that represent the luck balance and importance of the ith contest.

Input Format

The first line contains two space-separated integers n and k, the number of preliminary contests and the maximum number of important contests Lena can lose.
Each of the next n lines contains two space-separated integers, L[i] and T[i], the contest’s luck balance and its importance rating.

Constraints Output Format

Print a single integer denoting the maximum amount of luck Lena can have after all the contests.

Sample Input

6 3
5 1
2 1
1 1
8 1
10 0
5 0


Sample Output

29

Solution:

public class LuckBalance {
public static void sort(int a[], int lo, int hi) {
if (hi > lo) {
int q = partition(a, lo, hi);
sort(a, lo, q - 1);
sort(a, q + 1, hi);
}
}

public static int partition(int a[], int lo, int hi) {
int i = lo;
int j = hi + 1;
while (hi > lo) {

while (a[++i] < a[lo])
if (i == hi)
break;
while (a[--j] > a[lo])
if (j == lo)
break;

if (i >= j)
break;
swap(a, i, j);

}
swap(a, lo, j);
return j;
}

public static void swap(int a[], int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
int win = 0;
int a[] = new int[N];
int sum = 0;
for (int i = 0; i < N; i++) {
int temp = sc.nextInt();
if (sc.nextInt() == 1) {
win++;
a[i] = temp;
} else {
a[i] = Integer.MAX_VALUE;
}
sum += temp;
}
sort(a, 0, a.length - 1);
int s2 = 0;
for (int i = 0; i < win - K; i++) {
s2 += a[i];
}

System.out.println(sum - 2 * s2);
sc.close();
}
}

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

• ≤ n ≤ 2 x 105

• ≤ m ≤ 2 x 105

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

• 0 ≤ alice[j] ≤ 10for 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:

• ≤ n ≤ 200

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

6421

Solution:

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 = 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) {
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;
}

}

Consider an array of numeric strings where each string is a positive number with anywhere from 1 to 106digits. Sort the array’s elements in non-decreasing, or ascending order of their integer values and print each element of the sorted array on a new line.

Function Description

Complete the bigSorting function in the editor below. It should return the sorted string array.

bigSorting has the following parameter(s):

• unsorted: an unsorted array of integers as strings

Input Format

The first line contains an integer, n , denoting the number of strings in unsorted
Each of the n subsequent lines contains an integer string unsorted[i].

Constraints

• 1≤N≤2*10^5
• Each string is guaranteed to represent a positive integer without leading zeros.
• The total number of digits across all strings in unsorted is between 1 and 10^6
•  (inclusive).

Output Format

Print each element of the sorted array on a new line.

Sample Input 0

6
31415926535897932384626433832795
1
3
10
3
5


Sample Output 0

1
3
3
5
10
31415926535897932384626433832795


Solution:

public class BigSorting {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String[] unsorted = new String[n];
for (int unsorted_i = 0; unsorted_i < n; unsorted_i++) {
unsorted[unsorted_i] = in.next();
}

Arrays.sort(unsorted, new Comparator() {

public int compare(String s1, String s2) {
return compareStrings(s1, s2);
}
});
printArray(unsorted);
in.close();
}

private static int compareStrings(String s1, String s2) {
if (s1.length() < s2.length()) {
return -1;
} else if (s1.length() > s2.length()) {
return 1;
}
for (int k = 0; k < s1.length(); k++) {
if ((int) s1.charAt(k) < (int) s2.charAt(k))
return -1;
if ((int) s1.charAt(k) > (int) s2.charAt(k))
return 1;

}
return 0;

}

private static void printArray(String[] unsorted) {

for (String string : unsorted) {
System.out.println(string);
}

}

}

Sorting
One common task for computers is to sort data. For example, people might want to see all their files on a computer sorted by size. Since sorting is a simple problem with many different possible solutions, it is often used to introduce the study of algorithms.

Insertion Sort
These challenges will cover Insertion Sort, a simple and intuitive sorting algorithm. We will first start with a nearly sorted list.

Insert element into sorted list
Given a sorted list with an unsorted number e in the rightmost cell, can you write some simple code to insert e into the array so that it remains sorted?

Since this is a learning exercise, it won’t be the most efficient way of performing the insertion. It will instead demonstrate the brute-force method in detail.

Assume you are given the array arr = [1,2,4,5,3] indexed 0…4. Store the value of arr. Now test lower index values successively from 3 to 0 until you reach a value that is lower than arrarr in this case. Each time your test fails, copy the value at the lower index to the current index and print your array. When the next lower indexed value is smaller than arr, insert the stored value at the current index and print the entire array.

The results of operations on the example array is:

Starting array:  [1,2,4,5,3]
Store the value of arr = 3 Do the tests and print interim results:

1 2 4 5 5
1 2 4 4 5
1 2 3 4 5


Function Description

Complete the insertionSort1 function in the editor below. It should print the interim and final arrays, each on a new line.

insertionSort1 has the following parameter(s):

• n: an integer, the size of arr
• arr: an array of integers to sort

Input Format

The first line contains the integer n, the size of the array arr
The next line contains n space-separated integers arr[o]…arr[n – 1].

Constraints

1 ≤ n ≤ 1000

-10000 ≤ arr[i] ≤ 10000

Output Format

Print the array as a row of space-separated integers each time there is a shift or insertion.

Sample Input

5
2 4 6 8 3


Sample Output

2 4 6 8 8
2 4 6 6 8
2 4 4 6 8
2 3 4 6 8 

Solution:

public class InsertionSortPart1 {
public static void insertIntoSorted(int[] ar) {
int length = ar.length;
int elementNeedToBeInserted = ar[length - 1];
for (int i = length - 2; i >= 0; i--) {
if (ar[i] > elementNeedToBeInserted) {
ar[i + 1] = ar[i];
printArray(ar);

} else {
ar[i + 1] = elementNeedToBeInserted;
printArray(ar);
break;
}
if ((i == 0) && (ar[i] > elementNeedToBeInserted)) {
ar[i] = elementNeedToBeInserted;
printArray(ar);
}
}

}

/* Tail starts here */
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int s = in.nextInt();
int[] ar = new int[s];
for (int i = 0; i < s; i++) {
ar[i] = in.nextInt();
}
insertIntoSorted(ar);
in.close();
}

private static void printArray(int[] ar) {
for (int n : ar) {
System.out.print(n + " ");
}
System.out.println("");
}
}

In Insertion Sort Part 1, you inserted one element into an array at its correct sorted position. Using the same approach repeatedly, can you sort an entire array?

Guideline: You already can place an element into a sorted array. How can you use that code to build up a sorted array, one element at a time? Note that in the first step, when you consider an array with just the first element, it is already sorted since there’s nothing to compare it to.

In this challenge, print the array after each iteration of the insertion sort, i.e., whenever the next element has been inserted at its correct position. Since the array composed of just the first element is already sorted, begin printing after placing the second element.

For example, there are n = 7 elements in arr = [3,4,7,5,6,2,1]. Working from left to right, we get the following output:

3 4 7 5 6 2 1
3 4 7 5 6 2 1
3 4 5 7 6 2 1
3 4 5 6 7 2 1
2 3 4 5 6 7 1
1 2 3 4 5 6 7


Function Description

Complete the insertionSort2 function in the editor below. At each iteration, it should print the array as space-separated integers on a separate line.

insertionSort2 has the following parameter(s):

• n: an integer representing the length of the array arr
• arr: an array of integers

Input Format

The first line contains an integer, n, the size of arr
The next line contains n space-separated integers arr[i].

Constraints

1 ≤ n ≤ 1000

-10000 ≤ arr[i] ≤ 10000, 0 ≤ i < n

Output Format

On each line, output the entire array at every iteration.

Sample Input

6
1 4 3 5 6 2


Sample Output

1 4 3 5 6 2
1 3 4 5 6 2
1 3 4 5 6 2
1 3 4 5 6 2
1 2 3 4 5 6 

Solution:

public class InsertionSortPart2 {
public static void insertionSortPart2(int[] ar) {
for (int i = 1; i < ar.length; i++) {

for (int j = i; j > 0; j--) {
if (ar[j] < ar[j - 1]) {
int temp = ar[j];
ar[j] = ar[j - 1];
ar[j - 1] = temp;
} else {
break;
}
}
printArray(ar);
}

}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int s = in.nextInt();
int[] ar = new int[s];
for (int i = 0; i < s; i++) {
ar[i] = in.nextInt();
}
insertionSortPart2(ar);
in.close();
}

private static void printArray(int[] ar) {
for (int n : ar) {
System.out.print(n + " ");
}
System.out.println("");
}
}

In the previous challenge, you wrote code to perform an Insertion Sort on an unsorted array. But how would you prove that the code is correct? I.e. how do you show that for any input your code will provide the right output?

Loop Invariant
In computer science, you could prove it formally with a loop invariant, where you state that a desired property is maintained in your loop. Such a proof is broken down into the following parts:

• Initialization: It is true (in a limited sense) before the loop runs.
• Maintenance: If it’s true before an iteration of a loop, it remains true before the next iteration.
• Termination: It will terminate in a useful way once it is finished.

Insertion Sort’s Invariant
Say, you have some InsertionSort code, where the outer loop goes through the whole array A:

for(int i = 1; i < A.length; i++){
//insertion sort code


You could then state the following loop invariant:

At the start of every iteration of the outer loop (indexed with i), the subarray until ar[i] consists of the original elements that were there, but in sorted order.

To prove Insertion Sort is correct, you will then demonstrate it for the three stages:

• Initialization – The subarray starts with the first element of the array, and it is (obviously) sorted to begin with.

• Maintenance – Each iteration of the loop expands the subarray, but keeps the sorted property. An element V gets inserted into the array only when it is greater than the element to its left. Since the elements to its left have already been sorted, it means V is greater than all the elements to its left, so the array remains sorted. (In Insertion Sort 2 we saw this by printing the array each time an element was properly inserted.)

• Termination – The code will terminate after i has reached the last element in the array, which means the sorted subarray has expanded to encompass the entire array. The array is now fully sorted. You can often use a similar process to demonstrate the correctness of many algorithms. You can see these notes for more information.

Challenge

In the InsertionSort code below, there is an error. Can you fix it? Print the array only once, when it is fully sorted.

Input Format

There will be two lines of input:

•  – the size of the array
•  arr – the list of numbers that makes up the array

Constraints Output Format

Output the numbers in order, space-separated on one line.

Sample Input

6
7 4 3 5 6 2


Sample Output

2 3 4 5 6 7

Solution:

public class CorrectnessAndTheLoopInvariant {
public static void insertionSort(int[] A) {
for (int i = 1; i < A.length; i++) {
int value = A[i];
int j = i - 1;
while (j >= 0 && A[j] > value) {
A[j + 1] = A[j];

j = j - 1;
}
A[j + 1] = value;

}

printArray(A);
}

static void printArray(int[] ar) {
for (int n : ar) {
System.out.print(n + " ");
}
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] ar = new int[n];
for (int i = 0; i < n; i++) {
ar[i] = in.nextInt();
}
insertionSort(ar);
in.close();
}
}

In a previous challenge you implemented the Insertion Sort algorithm. It is a simple sorting algorithm that works well with small or mostly sorted data. However, it takes a long time to sort large unsorted data. To see why, we will analyze its running time.

Running Time of Algorithms
The running time of an algorithm for a specific input depends on the number of operations executed. The greater the number of operations, the longer the running time of an algorithm. We usually want to know how many operations an algorithm will execute in proportion to the size of its input, which we will call N.

What is the ratio of the running time of Insertion Sort to the size of the input? To answer this question, we need to examine the algorithm.

Analysis of Insertion Sort
For each element V in an array of N numbers, Insertion Sort compares the number to those to its left until it reaches a lower value element or the start. At that point it shifts everything to the right up one and inserts V  into the array.

How long does all that shifting take?

In the best case, where the array was already sorted, no element will need to be moved, so the algorithm will just run through the array once and return the sorted array. The running time would be directly proportional to the size of the input, so we can say it will take N time.

However, we usually focus on the worst-case running time (computer scientists are pretty pessimistic). The worst case for Insertion Sort occurs when the array is in reverse order. To insert each number, the algorithm will have to shift over that number to the beginning of the array. Sorting the entire array of N numbers will therefore take 1 + 2 +…+ (N-1) operations, which is N(N-1)/2 (almost N2/2). Computer scientists just round that up (pick the dominant term) to N2 and say that Insertion Sort is an “N2 time” algorithm. What this means
The running time of the algorithm against an array of N elements is N2. For 2N elements, it will be 4N2. Insertion Sort can work well for small inputs or if you know the data is likely to be nearly sorted, like check numbers as they are received by a bank. The running time becomes unreasonable for larger inputs.

Challenge
Can you modify your previous Insertion Sort implementation to keep track of the number of shifts it makes while sorting? The only thing you should print is the number of shifts made by the algorithm to completely sort the array. A shift occurs when an element’s position changes in the array. Do not shift an element if it is not necessary.

Function Description

Complete the runningTime function in the editor below. It should return an integer representing the number of shifts it will take to sort the given array.

runningTime has the following parameter(s):

• arr: an array of integers

Input Format

The first line contains the integer n, the number of elements to be sorted.
The next line contains n integers of arr[arr…arr[n-1]].

Constraints Output Format

Output the number of shifts it takes to sort the array.

Sample Input

5
2 1 3 1 2


Sample Output

4

Solution:

public class RunningTimeOfAlgorithms {
public static int shiftCount(int[] a) {
int count = 0;
for (int i = 0; i < a.length; i++) {
for (int j = i; j > 0; j--) {
if (a[j] < a[j - 1]) {
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
count++;
}
}
}

return count;
}

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(shiftCount(a));
sc.close();
}
}

Comparison Sorting
Quicksort usually has a running time of n x log(n), but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e. they sort a list just by comparing the elements to one another. A comparison sort algorithm cannot beat n x log(n) (worst-case) running time, since n x log(n) represents the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF).

Alternative Sorting
Another sorting method, the counting sort, does not require comparison. Instead, you create an integer array whose index range covers the entire range of values in your array to sort. Each time a value occurs in the original array, you increment the counter at that index. At the end, run through your counting array, printing the value of each non-zero valued index that number of times.

For example, consider an array arr = [1,1,3,2,1]. All of the values are in the range [0…3], so create an array of zeroes, result = [0,0,0,0]. The results of each iteration follow:

i	arr[i]	result
0	1	[0, 1, 0, 0]
1	1	[0, 2, 0, 0]
2	3	[0, 2, 0, 1]
3	2	[0, 2, 1, 1]
4	1	[0, 3, 1, 1]


Now we can print the list of occurrences, 0 3 1 1 or determine the sorted array: sorted = [1,1,1,2,3].

Challenge
Given a list of integers, count and output the number of times each value appears as a list of space-separated integers.

Function Description

Complete the countingSort function in the editor below. It should return an array of integers where each value is the number of occurrences of the element’s index value in the original array.

countingSort has the following parameter(s):

• arr: an array of integers

Input Format

The first line contains an integer n, the number of items in arr
Each of the next n lines contains an integer arr[i] where ≤ i < n.

Constraints

100 ≤ n ≤ 106

0 ≤ arr[i] ≤ 100

Output Format

Output the number of times every number from 0 through 99 appears in arr as a list of space-separated integers on one line.

Sample Input

100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10
94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33


Sample Output

0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0
0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2 

Solution:

public class CountingSort1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int a[] = new int;

for (int i = 0; i < N; i++) {
a[sc.nextInt()]++;
}
for (int j = 0; j < N; j++) {
System.out.print(a[j] + " ");
}
sc.close();
}
}

Often, when a list is sorted, the elements being sorted are just keys to other values. For example, if you are sorting files by their size, the sizes need to stay connected to their respective files. You cannot just take the size numbers and output them in order, you need to output all the required file information.

The counting sort is used if you just need to sort a list of integers. Rather than using a comparison, you create an integer array whose index range covers the entire range of values in your array to sort. Each time a value occurs in the original array, you increment the counter at that index. At the end, run through your counting array, printing the value of each non-zero valued index that number of times.

For example, consider an array arr = [1,1,3,2,1]. All of the values are in the range [0…3], so create an array of zeroes, result = [0,0,0,0]. The results of each iteration follow:

i	arr[i]	result
0	1	[0, 1, 0, 0]
1	1	[0, 2, 0, 0]
2	3	[0, 2, 0, 1]
3	2	[0, 2, 1, 1]
4	1	[0, 3, 1, 1]


Now we can print the sorted array: sorted = [1,1,1,2,3].

Challenge
Given an unsorted list of integers, use the counting sort method to sort the list and then print the sorted list.

Hint: You can use your previous code that counted the items to print out the actual values in order.

Function Description

Complete the countingSort function in the editor below. It should return the original array, sorted ascending, as an array of integers.

countingSort has the following parameter(s):

• arr: an array of integers

Input Format

The first line contains an integer n, the length of arr. The next line contains space-separated integers arr[i] where ≤ i < n.

Constraints

0 ≤ n ≤ 1000000

0 ≤ arr[i] ≤ 100

Output Format

Print the sorted list as a single line of space-separated integers.

Sample Input

100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50
30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33


Sample Output

1 1 3 3 6 8 9 9 10 12 13 16 16 18 20 21 21 22 23 24 25 25 25 27 27 30 30 32 32 32 33 33 33 34 39 39 40
40 41 42 43 44 44 46 46 48 50 53 56 56 57 59 60 61 63 65 67 67 68 69 69 69 70 70 73 73 74 75 75 76 78 78
79 79 80 81 81 82 83 83 84 85 86 86 87 87 89 89 89 90 90 91 92 94 95 96 98 98 99 99

Solution:

public class CountingSort2 {
public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int a[] = new int[N];
int b[] = new int;
int c[] = new int[N + 1];

for (int i = 0; i < N; i++) {
a[i] = sc.nextInt();
}

for (int i = 0; i < N; i++) {
b[a[i]]++;
}

for (int i = 1; i < 100; i++) {
b[i] = b[i] + b[i - 1];
}

for (int j = 0; j < N; j++) {
c[b[a[j]]] = a[j];
b[a[j]] = b[a[j]] - 1;
}

for (int j = 1; j <= N; j++) {
System.out.print(c[j] + " ");
}
sc.close();
}

}

In the previous challenge, it was easy to print all the integers in order, since you did not have to access the original list. Once you had obtained the frequencies of all the integers, you could simply print each integer in order the correct number of times. However, if there is other data associated with an element, you will have to access the original element itself.

In the final counting sort challenge, you are required to print the data associated with each integer. This means, you will go through the original array to get the data, and then use some “helper arrays” to determine where to place everything in a sorted array.

If you know the frequencies of each element, you know how many times to place it, but which index will you start placing it from? It will be helpful to create a helper array for the “starting values” of each element.

Challenge
You will be given a list that contains both integers and strings. In this challenge you just care about the integers. For every value i from 0 to 99, can you output L, the number of elements that are less than or equal to i?

Input Format
– n, the size of the list ar
– lines follow, each containing an integer x and a string s.

Output Format
Output L for all numbers from 0 to 99 (inclusive).

Constraints Sample Input

10
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the


Sample Output

1 3 5 6 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 

Solution:

public class CountingSort3 {
public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int a[] = new int[N];
int b[] = new int;

for (int i = 0; i < N; i++) {
a[i] = sc.nextInt();
sc.next();
}

for (int i = 0; i < N; i++) {
b[a[i]]++;
}

for (int i = 1; i < 100; i++) {
b[i] = b[i] + b[i - 1];
}

for (int j = 0; j < 100; j++) {
System.out.print(b[j] + " ");
}
sc.close();
}

}

About Tutorial Challenges
Many of the challenges on HackerRank are difficult and assume that you already know the relevant algorithms. These tutorial challenges are different. They break down algorithmic concepts into smaller challenges so that you can learn the algorithm by solving them. They are intended for those who already know some programming, however. You could be a student majoring in computer science, a self-taught programmer, or an experienced developer who wants an active algorithms review. Here’s a great place to learn by doing!

There will also be some challenges where you’ll get to apply what you’ve learned using the completed algorithms.

About the Challenges
Each challenge will describe a scenario and you will code a solution. As you progress through the challenges, you will learn some important concepts in algorithms. In each challenge, you will receive input on STDIN and you will need to print the correct output to STDOUT.

There may be time limits that will force you to make your code efficient. If you receive a “Terminated due to time out” message when you submit your solution, you’ll need to reconsider your method. If you want to test your code locally, each test case can be downloaded, inputs and expected results, using hackos. You earn hackos as you solve challenges, and you can spend them on these tests.

For many challenges, helper methods (like an array) will be provided for you to process the input into a useful format. You can use these methods to get started with your program, or you can write your own input methods if you want. Your code just needs to print the right output to each test case.

Sample Challenge
This is a simple challenge to get things started. Given a sorted array (arr) and a number (V), can you print the index location of V in the array?

For example, if arr = [1,2,3] and V = 3, you would print 2 for a zero-based index array.

If you are going to use the provided code for I/O, this next section is for you.

Function Description

Complete the introTutorial function in the editor below. It must return an integer representing the zero-based index of V.

introTutorial has the following parameter(s):

• arr: a sorted array of integers
• V: an integer to search for

The next section describes the input format. You can often skip it, if you are using included methods or code stubs.

Input Format

The first line contains an integer, V, a value to search for.
The next line contains an integer, n, the size of arr. The last line contains n space-separated integers, each a value of arr[i] where ≤ i ≤ n.

Output Format
Output the index of V in the array.

The next section describes the constraints and ranges of the input. You should check this section to know the range of the input.

Constraints

• 1 ≤ n ≤ 1000

• -1000 ≤ V ≤ 1000, V ∈ arr

• It is guaranteed that V will occur in arr exactly once.

This “sample” shows the first input test case. It is often useful to go through the sample to understand a challenge.

Sample Input 0

4
6
1 4 5 7 9 12


Sample Output 0

1

Solution:

public class IntroToTutorialChallenges {
public static int binarySearch(int a[], int key) {
int lo = 0;
int hi = a.length;
while (lo <= hi) {
int mid = (lo + (hi - lo) / 2);
if (a[mid] == key)
return mid;
if (a[mid] < key)
lo = mid + 1;
if (a[mid] > key)
hi = mid - 1;
}
return -1;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int key = in.nextInt();
int s = in.nextInt();
int[] ar = new int[s];
for (int i = 0; i < s; i++) {
ar[i] = in.nextInt();
}
System.out.println(binarySearch(ar, key));
in.close();
}
}

The median of a list of numbers is essentially it’s middle element after sorting. The same number of elements occur after it as before. Given a list of numbers with an odd number of elements, can you find the median?

For example, the median of arr = [1,2,3,4,5] is 3, the middle element in the sorted array.

Function Description

Complete the findMedian function in the editor below. It must return an integer that represents the median of the array.

findMedian has the following parameter(s):

• arr: an unsorted array of integers

Input Format

The first line contains the integer n, the size of arr
The second line contains n space-separated integers arr[i]

Constraints

• 1 ≤ n ≤ 1000001

• n is odd
• -10000 ≤ arr[i] ≤ 10000

Output Format

Output one integer, the median.

Sample Input 0

7
0 1 2 4 6 5 3


Sample Output 0

3

Solution:

public class FindTheMedian {

public static void main(String[] args) {
/*
* Enter your code here. Read input from STDIN. Print output to STDOUT. Your
* class should be named Solution.
*/
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();
Arrays.sort(a);
if ((n & 1) == 1) {
System.out.println(a[n / 2]);
} else {
System.out.println((a[n / 2] + a[n / 2 + 1]) / 2);
}
sc.close();
}
}

Sorting is useful as the first step in many different tasks. The most common task is to make finding things easier, but there are other uses as well. In this case, it will make it easier to determine which pair or pairs of elements have the smallest absolute difference between them.

For example, if you’ve got the list [5,2,3,4,1], sort it as [1,2,3,4,5] to see that several pairs have the minimum difference of 1[(1,2), (2,3), (3,4), (4,5)]. The return array would be [1,2,2,3,3,4,4,5].

Given a list of unsorted integers, arr, find the pair of elements that have the smallest absolute difference between them. If there are multiple pairs, find them all.

Function Description

Complete the closestNumbers function in the editor below. It must return an array of integers as described.

closestNumbers has the following parameter(s):

• arr: an array of integers

Input Format

The first line contains a single integer n, the length of arr
The second line contains n space-separated integers, arr[i].

Constraints Output Format

Output the pairs of elements with the smallest difference. If there are multiple pairs, output all of them in ascending order, all on the same line with just a single space between each pair of numbers. A number may be part of two pairs when paired with its predecessor and its successor.

Sample Input 0

10
-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854


Sample Output 0

-20 30

Solution:

public class ClosestNumbers {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
int a[] = new int[t];
for (int i = 0; i < t; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
int minDiff = Integer.MAX_VALUE;
int min1 = 0;
int min2 = 0, minIndex = -1;

String result = "";
for (int i = 1; i < t; i++) {
int diff = Math.abs(a[i] - a[i - 1]);
if (diff < minDiff) {
minDiff = diff;
min1 = a[i - 1];
min2 = a[i];
minIndex = i;
result = min1 + " " + min2;
}
}
for (int i = minIndex + 1; i < t; i++) {
if (minDiff == Math.abs(a[i] - a[i - 1])) {
result = result + " " + a[i - 1] + " " + a[i];
}
}
System.out.println(result);
sc.close();
}
}

Mark and Jane are very happy after having their first child. Their son loves toys, so Mark wants to buy some. There are a number of different toys lying in front of him, tagged with their prices. Mark has only a certain amount to spend, and he wants to maximize the number of toys he buys with this money.

Given a list of prices and an amount to spend, what is the maximum number of toys Mark can buy? For example, if prices = [1,2,3,4] and Mark has k = 7 to spend, he can buy items [1,2,3] for 6, or [3,4] for 7 units of currency. He would choose the first group of 3 items.

Function Description

Complete the function maximumToys in the editor below. It should return an integer representing the maximum number of toys Mark can purchase.

maximumToys has the following parameter(s):

• prices: an array of integers representing toy prices
• k: an integer, Mark’s budget

Input Format

The first line contains two integers, n and k, the number of priced toys and the amount Mark has to spend.
The next line contains n space-separated integers prices[i]

Constraints A toy can’t be bought multiple times.

Output Format

An integer that denotes the maximum number of toys Mark can buy for his son.

Sample Input

7 50
1 12 5 111 200 1000 10


Sample Output

4

Solution:

public class MarkAndToys {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int K = in.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = in.nextInt();
}
Arrays.sort(a);
int toyCount = 0, sum = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
if (sum <= K) {
toyCount++;
} else {
break;
}
}
System.out.println(toyCount);
in.close();
}
}

Jim’s Burgers has a line of hungry customers. Orders vary in the time it takes to prepare them. Determine the order the customers receive their orders. Start by numbering each of the customers from 1 to n, front of the line to the back. You will then be given an order number and a preparation time for each customer.

The time of delivery is calculated as the sum of the order number and the preparation time. If two orders are delivered at the same time, assume they are delivered in ascending customer number order.

For example, there are n = 5 customers in line. They each receive an order number order[i] and a preparation time prep[i].:

Customer	1	2	3	4	5
Order #		8	5	6	2	4
Prep time	3	6	2	3	3
Calculate:
Serve time	11	11	8	5	7


We see that the orders are delivered to customers in the following order:

Order by:
Serve time	5	7	8	11	11
Customer	4	5	3	1	2


Function Description

Complete the jimOrders function in the editor below. It should return an array of integers that represent the order that customers’ orders are delivered.

jimOrders has the following parameter(s):

• orders: a 2D integer array where each orders[i] is in the form [order[i], prep[i]].

Input Format

The first line contains an integer n, the number of customers.
Each of the next n lines contains two space-separated integers, an order number and prep time for customer[i].

Constraints Output Format

Print a single line of n space-separated customer numbers (recall that customers are numbered from 1 to n) that describes the sequence in which the customers receive their burgers. If two or more customers receive their burgers at the same time, print their numbers in ascending order.

Sample Input 0

3
1 3
2 3
3 3


Sample Output 0

1 2 3

Solution:

public class JimAndTheOrders {
public static void main(String[] args) {
Map<Integer, Integer> hmap = new LinkedHashMap<Integer, Integer>();
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
for (int i = 1; i <= N; i++) {
int key = i;
int value = sc.nextInt() + sc.nextInt();
hmap.put(key, value);
}

Set<Entry<Integer, Integer>> set = hmap.entrySet();
List<Entry<Integer, Integer>> list = new ArrayList<Entry<Integer, Integer>>(set);
Collections.sort(list, new Comparator<Entry<Integer, Integer>>() {
public int compare(Entry<Integer, Integer> e1, Entry<Integer, Integer> e2) {
return e1.getValue().compareTo(e2.getValue());
}
});

for (Entry<Integer, Integer> i : list) {
System.out.print(i.getKey() + " ");
}
sc.close();
}
}

You will be given an array of integers. All of the integers except one occur twice. That one is unique in the array.

Given an array of integers, find and print the unique element.

For example, a = [1,2,3,4,3,2,1], the unique element is 4.

Function Description

Complete the lonelyinteger function in the editor below. It should return the integer which occurs only once in the input array.

lonelyinteger has the following parameter(s):

• a: an array of integers

Input Format

The first line contains a single integer, n, denoting the number of integers in the array.
The second line contains n space-separated integers describing the values in a.

Constraints

• 1 ≤ n ≤ 100

• It is guaranteed that n is an odd number and that there is one unique element.
• 0 ≤ a[i] ≤ 100, where 0 ≤ i ≤ n.

Output Format

Print the unique integer in the array.

Sample Input 0

1
1


Sample Output 0

1

Solution:

public class LonelyInteger {
static int lonelyinteger(int[] a) {
int result = 0;
for (int i = 0; i < a.length; i++) {
result ^= a[i];

}

return result;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int res;

int _a_size = Integer.parseInt(in.nextLine());
int[] _a = new int[_a_size];
int _a_item;
String next = in.nextLine();
String[] next_split = next.split(" ");

for (int _a_i = 0; _a_i < _a_size; _a_i++) {
_a_item = Integer.parseInt(next_split[_a_i]);
_a[_a_i] = _a_item;
}

res = lonelyinteger(_a);
System.out.println(res);
in.close();
}
}

Consider an array of integers where all but one of the integers occur in pairs. In other words, every element occurs exactly twice except for one unique element. Find the unique element.

For example, given the array arr = [1,1,2,3,2], you would return 3.

Function Description

Complete the findLonely function in the editor below. It should return the unique integer in arr.

findLonely has the following parameter(s):

• arr: an array of integers

Input Format

The first line contains a single integer, n, denoting the number of integers in arr
The second line contains n space-separated integers, each an element, arr[i].

Constraints

• 1 ≤ n < 100

• It is guaranteed that n is an odd number.
• 0 ≤ arr[i] ≤ 100, where 0 ≤ i < n.

Output Format

Print the unique number in arr on a new line.

Sample Input 0

1
1


Sample Output 0

1

Solution:

public class BitManipulationLonelyInteger {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int res = 0;
for (int i = 0; i < n; i++) {
res ^= sc.nextInt();
}
System.out.println(res);
sc.close();
}
}

Sunny and Johnny like to pool their money and go to the ice cream parlor. Johnny never buys the same flavor that Sunny does. The only other rule they have is that they spend all of their money.

Given a list of prices for the flavors of ice cream, select the two that will cost all of the money they have.

For example, they have m = 6 to spend and there are flavors costing cost = [1,3,4,5,6]. The two flavors costing 1 and meet the criteria. Using 1-based indexing, they are at indices 1 and 4.

Function Description

Complete the icecreamParlor function in the editor below. It should return an array containing the indices of the prices of the two flavors they buy, sorted ascending.

icecreamParlor has the following parameter(s):

• m: an integer denoting the amount of money they have to spend
• cost: an integer array denoting the cost of each flavor of ice cream

Input Format

The first line contains an integer, t, denoting the number of trips to the ice cream parlor. The next t sets of lines each describe a visit. Each trip is described as follows:

1. The integer m, the amount of money they have pooled.
2. The integer n, the number of flavors offered at the time.
3. n space-separated integers denoting the cost of each flavor: cost[cost,cost,…,cost[n]].

Note: The index within the cost array represents the flavor of the ice cream purchased.

Constraints Output Format

For each test case, print two space-separated integers denoting the indices of the two flavors purchased, in ascending order.

Sample Input

2
4
5
1 4 5 3 2
4
4
2 2 4 3


Sample Output

1 4
1 2

Solution:

public class IceCreamParlor {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
int m = sc.nextInt();
int n = sc.nextInt();
int a[] = new int[n];
for (int j = 0; j < n; j++) {
a[j] = sc.nextInt();
}

for (int j = 0; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (m == a[j] + a[k]) {
if (j > k) {
System.out.println(++k + " " + ++j);
} else {
System.out.println(++j + " " + ++k);
}
break;
}

}
}
}
sc.close();
}
}

Each time Sunny and Johnny take a trip to the Ice Cream Parlor, they pool their money to buy ice cream. On any given day, the parlor offers a line of flavors. Each flavor has a cost associated with it.

Given the value of money and the cost of each flavor for t trips to the Ice Cream Parlor, help Sunny and Johnny choose two distinct flavors such that they spend their entire pool of money during each visit. ID numbers are the 1- based index number associated with a cost. For each trip to the parlor, print the ID numbers for the two types of ice cream that Sunny and Johnny purchase as two space-separated integers on a new line. You must print the smaller ID first and the larger ID second.

For example, there are n =5 flavors having cost = [2,1,3,5,6]. Together they have money = 5 to spend. They would purchase flavor ID’s 1 and 3 for a cost of 2 + 3 = 5. Use 1 based indexing for your response.

Note:

• Two ice creams having unique IDs  and  may have the same cost (i.e., ).
• There will always be a unique solution.

Function Description

Complete the function whatFlavors in the editor below. It must determine the two flavors they will purchase and print them as two space-separated integers on a line.

whatFlavors has the following parameter(s):

• cost: an array of integers representing price for a flavor
• money: an integer representing the amount of money they have to spend

Input Format

The first line contains an integer, t, the number of trips to the ice cream parlor.

Each of the next t sets of 3 lines is as follows:

• The first line contains money.
• The second line contains an integer, n, the size of the array cost.
• The third line contains n space-separated integers denoting the cost[i].

Constraints Output Format

Print two space-separated integers denoting the respective indices for the two distinct flavors they choose to purchase in ascending order. Recall that each ice cream flavor has a unique ID number in the inclusive range from 1 to |cost|.

Sample Input

2
4
5
1 4 5 3 2
4
4
2 2 4 3


Sample Output

1 4
1 2

Solution:

public class HashTablesIceCreamParlor {
static void solve(int[] arr, int money) {
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
int len=arr.length;
for(int i=1;i<=len;i++){
map.put(arr[i-1], i);
}
for(int i=1;i<=len;i++){
if(map.containsKey(arr[i-1]) && map.containsKey(Math.abs(money-arr[i-1]))) {
System.out.println(i+" "+map.get(Math.abs(money-arr[i-1])));
break;
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for (int a0 = 0; a0 < t; a0++) {
int money = in.nextInt();
int n = in.nextInt();
int[] arr = new int[n];
for (int arr_i = 0; arr_i < n; arr_i++) {
arr[arr_i] = in.nextInt();
}
solve(arr, money);
}
in.close();
}
}

Lauren has a chart of distinct projected prices for a house over the next several years. She must buy the house in one year and sell it in another, and she must do so at a loss. She wants to minimize her financial loss.

For example, the house is valued at price = [20,15,8,2,12] over the next n = 5 years. She can purchase the home in any year, but she must resell the house at a loss in one of the following years. Her minimum loss would be incurred by purchasing in year 2 at price = 15 and reselling in year 5 at price = 12.

Find and print the minimum amount of money Lauren must lose if she buys the house and resells it within the next n years.

Note: It’s guaranteed that a valid answer exists.

Function Description

Complete the minimumLoss function in the editor below. It should return an integer that represents the minimum loss that can be achieved.

minimumLoss has the following parameter(s):

• price: an array of integers that represent prices at each year

Input Format

The first line contains an integer n, the number of years of house data.
The second line contains n space-separated long integers describing each price[i].

Constraints

• 2 ≤ n ≤ 2 x 105

• ≤ price[i] ≤ 1016

• All the prices are distinct.
• A valid answer exists.

Subtasks

• 2≤ n ≤ 1000 for 50% of the maximum score.

Output Format

Print a single integer denoting the minimum amount of money Lauren must lose if she buys and resells the house within the next n years.

Sample Input 0

3
5 10 3


Sample Output 0

2

Solution:

public class MinimumLoss {
static int minimumLoss(long[] price) {
Map<Long,Integer> map=new HashMap<Long,Integer>();
for(int i=0;i<price.length;i++) {
map.put(price[i], i);
}
Arrays.sort(price);
long min=Long.MAX_VALUE;
for(int i=price.length-1;i>0;i--) {
long diff=price[i]-price[i-1];
if( diff

Watson gives Sherlock an array of integers. His challenge is to find an element of the array such that the sum of all elements to the left is equal to the sum of all elements to the right. For instance, given the array arr = [5,6,8,11]8 is between two subarrays that sum to 11. If your starting array is , that element satisfies the rule as left and right sum to 0.

You will be given arrays of integers and must determine whether there is an element that meets the criterion.

Function Description

Complete the balancedSums function in the editor below. It should return a string, either YES if there is an element meeting the criterion or NO otherwise.

balancedSums has the following parameter(s):

• arr: an array of integers

Input Format

The first line contains T, the number of test cases.

The next T pairs of lines each represent a test case.
– The first line contains n, the number of elements in the array arr
– The second line contains n space-separated integers arr[i] where 0 ≤ i ≤ n.

Constraints Output Format

For each test case print YES if there exists an element in the array, such that the sum of the elements on its left is equal to the sum of the elements on its right; otherwise print NO.

Sample Input 0

2
3
1 2 3
4
1 2 3 3


Sample Output 0

NO
YES

Solution:

public class SherlockAndArray {

static String balancedSums(List arr) {
int x = 0;
int sum = 0;
for (int a : arr) {
sum += a;
}

for (int y : arr) {
if (2 * x == sum - y) {
return "YES";
}
x = x + y;
}
return "NO";

}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int n = sc.nextInt();
List list = new ArrayList();
for (int i = 0; i < n; i++) {
list.add(sc.nextInt());
}
System.out.println(balancedSums(list));
}
sc.close();
}

}

You have three stacks of cylinders where each cylinder has the same diameter, but they may vary in height. You can change the height of a stack by removing and discarding its topmost cylinder any number of times.

Find the maximum possible height of the stacks such that all of the stacks are exactly the same height. This means you must remove zero or more cylinders from the top of zero or more of the three stacks until they’re all the same height, then print the height. The removals must be performed in such a way as to maximize the height.

Note: An empty stack is still a stack.

Input Format

The first line contains three space-separated integers,n1 ,n2 , and n3 , describing the respective number of cylinders in stacks 1, 2, and 3. The subsequent lines describe the respective heights of each cylinder in a stack from top to bottom:

• The second line contains n1 space-separated integers describing the cylinder heights in stack 1. The first element is the top of the stack.
• The third line contains n2 space-separated integers describing the cylinder heights in stack 2. The first element is the top of the stack.
• The fourth line contains n3 space-separated integers describing the cylinder heights in stack 3. The first element is the top of the stack.

Constraints Output Format

Print a single integer denoting the maximum height at which all stacks will be of equal height.

Sample Input

5 3 4
3 2 1 1 1
4 3 2
1 1 4 1


Sample Output

5

Solution:

public class EqualStacks {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n1 = in.nextInt();
int n2 = in.nextInt();
int n3 = in.nextInt();
int h1[] = new int[n1];
for (int h1_i = 0; h1_i < n1; h1_i++) {
h1[h1_i] = in.nextInt();
}
int h2[] = new int[n2];
for (int h2_i = 0; h2_i < n2; h2_i++) {
h2[h2_i] = in.nextInt();
}
int h3[] = new int[n3];
for (int h3_i = 0; h3_i < n3; h3_i++) {
h3[h3_i] = in.nextInt();
}

Stack st1 = new Stack();
Stack st2 = new Stack();
Stack st3 = new Stack();
long sum1 = 0, sum2 = 0, sum3 = 0;
for (int i = h1.length - 1; i >= 0; i--) {
sum1 += h1[i];
st1.push(sum1);
}
for (int i = h2.length - 1; i >= 0; i--) {
sum2 += h2[i];
st2.push(sum2);
}
for (int i = h3.length - 1; i >= 0; i--) {
sum3 += h3[i];
st3.push(sum3);
}

boolean found = false;
if (n1 <= n2 && n1 <= n3) {
while (!st1.isEmpty()) {
long top = st1.pop();
if (st2.contains(top) && st3.contains(top)) {
System.out.println(top);
found = true;
break;
}
}

} else if (n2 <= n3 && n2 <= n1) {
while (!st2.isEmpty()) {
long top = st2.pop();
if (st1.contains(top) && st3.contains(top)) {
System.out.println(top);
found = true;
break;
}
}

} else if (n3 <= n1 && n3 <= n2) {
while (!st3.isEmpty()) {
long top = st3.pop();
if (st2.contains(top) && st1.contains(top)) {
System.out.println(top);
found = true;
break;
}
}
}
if (!found) {
System.out.println("0");
}
in.close();
}
}

Priyanka works for an international toy company that ships by container. Her task is to the determine the lowest cost way to combine her orders for shipping. She has a list of item weights. The shipping company has a requirement that all items loaded in a container must weigh less than or equal to 4 units plus the weight of the minimum weight item. All items meeting that requirement will be shipped in one container.

What is the smallest number of containers that can be contracted to ship the items based on the given list of weights?

For example, there are items with weights w = [1,2,3,4,5,10,11,12,13]. This can be broken into two containers: [1,2,3,4,5] and [10,11,12,13]. Each container will contain items weighing within 4 units of the minimum weight item.

Function Description

Complete the toys function in the editor below. It should return the minimum number of containers required to ship.

toys has the following parameter(s):

• w: an array of integers that represent the weights of each order to ship

Input Format

The first line contains an integer n, the number of orders to ship.
The next line contains n space-separated integers, w,w,…,w[n], representing the orders in a weight array.

Constraints Output Format

Return the integer value of the number of containers Priyanka must contract to ship all of the toys.

Sample Input

8
1 2 3 21 7 12 14 21


Sample Output

4

Solution:

public class PriyankaAndToys {
static int toys(int[] w) {
Arrays.sort(w);
int containerCouter = 1, weightLimit = w;
for (int i = 0; i < w.length; i++) {
if (w[i] > weightLimit + 4) {
weightLimit = w[i];
containerCouter++;
}
}
return containerCouter;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] w = new int[n];
for (int w_i = 0; w_i < n; w_i++) {
w[w_i] = in.nextInt();
}
int result = toys(w);
System.out.println(result);
in.close();
}
}

Given an undirected weighted connected graph, find the Really Special SubTree in it. The Really Special SubTree is defined as a subgraph consisting of all the nodes in the graph and:

• There is only one exclusive path from a node to every other node.
• The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.
• No cycles are formed

To create the Really Special SubTree, always pick the edge with smallest weight. Determine if including it will create a cycle. If so, ignore the edge. If there are edges of equal weight available:

• Choose the edge that minimizes the sum u + v + wt where u and v are vertices and wt is the edge weight.
• If there is still a collision, choose any of them.

Print the overall weight of the tree formed using the rules.

For example, given the following edges:

u	v	wt
1	2	2
2	3	3
3	1	5


First choose  at weight . Next choose  at weight . All nodes are connected without cycles for a total weight of .

Function Description

Complete the kruskals function in the editor below. It should return an integer that represents the total weight of the subtree formed.

kruskals has the following parameters:

• g_nodes: an integer that represents the number of nodes in the tree
• g_from: an array of integers that represent beginning edge node numbers
• g_to: an array of integers that represent ending edge node numbers
• g_weight: an array of integers that represent the weights of each edge

Input Format

The first line has two space-separated integers g_nodes and g_edges, the number of nodes and edges in the graph.

The next g_edges lines each consist of three space-separated integers g_fromg_to and g_weight, where g_from and g_to denote the two nodes between which the undirected edge exists and g_weight denotes the weight of that edge.

Constraints **Note: ** If there are edges between the same pair of nodes with different weights, they are to be considered as is, like multiple edges.

Output Format

Print a single integer denoting the total weight of the Really Special SubTree.

Sample Input 1 Sample Output 1

12

Solution:

public class KruskalMSTReallySpecialSubtree {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
EdgeWeightedGraph G = new EdgeWeightedGraph(sc);
KruskalMST kmst = new KruskalMST(G);
System.out.println((int) kmst.weight());
}
}

class KruskalMST {

private Queue mst;
private double weight;

public KruskalMST(EdgeWeightedGraph G) {
mst = new LinkedList();
PriorityQueue pq = new PriorityQueue();
for (Edge e : G.edges()) {
pq.add(e);
}
UF uf = new UF(G.V());
while (!pq.isEmpty() && mst.size() < G.V() - 1) {
Edge e = pq.poll();
int v = e.either();
int w = e.other(v);
if (uf.connected(v, w))
continue;
uf.union(v, w);
mst.add(e);
weight += e.weight();
}
}

public Iterable edges() {
return mst;
}

public double weight() {
return weight;
}
}

class EdgeWeightedGraph {
private final int V;
private int E;
private final ArrayList[] adj;

@SuppressWarnings("unchecked")
public EdgeWeightedGraph(int V) {
super();
this.V = V;
this.E = 0;
this.adj = (ArrayList[]) new ArrayList[V + 1];
for (int v = 1; v <= V; v++)
adj[v] = new ArrayList();
}

public EdgeWeightedGraph(Scanner sc) {
this(sc.nextInt());
int E = sc.nextInt();
for (int i = 0; i < E; i++) {
int v = sc.nextInt();
int w = sc.nextInt();
double weight = sc.nextDouble();
Edge e = new Edge(v, w, weight);
addEdge(e);
}
}

public void addEdge(Edge e) {
int v = e.either();
int w = e.other(v);
adj[v].add(e);
adj[w].add(e);
E++;
}

public Iterable adj(int v) {
return adj[v];
}

public int V() {
return V;
}

public Iterable edges() {
ArrayList edges = new ArrayList();
for (int v = 1; v <= V; v++) {
for (Edge e : adj[v]) {
if (e.other(v) > v)
edges.add(e);
}
}
return edges;
}

@Override
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " " + E + "\n");
for (int v = 0; v < V; v++) {
s.append(v + ":");
for (Edge e : adj[v]) {
s.append(e + " ");
}
s.append("\n");
}
return s.toString();
}

}

class Edge implements Comparable {
private final int v, w;
private final double weight;

public Edge(int v, int w, double weight) {
super();
this.v = v;
this.w = w;
this.weight = weight;
}

public int either() {
return v;
}

public int other(int vertex) {
if (vertex == v)
return w;
return v;
}

public int compareTo(Edge that) {
if (this.weight > that.weight)
return 1;
if (this.weight < that.weight)
return -1;
return 0;
}

public double weight() {
return weight;
}

@Override
public String toString() {
return String.format("%d-%d %.5f", v, w, weight);
}

}

class UF {
int[] id;
int count;

public UF(int N) {
super();
count = N;
id = new int[N + 1];
for (int i = 1; i <= N; i++)
id[i] = i;
}

public int count() {
return count;
}

public boolean connected(int p, int q) {
return find(p) == find(q);
}

private int find(int p) {
return id[p];
}

public void union(int p, int q) {
int pId = find(p);
int qId = find(q);

if (pId == qId)
return;

for (int i = 0; i < id.length; i++)
if (id[i] == pId)
id[i] = qId;
count--;
}
}

Consider an undirected graph where each edge is the same weight. Each of the nodes is labeled consecutively.

You will be given a number of queries. For each query, you will be given a list of edges describing an undirected graph. After you create a representation of the graph, you must determine and report the shortest distance to each of the other nodes from a given starting position using the breadth-first search algorithm (BFS). Distances are to be reported in node number order, ascending. If a node is unreachable, print -1 for that node. Each of the edges weighs 6 units of distance.

For example, given a graph with 5 nodes and 3 edges, [1,2], [1,3], [3,4], a visual representation is: The start node for the example is node 1. Outputs are calculated for distances to nodes 2 through 5[6,6,12,-1]. Each edge is 6 units, and the unreachable node 5 has the required return distance of -1.

Function Description

Complete the bfs function in the editor below. It must return an array of integers representing distances from the start node to each other node in node ascending order. If a node is unreachable, its distance is -1.

bfs has the following parameter(s):

• n: the integer number of nodes
• m: the integer number of edges
• edges: a 2D array of start and end nodes for edges
• s: the node to start traversals from

Input Format

The first line contains an integer q, the number of queries. Each of the following q sets of lines has the following format:

• The first line contains two space-separated integers n and m, the number of nodes and edges in the graph.
• Each line i of the m subsequent lines contains two space-separated integers, u and v, describing an edge connecting node u to node v.
• The last line contains a single integer, s, denoting the index of the starting node.

Constraints Output Format

For each of the q queries, print a single line of n – 1 space-separated integers denoting the shortest distances to each of the n – 1 other nodes from starting position s. These distances should be listed sequentially by node number (i.e., 1,2,…,n), but should not include node s. If some node is unreachable from s, print -1 as the distance to that node.

Sample Input

2
4 2
1 2
1 3
1
3 1
2 3
2


Sample Output

6 6 -1
-1 6

Solution:

class Graph {

private final int V;
private int E;
private ArrayList[] adj;

@SuppressWarnings("unchecked")
Graph(int V) {
adj = (ArrayList[]) new ArrayList[V + 1];
this.V = V;
this.E = 0;
for (int v = 1; v <= V; v++)
adj[v] = new ArrayList(V);
}

Graph(Scanner in) {
this(in.nextInt());
int E = in.nextInt();
for (int i = 0; i < E; i++) {
int v = in.nextInt();
int w = in.nextInt();
addEdge(v, w);
}
}

public int V() {
return V;
}

public int E() {
return E;
}

public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
E++;
}

public Iterable adj(int v) {
return adj[v];
}

}

class BreadthFirstPaths {
private int s;
private boolean marked[];
private int edgeTo[];

BreadthFirstPaths(Graph G, int s) {
marked = new boolean[G.V() + 1];
this.s = s;
edgeTo = new int[G.V() + 1];
bfs(G, s);
}

private void bfs(Graph G, int s) {
Queue q = (Queue) new LinkedList();
q.add(s);
while (!q.isEmpty()) {
int v = q.poll();
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
marked[w] = true;
edgeTo[w] = v;
q.add(w);
}
}
}

}

public Iterable pathTo(int v) {
if (!hasPathTo(v))
return null;
Stack path = new Stack();
for (int x = v; x != s; x = edgeTo[x])
path.push(x);
path.push(s);
return path;

}

public boolean hasPathTo(int v) {
return marked[v];
}

}

public class BreadthFirstSearchShortestReach {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
for (int i = 0; i < q; i++) {
Graph G = new Graph(sc);
int s = sc.nextInt();
BreadthFirstPaths bfp = new BreadthFirstPaths(G, s);
for (int v = 1; v <= G.V(); v++) {
if (s != v) {
if (bfp.hasPathTo(v)) {
Stack st = (Stack) bfp.pathTo(v);
int sum = 0;
for (int x = 1; x < st.size(); x++) {
sum += 6;
}
System.out.print(sum + " ");

} else {
System.out.print(-1 + " ");
}
}
}
System.out.println();
}
}

}

Given a graph which consists of several edges connecting its nodes, find a subgraph of the given graph with the following properties:

• The subgraph contains all the nodes present in the original graph.
• The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.
• It is also required that there is exactly one, exclusive path between any two nodes of the subgraph.

One specific node S is fixed as the starting point of finding the subgraph using Prim’s Algorithm
Find the total weight or the sum of all edges in the subgraph. For example, consider a graph with 3 nodes. Possible edges are 1<->2 weight 22 <-> 3 weight 2 and 1 <-> 3 weight 3. Starting from node 1, we select the lower weight path, i.e. 1<->2 , weight 2. From node 2, there is only one path left, 2<->3  weight 2. We have all nodes connected at a cost of 2 + 2 = 4.

Function Description

Complete the prims function in the editor below. It should return and integer that represents the minimum weight to connect all nodes in the graph provided.

prims has the following parameter(s):

• n: an integer that represents the number of nodes in the graph
• edges: a two-dimensional array where each element contains three integers, two nodes numbers that are connected and the weight of that edge
• start: an integer that represents the number of the starting node

Input Format

The first line has two space-separated integers n and m, the number of nodes and edges in the graph.

Each of the next m lines contains three space-separated integers xy and r, the end nodes of edges[i], and the edge’s weight.
The last line has an integer start, denoting the starting node.

Constraints There may be multiple edges between two nodes.

Output Format

Print a single integer denoting the total weight of the subgraph.

Sample Input 0

5 6
1 2 3
1 3 4
4 2 6
5 2 2
2 3 5
3 5 7
1


Sample Output 0

15

Solution:

public class PrimsMSTSpecialSubtree {

static class EdgeWeightedGraph {
private final int V;
private int E;
private final ArrayList[] adj;

@SuppressWarnings("unchecked")
public EdgeWeightedGraph(int V) {
super();
this.V = V;
this.E = 0;
this.adj = (ArrayList[]) new ArrayList[V + 1];
for (int v = 1; v <= V; v++)
adj[v] = new ArrayList();
}

public EdgeWeightedGraph(Scanner sc) {
this(sc.nextInt());
int E = sc.nextInt();
for (int i = 0; i < E; i++) {
int v = sc.nextInt();
int w = sc.nextInt();
double weight = sc.nextDouble();
Edge e = new Edge(v, w, weight);
addEdge(e);
}
}

public void addEdge(Edge e) {
int v = e.either();
int w = e.other(v);
adj[v].add(e);
adj[w].add(e);
E++;
}

public Iterable adj(int v) {
return adj[v];
}

public int V() {
return V;
}

public Iterable edges() {
ArrayList edges = new ArrayList();
for (int v = 1; v <= V; v++) {
for (Edge e : adj[v]) {
if (e.other(v) > v)
edges.add(e);
}
}
return edges;
}

@Override
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " " + E + "\n");
for (int v = 0; v < V; v++) {
s.append(v + ":");
for (Edge e : adj[v]) {
s.append(e + " ");
}
s.append("\n");
}
return s.toString();
}

}

static class Edge implements Comparable {
private final int v, w;
private final double weight;

public Edge(int v, int w, double weight) {
super();
this.v = v;
this.w = w;
this.weight = weight;
}

public int either() {
return v;
}

public int other(int vertex) {
if (vertex == v)
return w;
return v;
}

public int compareTo(Edge that) {
if (this.weight > that.weight)
return 1;
if (this.weight < that.weight)
return -1;
return 0;
}

public double weight() {
return weight;
}

@Override
public String toString() {
return String.format("%d-%d %.5f", v, w, weight);
}

}

static class LazyPrimMST {

private boolean[] marked;
private Queue mst;
private PriorityQueue pq;
private double weight;

public LazyPrimMST(EdgeWeightedGraph G) {
super();
pq = new PriorityQueue();
mst = new LinkedList();
marked = new boolean[G.V() + 1];
for (int v = 1; v <= G.V(); v++)
if (!marked[v])
prim(G, v);

}

/**
* @param g
* @param v
*/
private void prim(EdgeWeightedGraph G, int s) {
scan(G, s);
while (!pq.isEmpty()) {
Edge e = pq.poll();
int v = e.either();
int w = e.other(v);
if (marked[v] && marked[w])
continue;
mst.add(e);
weight += e.weight();
if (!marked[v])
scan(G, v);
if (!marked[w])
scan(G, w);
}

}

/**
* @param g
* @param s
*/
private void scan(EdgeWeightedGraph G, int v) {
marked[v] = true;
for (Edge e : G.adj(v))
if (!marked[e.other(v)])
pq.add(e);

}

public Iterable edges() {
return mst;
}

public double weight() {
return weight;
}

}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
EdgeWeightedGraph G = new EdgeWeightedGraph(sc);
LazyPrimMST mst = new LazyPrimMST(G);
System.out.println((int) mst.weight());
}
}

Steve has a string of lowercase characters in range ascii[‘a’..’z’]. He wants to reduce the string to its shortest length by doing a series of operations. In each operation he selects a pair of adjacent lowercase letters that match, and he deletes them. For instance, the string aab could be shortened to b in one operation.

Steve’s task is to delete as many characters as possible using this method and print the resulting string. If the final string is empty, print Empty String

Function Description

Complete the superReducedString function in the editor below. It should return the super reduced string or Empty String if the final string is empty.

superReducedString has the following parameter(s):

• s: a string to reduce

Input Format

A single string, s.

Constraints

• 1 ≤ |s| ≤ 100

Output Format

If the final string is empty, print Empty String; otherwise, print the final non-reducible string.

Sample Input 0

aaabccddd


Sample Output 0

abd

Solution:

public class SuperReducedString {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
String value = getReducedString(s);
System.out.println(value == "" ? "Empty String" : value);
sc.close();
}

private static String getReducedString(String s) {
char[] ch = s.toCharArray();
Stack st = new Stack();
for (int i = 0; i < ch.length; i++) {
if (st.empty()) {
st.push(ch[i]);

} else if (st.peek() == ch[i]) {
st.pop();
} else {
st.push(ch[i]);

}
}
String str = "";
while (!st.isEmpty()) {
str = st.pop() + str;
}
return str;
}

}

Julius Caesar protected his confidential information by encrypting it using a cipher. Caesar’s cipher shifts each letter by a number of letters. If the shift takes you past the end of the alphabet, just rotate back to the front of the alphabet. In the case of a rotation by 3, w, x, y and z would map to z, a, b and c.

Original alphabet:      abcdefghijklmnopqrstuvwxyz
Alphabet rotated +3:    defghijklmnopqrstuvwxyzabc


For example, the given cleartext s = There’s-a-starman-waiting-in-the-sky and the alphabet is rotated by k = 3. The encrypted string is Wkhuh’v-d-vwdupdq-zdlwlqj-lq-wkh-vnb.

Note: The cipher only encrypts letters; symbols, such as -, remain unencrypted.

Function Description

Complete the caesarCipher function in the editor below. It should return the encrypted string.

caesarCipher has the following parameter(s):

• s: a string in cleartext
• k: an integer, the alphabet rotation factor

Input Format

The first line contains the integer, n, the length of the unencrypted string.
The second line contains the unencrypted string, s
The third line contains k, the number of letters to rotate the alphabet by.

Constraints

1 ≤ n ≤ 100

0 ≤ k ≤ 100
s is a valid ASCII string without any spaces.

Output Format

For each test case, print the encoded string.

Sample Input

11
middle-Outz
2


Sample Output

okffng-Qwvb

Solution:

public class CaesarCipher {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String s = sc.next();
int K = sc.nextInt();
K = K % 26;
String passwd = "";
for (int i = 0; i < N; i++) {
int ch = s.charAt(i);
int t = (ch + K);

if (ch >= 97 && ch <= 122) {
if (t > 122) {
t = 96 + (t - 122);
}
passwd += (char) (t);
} else if (ch >= 65 && ch <= 90) {
if (t > 90) {
t = 64 + (t - 90);
}
passwd += (char) (t);
} else {
passwd += (char) ch;
}
}
System.out.println(passwd);
sc.close();
}
}

John has collected various rocks. Each rock has various minerals embeded in it. Each type of mineral is designated by a lowercase letter in the range ascii[a – z]. There may be multiple occurrences of a mineral in a rock. A mineral is called a gemstone if it occurs at least once in each of the rocks in John’s collection.

Given a list of minerals embedded in each of John’s rocks, display the number of types of gemstones he has in his collection.

For example, the array of mineral composition strings arr = [abc,abc,bc]. The minerals b and c appear in each composite, so there are 2 gemstones.

Function Description

Complete the gemstones function in the editor below. It should return an integer representing the number of gemstones found in the list of rocks.

gemstones has the following parameter(s):

• arr: an array of strings

Input Format

The first line consists of an integer n, the size of arr
Each of the next n lines contains a string arr[i] where each letter represents an occurence of a mineral in the current rock.

Constraints

1 ≤ n ≤ 100

1 ≤ |arr[i]| ≤ 100

Each composition arr[i] consists of only lower-case Latin letters (‘a’-‘z’).

Output Format

Print the number of types of gemstones in John’s collection. If there are none, print 0.

Sample Input

3
abcdde
baccd
eeabg


Sample Output

2

Solution:

public class Gemstones {
static int gemstones(String[] arr) {
int rockNum = 0;
int gemCount=0;
int[] compositions = new int;
int noOfRocks = arr.length;
for (rockNum= 1; rockNum <= noOfRocks; rockNum++) {
String rock = arr[rockNum-1];
storeComposition(compositions, rock, rockNum);
}
for(int element:compositions) {
if(element==noOfRocks)
gemCount++;
}
return gemCount;
}

/**
* @param compositions
* @param rock
*/
private static void storeComposition(int[] compositions, String rock, int rockNum) {
for (int i = 0; i < rock.length(); i++) {
int index = rock.charAt(i) - 'a';
if(rockNum==1) {
compositions[index]=1;
}else {
if (compositions[index] >= rockNum - 1)
compositions[index] = rockNum;
}
}
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String[] arr = new String[n];
for (int arr_i = 0; arr_i < n; arr_i++) {
arr[arr_i] = in.next();
}
int result = gemstones(arr);
System.out.println(result);
in.close();
}
}

James found a love letter that his friend Harry has written to his girlfriend. James is a prankster, so he decides to meddle with the letter. He changes all the words in the letter into palindromes.

To do this, he follows two rules:

1. He can only reduce the value of a letter by 1, i.e. he can change d to c, but he cannot change c to d or d to b.
2. The letter a may not be reduced any further.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations required to convert a given string into a palindrome.

For example, given the string s = cde, the following two operations are performed: cde → cdd → cdc.

Function Description

Complete the theLoveLetterMystery function in the editor below. It should return the integer representing the minimum number of operations needed to make the string a palindrome.

theLoveLetterMystery has the following parameter(s):

• s: a string

Input Format

The first line contains an integer q, the number of queries.
The next q lines will each contain a string s.

Constraints

1 ≤ q ≤ 10

1 ≤ |s| ≤ 104
All strings are composed of lower case English letters, *ascii[a-z], with no spaces.

Output Format

A single line containing the minimum number of operations corresponding to each test case.

Sample Input

4
abc
abcba
abcd
cba


Sample Output

2
0
4
2

Solution:

public class TheLoveLetterMystery {
static int theLoveLetterMystery(String s) {
// Complete this function
int minOpCount = 0;
int strLen = s.length();
for (int i = 0; i < strLen / 2; i++) {
minOpCount += Math.abs(s.charAt(i) - s.charAt(strLen - i-1));
}
return minOpCount;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int q = in.nextInt();
for (int a0 = 0; a0 < q; a0++) {
String s = in.next();
int result = theLoveLetterMystery(s);
System.out.println(result);
}
in.close();
}
}

Dothraki are planning an attack to usurp King Robert’s throne. King Robert learns of this conspiracy from Raven and plans to lock the single door through which the enemy can enter his kingdom. But, to lock the door he needs a key that is an anagram of a palindrome. He starts to go through his box of strings, checking to see if they can be rearranged into a palindrome.

For example, given the string s = [aabbccdd], one way it can be arranged into a palindrome is abcddcba.

Function Description

Complete the gameOfThrones function below to determine whether a given string can be rearranged into a palindrome. If it is possible, return YES, otherwise return NO.

gameOfThrones has the following parameter(s):

• s: a string to analyze

Input Format

A single line which contains s, the input string.

Constraints

• ≤ |s| ≤ 105

• s contains only lowercase letters in the range ascii[a…z]

Output Format

A single line which contains YES or NO.

Sample Input 0

aaabbbb


Sample Output 0

YES

Solution:

public class GameOfThronesI {
static String gameOfThrones(String s) {
int a[] = new int;
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - 'a';
a[index]++;
}
int oddCount = 0;
for (int i = 0; i < 26; i++) {
if (a[i] != 0) {
if ((a[i] & 1) == 1) {
oddCount++;
}
}
}
return oddCount > 1 ? "NO" : "YES";

}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.next();
String result = gameOfThrones(s);
System.out.println(result);
in.close();
}
}

Sherlock considers a string to be valid if all characters of the string appear the same number of times. It is also valid if he can remove just 1 character at 1 index in the string, and the remaining characters will occur the same number of times. Given a string s, determine if it is valid. If so, return YES, otherwise return NO.

For example, if s = abc, it is a valid string because frequencies are {a :1,b : 1,c : 1}. So is s = abcc because we can remove one c and have 1 of each character in the remaining string. If s = abccc however, the string is not valid as we can only remove 1 occurrence of c. That would leave character frequencies of {a :1,b : 1,c : 2}

Function Description

Complete the isValid function in the editor below. It should return either the string YES or the string NO.

isValid has the following parameter(s):

• s: a string

Input Format

A single string s.

Constraints

• ≤ |s| ≤ 105

• Each character s[i] ∈ ascii[a-z]

Output Format

Print YES if string s is valid, otherwise, print NO.

Sample Input 0

aabbcd


Sample Output 0

NO

Solution:

public class SherlockAndTheValidString {
static String isValid(String s) {
int a[] = new int;
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - 'a';
a[index]++;
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < 26; i++) {
if (a[i] != 0) {
if (map.containsKey(a[i])) {
map.put(a[i], map.get(a[i]) + 1);
} else {
map.put(a[i], 1);
}
}
}
if (map.size() == 1)
return "YES";
if (map.size() == 2) {
Set<Entry<Integer, Integer>> entrySet = map.entrySet();
Iterator it = entrySet.iterator();
Entry<Integer, Integer> e1 = (Entry<Integer, Integer>) it.next();
int key1 = e1.getKey();
int value1 = e1.getValue();
Entry<Integer, Integer> e2 = (Entry<Integer, Integer>) it.next();
int key2 = e2.getKey();
int value2 = e2.getValue();
if (value1 == 1 || value2 == 1 && Math.abs(key1 - key2) == 1)
return "YES";
}
return "NO";
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.next();
String result = isValid(s);
System.out.println(result);
}
}

We define super digit of an integer x using the following rules:

Given an integer, we need to find the super digit of the integer.

• If x has only 1 digit, then its super digit is x.
• Otherwise, the super digit of x is equal to the super digit of the sum of the digits of x.

For example, the super digit of 9875 will be calculated as:

	super_digit(9875)   	9+8+7+5 = 29
super_digit(29) 	2 + 9 = 11
super_digit(11)		1 + 1 = 2
super_digit(2)		= 2


You are given two numbers n and k. The number p is created by concatenating the string n k times. Continuing the above example where n = 9875, assume your value k = 4. Your initial p = 987 (spaces added for clarity).

    superDigit(p) = superDigit(9875987598759875)
5+7+8+9+5+7+8+9+5+7+8+9+5+7+8+9 = 116
superDigit(p) = superDigit(116)
1+1+6 = 8
superDigit(p) = superDigit(8)


All of the digits of p sum to 116. The digits of 116 sum to 88 is only one digit, so it’s the super digit.

Function Description

Complete the function superDigit in the editor below. It must return the calculated super digit as an integer.

superDigit has the following parameter(s):

• n: a string representation of an integer
• k: an integer, the times to concatenate n to make p

Input Format

The first line contains two space separated integers, n and k.

Constraints

• ≤ n ≤ 10100000

• ≤ k ≤ 105

Output Format

Return the super digit of p, where p is created as described above.

Sample Input 0

148 3


Sample Output 0

3

Solution:

public class RecursiveDigitSum {

// method 1 -> recursive solution
static int digitSum(String n, int k) {
long superDigit = getSuperDigit(n);
long n1 = getSuperDigit(superDigit);
long k1 = getSuperDigit(k);

long result = n1 * k1;

while (result / 10 != 0) {
result = getSuperDigit(result);
}

return (int) result;
}

private static long getSuperDigit(String n) {
if (n == null || n.isEmpty())
return 0;
return (n.charAt(0) - '0') + getSuperDigit(n.substring(1));
}

private static long getSuperDigit(long n) {
if (n / 10 != 0)
return (n % 10) + getSuperDigit(n / 10);
return (n % 10);
}

// method 2 > Iterative solutions hint -->http://applet-magic.com/digitsummod9.htm
static int digitSumUsingMathTrick(String n, int k) {
BigInteger n1 = new BigInteger(n);
n1 = n1.multiply(new BigInteger(k + ""));
n1 = n1.remainder(new BigInteger("9"));
return n1.intValue() == 0 ? 9 : n1.intValue();

}

}

We define a modified Fibonacci sequence using the following definition:

Given terms tand ti+1 where i ∈ (1,∞) , term ti+2 is computed using the following relation: For example, if t1 = 0 and t2 = 1, Given three integers, t1t2, and n, compute and print the nth term of a modified Fibonacci sequence.

Function Description

Complete the fibonacciModified function in the editor below. It must return the nth  number in the sequence.

fibonacciModified has the following parameter(s):

• t1: an integer
• t2: an integer
• n: an integer

Note: The value of t may far exceed the range of a 64-bit integer. Many submission languages have libraries that can handle such large results but, for those that don’t (e.g., C++), you will need to compensate for the size of the result.

Input Format

A single line of three space-separated integers describing the respective values of t1t2, and n.

Constraints

• 0 ≤ t1,t2 ≤ 2
• 3 ≤ n ≤ 20
• t may far exceed the range of a 64-bit integer.

Output Format

Print a single integer denoting the value of term tn in the modified Fibonacci sequence where the first two terms are t1 and t2.

Sample Input

0 1 5


Sample Output

5

Solution:

public class FibonacciModified {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
BigDecimal t1 = new BigDecimal(sc.nextInt());
BigDecimal t2 = new BigDecimal(sc.nextInt());
int n = sc.nextInt();

BigDecimal sum = new BigDecimal(0);
for (int i = 3; i <= n; i++) {
sum = t1.add(t2.multiply(t2));
t1 = t2;
t2 = sum;
}
System.out.println(sum);
sc.close();
}
}

We define subsequence as any subset of an array. We define a subarray as a contiguous subsequence in an array.

Given an array, find the maximum possible sum among:

1. all nonempty subarrays.
2. all nonempty subsequences.

Print the two values as space-separated integers on one line.

Note that empty subarrays/subsequences should not be considered.

For example, given an array arr = [-1,2,3,-4,5,10], the maximum subarray sum is comprised of element inidices [1 – 5] and the sum is 2 + 3 + -4 + 5 + 10 = 16. The maximum subsequence sum is comprised of element indices [1,2,4,5] and the sum is 2 + 3 + 5 + 10 = 20.

Function Description

Complete the maxSubarray function in the editor below. It should return an array of two integers: the maximum subarray sum and the maximum subsequence sum of arr.

maxSubarray has the following parameter(s):

• arr: an array of integers

Input Format

The first line of input contains a single integer , the number of test cases.

The first line of each test case contains a single integer
The second line contains n space-separated integers arr[i] where 0 ≤ i ≤ n .

Constraints The subarray and subsequences you consider should have at least one element.

Output Format

Print two space-separated integers denoting the maximum sums of nonempty subarrays and nonempty subsequences, respectively.

Sample Input 0

2
4
1 2 3 4
6
2 -1 2 3 4 -5


Sample Output 0

10 10
10 11

Solution:

public class TheMaximumSubarray {

static int[] maxSubarray(int[] arr) {
int max_so_far = Integer.MIN_VALUE, max_end_here = 0, maxSum = 0;
int ans[] = new int;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 0)
maxSum += arr[i];
max_end_here += arr[i];
max_end_here = Math.max(max_end_here, arr[i]);
max_so_far = Math.max(max_so_far, max_end_here);
}
ans = max_so_far;
ans = max_so_far < 0 ? max_so_far : maxSum;
return ans;

}
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[] arr = new int[n];
for (int arr_i = 0; arr_i < n; arr_i++) {
arr[arr_i] = in.nextInt();
}
int[] result = maxSubarray(arr);
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + (i != result.length - 1 ? " " : ""));
}
System.out.println("");

}
in.close();
}
}

You will be given an array of integers. All of the integers except one occur twice. That one is unique in the array.

Given an array of integers, find and print the unique element.

For example, a = [1,2,3,4,3,2,1], the unique element is 4.

Function Description

Complete the lonelyinteger function in the editor below. It should return the integer which occurs only once in the input array.

lonelyinteger has the following parameter(s):

• a: an array of integers

Input Format

The first line contains a single integer, n, denoting the number of integers in the array.
The second line contains n space-separated integers describing the values in a.

Constraints

• 1 ≤ n ≤ 100
• It is guaranteed that n is an odd number and that there is one unique element.
• 0 ≤ a[i] ≤ 100, where 0 ≤ i ≤ n .

Output Format

Print the unique integer in the array.

Sample Input 0

1
1


Sample Output 0

1

Solution:

public class LonelyInteger {
static int lonelyinteger(int[] a) {
int result = 0;
for (int i = 0; i < a.length; i++) {
result ^= a[i];

}

return result;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int res;

int _a_size = Integer.parseInt(in.nextLine());
int[] _a = new int[_a_size];
int _a_item;
String next = in.nextLine();
String[] next_split = next.split(" ");

for (int _a_i = 0; _a_i < _a_size; _a_i++) {
_a_item = Integer.parseInt(next_split[_a_i]);
_a[_a_i] = _a_item;
}

res = lonelyinteger(_a);
System.out.println(res);
in.close();
}
}

Consider an array of integers where all but one of the integers occur in pairs. In other words, every element occurs exactly twice except for one unique element. Find the unique element.

For example, given the array arr = [1,1,2,3,2], you would return 3.

Function Description

Complete the findLonely function in the editor below. It should return the unique integer in arr.

findLonely has the following parameter(s):

• arr: an array of integers

Input Format

The first line contains a single integer, n, denoting the number of integers in arr
The second line contains n space-separated integers, each an element, arr[i].

Constraints

• 1 ≤ n ≤ 100
• It is guaranteed that n is an odd number.
• 0 ≤ a[i] ≤ 100, where 0 ≤ i ≤ n .

Output Format

Print the unique number in arr on a new line.

Sample Input 0

1
1


Sample Output 0

1

Solution:

public class BitManipulationLonelyInteger {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int res = 0;
for (int i = 0; i < n; i++) {
res ^= sc.nextInt();
}
System.out.println(res);
sc.close();
}
}

Given an integer n, find each x such that: where  denotes the bitwise XOR operator. Print the number of x‘s satisfying the criteria.

For example, if n = 4, there are four values: Function Description

Complete the sumXor function in the editor below. It should return the number of values determined, as an integer.

sumXor has the following parameter(s):
– n: an integer

Input Format

A single integer, n.

Constraints

• 0 ≤ n ≤ 1015

Subtasks

• 0 ≤ n ≤ 100 for 60% of the maximum score.

Output Format

Print the total number of integers x satisfying the criteria.

Sample Input 0

5


Sample Output 0

2

Solution:

public class SumvsXOR {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
System.out.println((long) Math.pow(2, getNumberOfOnes(n)));
sc.close();
}

private static long getNumberOfOnes(long n) {
long result = 0;
while (n != 0) {
if ((n & 1) == 0) {
result += 1;
}
n >>>= 1;
}
return result;
}
}

Given two integers, l and r, find the maximal value of a xor b, where a and b satisfy the following condition:

l ≤ a ≤ b ≤ r

For example, if l = 11 and r =12, then Our maximum value is 7.

Function Description

Complete the maximizingXor function in the editor below. It must return an integer representing the maximum value calculated.

maximizingXor has the following parameter(s):

• l: an integer, the lower bound, inclusive
• r: an integer, the upper bound, inclusive

Input Format

The first line contains the integer l
The second line contains the integer r.

Constraints

1 ≤ l ≤ r ≤ 103

Output Format

Return the maximal value of the xor operations for all permutations of the integers from  to , inclusive.

Sample Input 0

10
15


Sample Output 0

7

Solution:

public class MaximizingXOR {
/*
* Complete the function below.
*/

static int maxXor(int l, int r) {
int maxXor = 0;
for (int i = l; i < r; i++) {
int temp;
temp = i ^ (i + 1);
if (temp > maxXor) {
maxXor = temp;
}
}

return maxXor;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int res;
int _l;
_l = Integer.parseInt(in.nextLine());

int _r;
_r = Integer.parseInt(in.nextLine());

res = maxXor(_l, _r);
System.out.println(res);
in.close();
}
}

Sansa has an array. She wants to find the value obtained by XOR-ing the contiguous subarrays, followed by XOR-ing the values thus obtained. Determine this value.

For example, if arr = [3,4,5]:

Subarray	Operation	Result
3		None		3
4		None		4
5		None		5
3,4		3 XOR 4		7
4,5		4 XOR 5		1
3,4,5		3 XOR 4 XOR 5	2


Now we take the resultant values and XOR them together: Function Description

Complete the sansaXor function in the editor below. It should return an integer that represents the results of the calculations.

sansaXor has the following parameter(s):

• arr: an array of integers

Input Format

The first line contains an integer t, the number of the test cases.

Each of the next t pairs of lines is as follows:
– The first line of each test case contains an integer n, the number of elements in arr
– The second line of each test case contains n space-separated integers arr[i].

Constraints Output Format

Print the results of each test case on a separate line.

Sample Input 0

2
3
1 2 3
4
4 5 7 5


Sample Output 0

2
0

Solution:

public class SansaAndXOR {
static int sansaXor(int[] arr) {
int res = 0;
int len = arr.length;
if ((len ^ 1) == 0)
return 0;
for (int i = 0; i < arr.length; i++) {
if ((i & 1) == 1)
res ^= arr[i];
}
return res;
}

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[] arr = new int[n];
for (int arr_i = 0; arr_i < n; arr_i++) {
arr[arr_i] = in.nextInt();
}
int result = sansaXor(arr);
System.out.println(result);
}
in.close();
}
}

## Alogrithm

1. What Is Algorithm? Algorithm is a step by step procedure, which defines a set of instructions to be executed in certain order to get…

## data-structure-frequently asked-questions

1.What is a Data Structure? Data structure is representation of the logical relationship existing between individual elements of data. In other words, a data structure…

## Hackerearth-Algorithm

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

## 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…