Problem: Count Pairs in an Array

Given an array of integers arr[0..n-1], count all pairs (arr[i], arr[j]) in the such that i*arr[i] > j*arr[j], 0 =< i < j j*arr[j] are
(10, 2) (10, 4) (10, 1) (2, 1) (4, 1)
Input:

The first line of input contains T denoting the no. of test cases . Then T test cases follow . The first line of each test case contains an Integer N and the next line contains N space separated values of the array A[ ] .

Output:

For each test case output the required result in a new line.

Constraints:

1<=T<=100
1<=N<=100
1<=A[ ] <=1000

Example:

Input:
2
7
5 0 10 2 4 1 6
4
8 4 2 1
Output:
5
2

import itertools
def count_pairs(arr):
    """
        counting all pairs in arr such that 
        i*arr[i] > j*arr[j] and j > i
        arr: a list of tuple - [(index, value),...]
    """
    # get all pairs
    all_pairs = list(itertools.combinations(arr, 2))
    # check all pairs for the condition
    count_pairs = 0
    for pair in all_pairs:
        i, j, arr_i, arr_j = pair[0][0], pair[1][0], pair[0][1], pair[1][1]
        if i*arr_i > j*arr_j and j > i:
            count_pairs += 1
    return count_pairs

if __name__ == '__main__':
    t = input()
    for _ in range(t):
        n = input()
        arr = map(int, raw_input().strip().split())
        arr = [(i,arr_i) for (i, arr_i) in enumerate(arr)]
        print count_pairs(arr)

**'Life is short, why haven't you learned python yet?'

Advertisements