Weekly Challenge 243

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Reverse Pairs

Task

You are given an array of integers.

Write a script to return the number of reverse pairs in the given array.

A reverse pair is a pair (i, j) where: a) 0 <= i < j < nums.length and b) nums[i] > 2 * nums[j].

My solution

This is relatively straight forward. Have a loop for the values of i. Count the number of times nums[i] > 2 * nums[j] is true for the remaining values, where j starts at the position after i.

for i, value in enumerate(ints):
    solutions += sum(1 for j in ints[i+1:] if value > 2 * j)

Examples

$ ./ch-1.py 1 3 2 3 1
2

$ ./ch-1.py 2 3 4 5 1
3

Task 2: Floor Sum

Task

You are given an array of positive integers (>=1).

Write a script to return the sum of floor(nums[i] / nums[j]) where 0 <= i,j < nums.length. The floor() function returns the integer part of the division.

My solution

This is also pretty straight forward. Python's math module provides a floor() method, while in Perl the POSIX module does.

Python supports a double for loop, so it can be completed in a single function.

solution = sum(math.floor(i / j) for i in ints for j in ints)

Meanwhile in Perl I have a traditional foreach loop for the i variable, and a sum + map function for the j value.

foreach my $i (@ints) {
    $solution += sum( map { floor( $i / $_ ) } @ints );
}

Examples

$ ./ch-2.py 2 5 9
10

$ ./ch-2.py 7 7 7 7 7 7 7
49