You are given an array of integers
@N.Write a script to display the maximum difference between two successive elements once the array is sorted.
If the array contains only 1 element then display
0.
Input: @N = (2, 9, 3, 5)
Output: 4
Input: @N = (1, 3, 8, 2, 0)
Output: 5
Input: @N = (5)
Output: 0
The solution is pretty straight forward. After reading in the numbers, we have to sort the list of number. Then we iterate over the numbers, calculate the difference between the number and the previous number, and keeping track of the maximum.
We will be reading input from standard input, where each line contains a set of numbers, separated by white space. Each line is seen as a different challenge.
We are iterating line by line over the input (<>), and splitting
each line on whitespace (split). The resulting list is numerically
sorted, and stored in an array (@N).
We're then finding all the differences between a number and
the preceeding number using map, starting from the second
number in the array. We use the max function from the
module List::Util to get the maximum. If the input has just
one number, the list of differences is empty; it that case,
max returns undef. Hence the // 0, which means that
in that case, we print 0.
use List::Util qw [max];
while (<>) {
my @N = sort {$a <=> $b} split;
say max (map {$N [$_] - $N [$_ - 1]} 1 .. $#N) // 0;
}
Find the full program on GitHub.
For our AWK solution, we turn to GNU AWK, the GNU implemenation of AWK.
This implementation has the method asort, which
takes an array, and sorts it.
In AWK, the input is by default already split on whitespace, and
available in the variables $1, $2, $3, .... The variable
NF contains the number of fields the input
has been split into. We can then iterate over the fields, and
populate an array N.
Finding the maximum of the differences is done by iterating over the array.
{
#
# We don't have lexical variables, so we need to clear
# the array N in each iteration.
#
delete N
#
# Read in the data, and populate N
#
for (i = 1; i <= NF; i ++) {
N [i] = $i
}
#
# Sort the array; for numeric values, this sorts numerically.
#
asort(N)
#
# Find the maximum of the differences. For a single element
# array, the maximum will be 0.
#
max = 0
for (i = 2; i <= NF; i ++) {
if (N [i] - N [i - 1] > max) {
max = N [i] - N [i - 1]
}
}
#
# Print the result.
#
print max
}
Find the full program on GitHub.
Bash does not have a sort function, so first point of business is the write one. We will write an implementation of a selection sort:
function ssort() {
for ((i = 0; i < ${#N[*]}; i ++))
do for ((j = i + 1; j < ${#N[*]}; j ++))
do if ((N[j] < N[i]))
then t=${N[$i]}
N[$i]=${N[$j]]}
N[$j]=$t
fi
done
done
}
Note that bash doesn't have named function arguments, nor references,
and only limited return values (integers 0 - 255). So, we're sorting
an array named N in place. This sort has a worst case runtime of
\(\mathcal{\Theta} (N^2)\).
Once we have a sort function, the rest is simple:
while read -a N
do ssort # Sort the array N
#
# Find the maximum value
#
max=0
for ((i = 1; i < ${#N[*]}; i ++))
do if (((N[i] - N[i - 1]) > max))
then max=$((N[i] - N[i - 1]))
fi
done
#
# Print the maximum
#
echo $max
done
Find the full program on GitHub.
C lets us work hard. We start with a function which takes a
string (char *) as input, extract the numbers from that
string, and which populates an array with those numbers.
The size of the array will be returned.
typedef long long number;
# define number_fmt "%lld"
/*
* Given a string, extract the numbers, and put them into an
* array. Return the number of extracted numbers.
*/
size_t extract_numbers (char * line, number ** list) {
/*
* First, calculate the number of numbers
*/
char * ptr = line; /* Copy of line, so we don't modify line */
number num; /* Number scanned */
int n; /* Number of characters scanned */
size_t c = 0; /* Count of numbers scanned */
number * numbers; /* List of numbers to be created */
while (sscanf (ptr, number_fmt "%n", &num, &n) == 1) {
ptr += n;
c ++;
}
/*
* Allocate memory for the array to be returned
*/
if ((numbers = (number *) malloc (c * sizeof (number))) == NULL) {
perror ("Malloc failed");
exit (1);
}
/*
* Scan again, this time, populate the array.
*/
ptr = line;
c = 0;
while (sscanf (ptr, number_fmt "%n", &num, &n) == 1) {
ptr += n;
numbers [c ++] = num;
}
* list = numbers;
return (c);
}
To sort an array, C has a qsort, but that requires a comparison
function. This function takes two
void pointers as
arguments — they point to the elements we want to compare. So,
we first have to cast the pointers to pointers of the appropriate
type, and then we can compare the numbers:
int num_compare (const void * p1, const void * p2) {
number n1 = * (const number *) p1;
number n2 = * (const number *) p2;
return n1 < n2 ? -1 : n1 > n2 ? 1 : 0;
}
Note that the compare function returns -1 if the first number is
less than the second number; it returns 1 if the first number is
larger than the second number; and it return 0 if the numbers are equal.
We are now ready for the main part of the C solution:
int main (void) {
char * line = NULL;
size_t len = 0;
size_t str_len;
/*
* Read a line of input
*/
while ((str_len = getline (&line, &len, stdin)) != -1) {
/*
* Extract the numbers from the line of input, putting
* them in an array N; n will be the number of numbers in N.
*/
number * N = NULL;
size_t n = extract_numbers (line, &N);
/*
* Sort the array.
*/
qsort (N, n, sizeof (number), num_compare);
/*
* Find the maximum
*/
number max = 0;
for (size_t i = 1; i < n; i ++) {
if (N [i] - N [i - 1] > max) {
max = N [i] - N [i - 1];
}
}
/*
* Print it
*/
printf (number_fmt "\n", max);
/*
* Free the used memory for the array of numbers.
*/
free (N);
}
free (line);
return (0);
}
Find the full program on GitHub.
The Lua implemenation is pretty straightforward:
for line in io . lines () do
--
-- Extract the numbers from the line of input
-- Note that gmatch() doesn't return an array or list;
-- we have to iterate over it, and construct an array
--
local numbers = {}
for i in line : gmatch ("(%S+)") do
numbers [#numbers + 1] = i
end
--
-- Sort it; the default sort is numerical
--
table . sort (numbers)
--
-- Find the max difference
--
local max = 0
for i, n in ipairs (numbers) do
if (i > 1 and (numbers [i] - numbers [i - 1]) > max)
then max = numbers [i] - numbers [i - 1]
end
end
--
-- And print it
--
print (max)
end
Find the full program on GitHub.
Using Node.js, we can write a program which is basically a single statement.
We're using the readline
module, which gives a call back on each line read.
In this call back, we split the given line on whitespace, and then
we numify each chuck by using the unary + operator.
We then sort
the array, and use reduce
to find the maximum of the differences.
require ('readline')
. createInterface ({input: process . stdin})
. on ('line', _ => console . log (
_ . split (/\s+/) // Split on white space
. map (_ => +_) // Numify
. sort () // Sort
. reduce ((max, _, i, N) => { // Find max difference
return i > 0 && (N [i] - N [i - 1]) > max
? (N [i] - N [i - 1]) : max
}, 0)))
Find the full program on GitHub.
Python makes life easy, although it requires an explict cast from string to integers.
import fileinput
for line in fileinput . input ():
#
# Extract the numbers from the line of input, by splitting
# the input on white space, and forcing the chucks to be integer.
#
N = list (map (lambda x: int (x), line . split ()))
#
# sort () modifies the array
#
N . sort ()
#
# Find the maximum difference
#
max = 0
for i in range (1, len (N)):
if N [i] - N [i - 1] > max:
max = N [i] - N [i - 1]
#
# Print it
#
print (max)
Find the full program on GitHub.
Nothing special in Ruby either. The also need an explicit cast from string to integer.
ARGF . each_line do |_|
#
# Split input on white space, turn the chucks into integers,
# then sort the result.
#
n = (_ . split (/\s+/))
. map {|_| _ . to_i}
. sort
#
# Find the maximum difference.
#
max = 0
n . each_index {|i|
if i > 0 && (n [i] - n [i - 1]) > max
then max = n [i] - n [i - 1]
end
}
#
# And print it
#
puts (max)
end
Find the full program on GitHub.