twoArrays

HackerRank 问题: twoArrays
Categories:
Tags:

Question

There are two n-element arrays of integers, A and B. Permute them into some A' and B' such that the relation A'[i] + B'[i] holds for all i where 0 <= i < n .

There will be q queries consisting of A, B ,and k. For each query, return YES if some permutation A', B' satisfying the relation exists. Otherwise, return NO.

HackerRank 问题: twoArrays HackerRank 问题: twoArrays

Answer

<?php

/*
 * Complete the 'twoArrays' function below.
 *
 * The function is expected to return a STRING.
 * The function accepts following parameters:
 *  1. INTEGER k
 *  2. INTEGER_ARRAY A
 *  3. INTEGER_ARRAY B
 */

function twoArrays($check_number, $element_list_1, $element_list_2) {

    // count every element number in each row
    $element_1_number_count_mapping = [];
    $element_2_number_count_mapping = [];
    foreach ($element_list_1 as $number) {
        if (!isset($element_1_number_count_mapping[$number])) {
            $element_1_number_count_mapping[$number] = 1;
            continue;
        }
        $element_1_number_count_mapping[$number]++;
    }

    foreach ($element_list_2 as $number) {
        if (!isset($element_2_number_count_mapping[$number])) {
            $element_2_number_count_mapping[$number] = 1;
            continue;
        }
        $element_2_number_count_mapping[$number]++;
    }

    // ascending sort
    ksort($element_1_number_count_mapping);
    // descending sort
    krsort($element_2_number_count_mapping);

    // permute element
    $permute_element_list_1 = [];
    $permute_element_list_2 = [];
    foreach ($element_1_number_count_mapping as $number => $number_count) {
        for ($i = 0; $i < $number_count; $i++) {
            $permute_element_list_1[] = $number;
        }
    }
    foreach ($element_2_number_count_mapping as $number => $number_count) {
        for ($i = 0; $i < $number_count; $i++) {
            $permute_element_list_2[] = $number;
        }
    }

    // check number
    $check_number_result = 'YES';
    $total_length_of_element_list = count($element_list_1);
    for ($check_element_index = 0; $check_element_index < $total_length_of_element_list; $check_element_index++) {
        $check_element_sum = $permute_element_list_1[$check_element_index] + $permute_element_list_2[$check_element_index];
        if ($check_element_sum < $check_number) {
            $check_number_result = 'NO';
            break;
        }
    }

    return $check_number_result;

}

$fptr = fopen(getenv("OUTPUT_PATH"), "w");

$q = intval(trim(fgets(STDIN)));

for ($q_itr = 0; $q_itr < $q; $q_itr++) {
    $first_multiple_input = explode(' ', rtrim(fgets(STDIN)));

    $n = intval($first_multiple_input[0]);

    $k = intval($first_multiple_input[1]);

    $A_temp = rtrim(fgets(STDIN));

    $A = array_map('intval', preg_split('/ /', $A_temp, -1, PREG_SPLIT_NO_EMPTY));

    $B_temp = rtrim(fgets(STDIN));

    $B = array_map('intval', preg_split('/ /', $B_temp, -1, PREG_SPLIT_NO_EMPTY));

    $result = twoArrays($k, $A, $B);

    fwrite($fptr, $result . "\n");
}

fclose($fptr);

Reference