Hacker Rank Solutions for Gem-Stones
Hacker Rank Solutions for Gem-Stones
John has discovered various rocks. Each rock is composed of various elements, and each element is represented by a lowercase latin letter from 'a' to 'z'. An element can be present multiple times in a rock. An element is called a 'gem-element' if it occurs at least once in each of the rocks.
Given the list of rocks with their compositions, display the number of gem-elements that exist in those rocks.
Input Format
The first line consists of N, the number of rocks.
Each of the next N lines contain rocks' composition. Each composition consists of lowercase letters of English alphabet.
Output Format
Print the number of gem-elements that are common in these rocks.
Constraints
1 ≤ N ≤ 100
Each composition consists of only small latin letters ('a'-'z').
1 ≤ Length of each composition ≤ 100
Sample Input
3
abcdde
baccd
eeabg
Sample Output
2
Explanation
Only "a", "b" are the two kind of gem-elements, since these are the only characters that occur in each of the rocks' composition.
John has discovered various rocks. Each rock is composed of various elements, and each element is represented by a lowercase latin letter from 'a' to 'z'. An element can be present multiple times in a rock. An element is called a 'gem-element' if it occurs at least once in each of the rocks.
Given the list of rocks with their compositions, display the number of gem-elements that exist in those rocks.
Input Format
The first line consists of N, the number of rocks.
Each of the next N lines contain rocks' composition. Each composition consists of lowercase letters of English alphabet.
Output Format
Print the number of gem-elements that are common in these rocks.
Constraints
1 ≤ N ≤ 100
Each composition consists of only small latin letters ('a'-'z').
1 ≤ Length of each composition ≤ 100
Sample Input
3
abcdde
baccd
eeabg
Sample Output
2
Explanation
Only "a", "b" are the two kind of gem-elements, since these are the only characters that occur in each of the rocks' composition.
Solutions
#include<stdio.h>
#include<string.h>
main(){
int n,i,j, ans=0;
int count[26]={0};
char s[100][100];
char *p;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%s",s[i]);
}
j=1;
int t, index;
int l = strlen(s[0]);
for(i=0;i<l;i++){
t=0;
for(j=1;j<n;j++){
if(strchr(s[j],s[0][i])!='\0'){
t++;
}
}
if(t==n-1){
index= s[0][i] - 'a';
count[index]=1;
}
}
for(i=0;i<26;i++){
if (count[i]==1)
ans++;
}
printf("%d",ans);
}
HACKER RANK SOLUTON FOR GAME OF ROTATION
HACKER RANK SOLUTON FOR GAME OF ROTATION
Mark is an undergraduate student and he is interested in rotation. A conveyor belt competition is going on in the town which Mark wants to win. In the competition, there's A conveyor belt which can be represented as a strip of 1xN blocks. Each block has a number written on it. The belt keeps rotating in such a way that after each rotation, each block is shifted to left of it and the first block goes to last position.
There is a switch near the conveyer belt which can stop the belt. Each participant would be given a single chance to stop the belt and his PMEAN would be calculated.
PMEAN is calculated using the sequence which is there on the belt when it stops. The participant having highest PMEAN is the winner. There can be multiple winners.
Mark wants to be among the winners. What PMEAN he should try to get which guarantees him to be the winner.
PMEAN=∑i=1ni×a[i]
where a represents the configuration of conveyor belt when it is stopped. Indexing starts from 1.
Input Format
First line contains N denoting the number of elements on the belt.
Second line contains N space separated integers.
Output Format
Output the required PMEAN
Constraints
1 ≤ N ≤ 106
-109 ≤ each number ≤ 109
For any rotation, PMEAN will always lie within the range of 64-bit signed integer.
Sample Input
3
20 30 10
Sample Output
140
Explanation
Number on top can be written in these manners.
Initial numbers on belt, 20 30 10 PMEAN = 1x20 + 2x30 + 3x10 = 110
After first rotation, 30 10 20 PMEAN = 1x30 + 2x10 + 3x20 = 110
After second rotation, 10 20 30 PMEAN = 1x10 + 2x20 + 3x30 = 140
So maximum possible value will be 140.
Solution
#include <stdio.h>
int main() {
int n,i,k;
scanf("%d",&n);
long long int a[n],sum[n], ans, s=0,temp;
sum[0] =0;
for(i=0;i<n;i++){
scanf("%lld",&a[i]);
sum[0]+=(i+1)*a[i];
s+= a[i];
}
ans = sum[0];
for(k=1;k<n;k++){
temp = n*a[k-1];
sum[k]= sum[k-1] - s + temp;
if(ans<sum[k])
ans = sum[k];
}
printf("%lld",ans);
return 0;
}
Mark is an undergraduate student and he is interested in rotation. A conveyor belt competition is going on in the town which Mark wants to win. In the competition, there's A conveyor belt which can be represented as a strip of 1xN blocks. Each block has a number written on it. The belt keeps rotating in such a way that after each rotation, each block is shifted to left of it and the first block goes to last position.
There is a switch near the conveyer belt which can stop the belt. Each participant would be given a single chance to stop the belt and his PMEAN would be calculated.
PMEAN is calculated using the sequence which is there on the belt when it stops. The participant having highest PMEAN is the winner. There can be multiple winners.
Mark wants to be among the winners. What PMEAN he should try to get which guarantees him to be the winner.
PMEAN=∑i=1ni×a[i]
where a represents the configuration of conveyor belt when it is stopped. Indexing starts from 1.
Input Format
First line contains N denoting the number of elements on the belt.
Second line contains N space separated integers.
Output Format
Output the required PMEAN
Constraints
1 ≤ N ≤ 106
-109 ≤ each number ≤ 109
For any rotation, PMEAN will always lie within the range of 64-bit signed integer.
Sample Input
3
20 30 10
Sample Output
140
Explanation
Number on top can be written in these manners.
Initial numbers on belt, 20 30 10 PMEAN = 1x20 + 2x30 + 3x10 = 110
After first rotation, 30 10 20 PMEAN = 1x30 + 2x10 + 3x20 = 110
After second rotation, 10 20 30 PMEAN = 1x10 + 2x20 + 3x30 = 140
So maximum possible value will be 140.
Solution
#include <stdio.h>
int main() {
int n,i,k;
scanf("%d",&n);
long long int a[n],sum[n], ans, s=0,temp;
sum[0] =0;
for(i=0;i<n;i++){
scanf("%lld",&a[i]);
sum[0]+=(i+1)*a[i];
s+= a[i];
}
ans = sum[0];
for(k=1;k<n;k++){
temp = n*a[k-1];
sum[k]= sum[k-1] - s + temp;
if(ans<sum[k])
ans = sum[k];
}
printf("%lld",ans);
return 0;
}
HACKER RANK SOLUTION FOR Counting-Sort-2
HACKER RANK SOLUTION FOR COUNTNG SORT-2
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.
However, if you are not concerned about any other information, then you can simply sort those numbers alone. This makes counting sort very simple. If you already counted the values in the list, you don't need to access the original list again. This challenge involves a simple counting sort where the elements being sorted are all that matter.
Challenge
Given an unsorted list of integers, output the integers in order.
Hint: You can use your previous code that counted the items to print out the actual values in-order.
Input Format
There will be two lines of input:
n - the size of the list
ar - n space separated numbers that belong to the list
Output Format
Output all the numbers of the list in-order.
Constraints
1 <= n <= 1000000
0 <= x < 100 , x ∈ ar
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
Explanation
In the output you can see the numbers sorted in ascending order. You can also see that numbers appearing multiple times are printed accordingly.
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.
However, if you are not concerned about any other information, then you can simply sort those numbers alone. This makes counting sort very simple. If you already counted the values in the list, you don't need to access the original list again. This challenge involves a simple counting sort where the elements being sorted are all that matter.
Challenge
Given an unsorted list of integers, output the integers in order.
Hint: You can use your previous code that counted the items to print out the actual values in-order.
Input Format
There will be two lines of input:
n - the size of the list
ar - n space separated numbers that belong to the list
Output Format
Output all the numbers of the list in-order.
Constraints
1 <= n <= 1000000
0 <= x < 100 , x ∈ ar
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
Explanation
In the output you can see the numbers sorted in ascending order. You can also see that numbers appearing multiple times are printed accordingly.
Solution
#include<stdio.h>
main()
{
int n,i,j;
scanf("%d",&n);
int ar[n];
int count[100] = {0}; //for 0 to 100
for(i=0;i<n;i++)
{
scanf("%d",&ar[i]);
count[ar[i]]++;
}
for(i=0;i<100;i++)
{
if(count[i]>0)
{
for(j=0;j<count[i];j++)
{
printf("%d ",i);
}
}
}
}
Hacker Rank Solution for Counting-Sort1
Hacker Rank Solution for Counting-Sort1
Comparison Sorting
Quicksort usually has a running time of n*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 with one another. A comparison sort algorithm cannot beat n log(n) (worst-case) running time, since n 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
However, for certain types of input, it is more efficient to use a non-comparison sorting algorithm. This will make it possible to sort lists even in linear time. These challenges will cover Counting Sort, a fast way to sort lists where the elements have a small number of possible values, such as integers within a certain range. We will start with an easy task - counting.
Challenge
Given a list of integers, can you count and output the number of times each value appears?
Hint: There is no need to sort the data, you just need to count it.
Input Format
There will be two lines of input:
n - the size of the list
ar - n space separated numbers that makes up the list
Output Format
Output the number of times every number from 0 to 99 (inclusive) appears in the list.
Constraints
100 <= n <= 106
0 <= x < 100 , x ∈ ar
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
Explanation
the output states that 0 appears 0 times.
1 appears 2 times.
2 appears 0 times.
and so on in the given input array.
Solution
#include<stdio.h>
main()
{
int n,i;
scanf("%d",&n);
int ar[n];
int count[100] = {0}; //for 0 to 100
for(i=0;i<n;i++)
{
scanf("%d",&ar[i]);
count[ar[i]]++;
}
for(i=0;i<100;i++)
{
printf("%d ",count[i]);
}
}
Comparison Sorting
Quicksort usually has a running time of n*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 with one another. A comparison sort algorithm cannot beat n log(n) (worst-case) running time, since n 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
However, for certain types of input, it is more efficient to use a non-comparison sorting algorithm. This will make it possible to sort lists even in linear time. These challenges will cover Counting Sort, a fast way to sort lists where the elements have a small number of possible values, such as integers within a certain range. We will start with an easy task - counting.
Challenge
Given a list of integers, can you count and output the number of times each value appears?
Hint: There is no need to sort the data, you just need to count it.
Input Format
There will be two lines of input:
n - the size of the list
ar - n space separated numbers that makes up the list
Output Format
Output the number of times every number from 0 to 99 (inclusive) appears in the list.
Constraints
100 <= n <= 106
0 <= x < 100 , x ∈ ar
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
Explanation
the output states that 0 appears 0 times.
1 appears 2 times.
2 appears 0 times.
and so on in the given input array.
Solution
#include<stdio.h>
main()
{
int n,i;
scanf("%d",&n);
int ar[n];
int count[100] = {0}; //for 0 to 100
for(i=0;i<n;i++)
{
scanf("%d",&ar[i]);
count[ar[i]]++;
}
for(i=0;i<100;i++)
{
printf("%d ",count[i]);
}
}
Hacker Rank soluton for Correctness-and-the-Loop-Invariant
Hacker Rank soluton for Correctness-and-the-Loop-Invariant
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 3 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 >= to the element to the left of it. Since the elements to the left have already been sorted, it means V >= all the elements to the left, so the array remains sorted. (In InsertionSort2, we saw this by printing array each time an element was 'inserted' into it.)
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. So the array is now fully sorted.
Loop Invariant Chart
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.
Details
The Input format and the constraints are the same as the previous challenges and are presented below.
Input Format
There will be two lines of input:
s - the size of the array
ar - the list of numbers that makes up the array
Output Format
Output the numbers in order, space-separated.
Constraints
1<=s<=1000
-1500<=x<= 1500 , x ∈ ar
Sample Input
6
1 4 3 5 6 2
Sample Output
1 2 3 4 5 6
Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <stddef.h>
void insertionSort(int ar_size, int * ar) {
int i,j;
int value;
for(i=1;i<ar_size;i++)
{
value=ar[i];
j=i-1;
while(j>=0 && value<ar[j])
{
ar[j+1]=ar[j];
j=j-1;
}
ar[j+1]=value;
}
for(j=0;j<ar_size;j++)
{
printf("%d",ar[j]);
printf(" ");
}
}
int main(void) {
int _ar_size;
scanf("%d", &_ar_size);
int _ar[_ar_size], _ar_i;
for(_ar_i = 0; _ar_i < _ar_size; _ar_i++) {
scanf("%d", &_ar[_ar_i]);
}
insertionSort(_ar_size, _ar);
return 0;
}
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 3 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 >= to the element to the left of it. Since the elements to the left have already been sorted, it means V >= all the elements to the left, so the array remains sorted. (In InsertionSort2, we saw this by printing array each time an element was 'inserted' into it.)
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. So the array is now fully sorted.
Loop Invariant Chart
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.
Details
The Input format and the constraints are the same as the previous challenges and are presented below.
Input Format
There will be two lines of input:
s - the size of the array
ar - the list of numbers that makes up the array
Output Format
Output the numbers in order, space-separated.
Constraints
1<=s<=1000
-1500<=x<= 1500 , x ∈ ar
Sample Input
6
1 4 3 5 6 2
Sample Output
1 2 3 4 5 6
Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <stddef.h>
void insertionSort(int ar_size, int * ar) {
int i,j;
int value;
for(i=1;i<ar_size;i++)
{
value=ar[i];
j=i-1;
while(j>=0 && value<ar[j])
{
ar[j+1]=ar[j];
j=j-1;
}
ar[j+1]=value;
}
for(j=0;j<ar_size;j++)
{
printf("%d",ar[j]);
printf(" ");
}
}
int main(void) {
int _ar_size;
scanf("%d", &_ar_size);
int _ar[_ar_size], _ar_i;
for(_ar_i = 0; _ar_i < _ar_size; _ar_i++) {
scanf("%d", &_ar[_ar_i]);
}
insertionSort(_ar_size, _ar);
return 0;
}
HAcker Rank Solutiom for Closest-Numbers
HAcker Rank Solutiom for Closest-Numbers
Problem Statement
Sorting is often useful as the first step in many different tasks. The most common task is to make finding things easier, but there are other uses also.
Challenge
Given a list of unsorted numbers, can you find the numbers that have the smallest absolute difference between them? If there are multiple pairs, find them all.
Input Format
There will be two lines of input:
n - the size of the list
array - the n numbers of the list
Output Format
Output the pairs of numbers with the smallest difference. If there are multiple pairs, output all of them in ascending order, all on the same line (consecutively) with just a single space between each pair of numbers. If there's a number which lies in two pair, print it two times (see sample case #3 for explanation).
Constraints
2 <= n <= 200000
-(107) <= x <= (107), where x ∈ array
array[i] != array[j], 0 <= i, j < N, and i != j
Sample Input
#1
10
-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854
Sample Output
#1
-20 30
Explanation
(30) - (-20) = 50, which is the smallest difference.
Sample Input #2
12
-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854 -520 -470
Sample Output #2
-520 -470 -20 30
Explanation
(-470) - (-520) = 30 - (-20) = 50, which is the smallest difference.
Sample Input #3
4
5 4 3 2
Sample Output #3
2 3 3 4 4 5
Explanation
Here, the minimum difference will be 1. So valid pairs are (2, 3), (3, 4), (4, 5). So we have to print 2 one time, 3 and 4 two times, and 5 one time.
Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[n];
for(int i=0; i<n; i++){
a[i] = in.nextInt();
}
int min=0, temp=0;
HashMap<Integer, ArrayList<Integer>> minMap = new HashMap<Integer,ArrayList<Integer>>();
Arrays.sort(a);
for(int i=0; i<n-1; i++){
temp = a[i+1] - a[i];
if(!minMap.containsKey(temp))
minMap.put(temp, new ArrayList<Integer>());
minMap.get(temp).add(a[i]);
minMap.get(temp).add(a[i+1]);
if(min>temp || i==0)
min = temp;
}
for(int i=0; i<minMap.get(min).size();i++)
System.out.print(minMap.get(min).get(i)+" ");
}
}
Problem Statement
Sorting is often useful as the first step in many different tasks. The most common task is to make finding things easier, but there are other uses also.
Challenge
Given a list of unsorted numbers, can you find the numbers that have the smallest absolute difference between them? If there are multiple pairs, find them all.
Input Format
There will be two lines of input:
n - the size of the list
array - the n numbers of the list
Output Format
Output the pairs of numbers with the smallest difference. If there are multiple pairs, output all of them in ascending order, all on the same line (consecutively) with just a single space between each pair of numbers. If there's a number which lies in two pair, print it two times (see sample case #3 for explanation).
Constraints
2 <= n <= 200000
-(107) <= x <= (107), where x ∈ array
array[i] != array[j], 0 <= i, j < N, and i != j
Sample Input
#1
10
-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854
Sample Output
#1
-20 30
Explanation
(30) - (-20) = 50, which is the smallest difference.
Sample Input #2
12
-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854 -520 -470
Sample Output #2
-520 -470 -20 30
Explanation
(-470) - (-520) = 30 - (-20) = 50, which is the smallest difference.
Sample Input #3
4
5 4 3 2
Sample Output #3
2 3 3 4 4 5
Explanation
Here, the minimum difference will be 1. So valid pairs are (2, 3), (3, 4), (4, 5). So we have to print 2 one time, 3 and 4 two times, and 5 one time.
Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[n];
for(int i=0; i<n; i++){
a[i] = in.nextInt();
}
int min=0, temp=0;
HashMap<Integer, ArrayList<Integer>> minMap = new HashMap<Integer,ArrayList<Integer>>();
Arrays.sort(a);
for(int i=0; i<n-1; i++){
temp = a[i+1] - a[i];
if(!minMap.containsKey(temp))
minMap.put(temp, new ArrayList<Integer>());
minMap.get(temp).add(a[i]);
minMap.get(temp).add(a[i+1]);
if(min>temp || i==0)
min = temp;
}
for(int i=0; i<minMap.get(min).size();i++)
System.out.print(minMap.get(min).get(i)+" ");
}
}
Hacker rank solution for Bus-Station
Hacker rank solution for Bus-Station
There are n groups of friends, and each group is numbered from 1 to n. The ith group contains ai people.
They live near a bus stop, and only a single bus operates on this route. An empty bus arrives at the bus stop and all the groups want to travel by the bus.
However, group of friends do not want to get separated. So they enter the bus only if the bus can carry the entire group.
Moreover, the groups do not want to change their relative positioning while travelling. In other words, group 3 cannot travel by bus, unless group 1 and group 2 have either (a) already traveled by the bus in the previous trip or (b) they are also sitting inside the bus at present.
You are given that a bus of size x can carry x people simultaneously.
Find the size x of the bus so that (1) the bus can transport all the groups and (2) every time when the bus starts from the bus station, there is no empty space in the bus (i.e. the total number of people present inside the bus is equal to x)?
Input Format
The first line contains an integer n (1≤n≤105). The second line contains n space-separated integers a1,a2,…,an (1≤ai≤104).
Output Format
Print all possible sizes of the bus in an increasing order.
Sample Input
8
1 2 1 1 1 2 1 3
Sample Output
3 4 6 12
Sample Explanation
In the above example, a1 = 1, a2 = 2, a3 = 1, a4 = 1, a5 = 1, a6 = 2, a7 = 1, a8 = 3.
If x = 1 : In the first trip, a1 go by the bus. There will be no second trip because the bus cannot accommodate group 2. Hence "x = 1" is not the required answer.
If x = 2 : No bus trip is possible. That's because a1 cannot go alone, as one seat will be left vacant in the bus. And, a1 & a2 cannot go together, because the bus is cannot accommodate both the groups simultaneously.
If x = 3 : In the first trip, a1 & a2 go by the bus. In the second trip, a3, a4 & a5 go by the bus. In the third trip, a6 & a7 go by the bus. In the fourth trip, a8 go by the bus.
If x = 4 : In the first trip, a1, a2 & a3 go by the bus. In the second trip, a4, a5 & a6go by the bus. In the third trip, a7 & a8 go by the bus.
Similarly you can figure out the output for x= 5, 6 & 7.
SOLUTION
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void quicksort(int * A, int p, int r){
if(p<r){
int q = partition(A,p,r);
quicksort(A,p,q-1);
quicksort(A,q+1,r);
}
}
int partition(int *A, int p, int r){
int x,i,j,temp;
x = A[r];
i = p-1;
for(j=p;j<r;j++){
if(A[j]<=x){
i++;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
temp = A[i+1];
A[i+1] = A[r];
A[r] = temp;
return i+1;
}
int main() {
int n,i,g, l=1,sum = 0;
scanf("%d",&n);
int a[n];
for(i=0;i<n;i++){
scanf("%d",&a[i]);
sum+= a[i];
if(g>a[i] || i==0)
g = a[i];
}
int k=0,m,d[n];
m = sqrt(sum);
while(l<= m){
if(sum % l == 0){
if(l>=g){
d[k] = l;
k++;
}
if(l != sum/l && (sum/l)>=g){
d[k] = sum/l;
k++;
}
}
l++;
}
int e[k];
l = 0;
int t = 0;
while(l<k){
m = d[l];
i = 0;
while(m>0){
m-= a[i];
i++;
if(m==0 && i<n)
m = d[l];
}
if(m==0 && i==n){
e[t] = d[l];
t++;
}
l++;
}
quicksort(e,0,t-1);
for(i=0;i<t;i++)
printf("%d ",e[i]);
return 0;
}
There are n groups of friends, and each group is numbered from 1 to n. The ith group contains ai people.
They live near a bus stop, and only a single bus operates on this route. An empty bus arrives at the bus stop and all the groups want to travel by the bus.
However, group of friends do not want to get separated. So they enter the bus only if the bus can carry the entire group.
Moreover, the groups do not want to change their relative positioning while travelling. In other words, group 3 cannot travel by bus, unless group 1 and group 2 have either (a) already traveled by the bus in the previous trip or (b) they are also sitting inside the bus at present.
You are given that a bus of size x can carry x people simultaneously.
Find the size x of the bus so that (1) the bus can transport all the groups and (2) every time when the bus starts from the bus station, there is no empty space in the bus (i.e. the total number of people present inside the bus is equal to x)?
Input Format
The first line contains an integer n (1≤n≤105). The second line contains n space-separated integers a1,a2,…,an (1≤ai≤104).
Output Format
Print all possible sizes of the bus in an increasing order.
Sample Input
8
1 2 1 1 1 2 1 3
Sample Output
3 4 6 12
Sample Explanation
In the above example, a1 = 1, a2 = 2, a3 = 1, a4 = 1, a5 = 1, a6 = 2, a7 = 1, a8 = 3.
If x = 1 : In the first trip, a1 go by the bus. There will be no second trip because the bus cannot accommodate group 2. Hence "x = 1" is not the required answer.
If x = 2 : No bus trip is possible. That's because a1 cannot go alone, as one seat will be left vacant in the bus. And, a1 & a2 cannot go together, because the bus is cannot accommodate both the groups simultaneously.
If x = 3 : In the first trip, a1 & a2 go by the bus. In the second trip, a3, a4 & a5 go by the bus. In the third trip, a6 & a7 go by the bus. In the fourth trip, a8 go by the bus.
If x = 4 : In the first trip, a1, a2 & a3 go by the bus. In the second trip, a4, a5 & a6go by the bus. In the third trip, a7 & a8 go by the bus.
Similarly you can figure out the output for x= 5, 6 & 7.
SOLUTION
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void quicksort(int * A, int p, int r){
if(p<r){
int q = partition(A,p,r);
quicksort(A,p,q-1);
quicksort(A,q+1,r);
}
}
int partition(int *A, int p, int r){
int x,i,j,temp;
x = A[r];
i = p-1;
for(j=p;j<r;j++){
if(A[j]<=x){
i++;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
temp = A[i+1];
A[i+1] = A[r];
A[r] = temp;
return i+1;
}
int main() {
int n,i,g, l=1,sum = 0;
scanf("%d",&n);
int a[n];
for(i=0;i<n;i++){
scanf("%d",&a[i]);
sum+= a[i];
if(g>a[i] || i==0)
g = a[i];
}
int k=0,m,d[n];
m = sqrt(sum);
while(l<= m){
if(sum % l == 0){
if(l>=g){
d[k] = l;
k++;
}
if(l != sum/l && (sum/l)>=g){
d[k] = sum/l;
k++;
}
}
l++;
}
int e[k];
l = 0;
int t = 0;
while(l<k){
m = d[l];
i = 0;
while(m>0){
m-= a[i];
i++;
if(m==0 && i<n)
m = d[l];
}
if(m==0 && i==n){
e[t] = d[l];
t++;
}
l++;
}
quicksort(e,0,t-1);
for(i=0;i<t;i++)
printf("%d ",e[i]);
return 0;
}
Hacker rank solution for Bigger-is-Greater
Hacker rank solution for Bigger-is-Greater
Please note that this is a team event, and your submission will be accepted only as a part of a team, even single member teams are allowed. Please click here to register as a team, if you have NOT already registered.
Given a word w, rearrange the letters of w to construct another word s in such a way that, s is lexicographically greater than w. In case of multiple possible answers, find the lexicographically smallest one.
Input Format
The first line of input contains t, number of test cases. Each of the next t lines contains w.
Constraints
1≤t≤105
1≤|w|≤100
w will contain only lower case english letters and its' length will not exceed 100.
Output Format
For each testcase, output a string lexicographically bigger than w in a separate line. In case of multiple possible answers, print the lexicographically smallest one and if no answer exists, print no answer.
Sample Input
3
ab
bb
hefg
Sample Output
ba
no answer
hegf
Explanation
Testcase 1 : There exists only one string greater than ab which can be built by rearranging ab. That is ba.
Testcase 2 : Not possible to re arrange bb and get a lexicographically greater string.
Testcase 3 : hegf is the next string ( lexicographically greater ) to hefg.
SOLUTION
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void solve (char str[])
{
int i, flag=0;
loop:
for(i=str.length-1; i>0; i--)
{
if(str[i]>str[i-1])
{
int j = str.length-1;
while(flag==0 && j!=i-1){
if(str[i-1]<str[j])
{
char t = str[j];
str[j] = str[i-1];
str[i-1] = t;
flag = 1;
break loop;
}
j--;
}
}
}
Arrays.sort(str,i,str.length);
if(flag==0)
System.out.println("no answer");
else
System.out.println(str);
}
public static void main(String[] args) {
char name[];
int t;
Scanner in = new Scanner(System.in);
t = in.nextInt();
for(int i=0; i<t; i++)
{
name = in.next().toCharArray();
solve(name);
}
}
}
Please note that this is a team event, and your submission will be accepted only as a part of a team, even single member teams are allowed. Please click here to register as a team, if you have NOT already registered.
Given a word w, rearrange the letters of w to construct another word s in such a way that, s is lexicographically greater than w. In case of multiple possible answers, find the lexicographically smallest one.
Input Format
The first line of input contains t, number of test cases. Each of the next t lines contains w.
Constraints
1≤t≤105
1≤|w|≤100
w will contain only lower case english letters and its' length will not exceed 100.
Output Format
For each testcase, output a string lexicographically bigger than w in a separate line. In case of multiple possible answers, print the lexicographically smallest one and if no answer exists, print no answer.
Sample Input
3
ab
bb
hefg
Sample Output
ba
no answer
hegf
Explanation
Testcase 1 : There exists only one string greater than ab which can be built by rearranging ab. That is ba.
Testcase 2 : Not possible to re arrange bb and get a lexicographically greater string.
Testcase 3 : hegf is the next string ( lexicographically greater ) to hefg.
SOLUTION
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void solve (char str[])
{
int i, flag=0;
loop:
for(i=str.length-1; i>0; i--)
{
if(str[i]>str[i-1])
{
int j = str.length-1;
while(flag==0 && j!=i-1){
if(str[i-1]<str[j])
{
char t = str[j];
str[j] = str[i-1];
str[i-1] = t;
flag = 1;
break loop;
}
j--;
}
}
}
Arrays.sort(str,i,str.length);
if(flag==0)
System.out.println("no answer");
else
System.out.println(str);
}
public static void main(String[] args) {
char name[];
int t;
Scanner in = new Scanner(System.in);
t = in.nextInt();
for(int i=0; i<t; i++)
{
name = in.next().toCharArray();
solve(name);
}
}
}
Subscribe to:
Posts (Atom)