简单的PHP程序需要较少的执行时间

Question

i had applied for a job recently and the requirement was to complete a test and then interview 2 questions were given for test which was very simple and i did it successfully but still i was told that i have failed the test because the script took more than 18 seconds to complete execution. here is the program i dont understand what else i could do to make it fast. although i have failed the test but still wants to know else i could do? Program language is PHP and i had to do it using command line input

here is the question:

 K Difference
Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K. [K>0 and K<1e9]

Input Format:
1st line contains N & K (integers).
2nd line contains N numbers of the set. All the N numbers are assured to be distinct.
Output Format:
One integer saying the no of pairs of numbers that have a diff K.

Sample Input #00:
5 2
1 5 3 4 2

Sample Output #00:3
Sample Input #01:
10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 
Sample Output #01:
0
Note: Java/C# code should be in a class named "Solution"
Read input from STDIN and write output to STDOUT.

and this is the solution

$fr = fopen("php://stdin", "r");
$fw = fopen("php://stdout", "w");

fscanf($fr, "%d", $total_nums);
fscanf($fr, "%d", $diff);

$ary_nums = array();
for ($i = 0; $i < $total_nums; $i++) {
    fscanf($fr, "%d", $ary_nums[$i]);
}

$count = 0;
sort($ary_nums);
for ($i = $total_nums - 1; $i > 0; $i--) {
    for ($j = $i - 1; $j >= 0; $j--) {
        if ($ary_nums[$i] - $ary_nums[$j] == $diff) {
            $count++;
            $j = 0;
        }
    }
}
fprintf($fw, "%d", $count);

Answer 1

Your algorithm's runtime is O(N^2) that is approximately 10^5 * 10^5 = 10^10. With some basic observation it can be reduced to O(NlgN) which is approximately 10^5*16 = 1.6*10^6 only.

Algorithm:

1. Sort the array ary_nums.
2. for every i'th integer of the array, make a binary search to find if ary_nums[i]-K, is present in the array or not. If present increase result, skip i'th integer otherwise.

sort($ary_nums);

for ($i = $total_nums - 1; $i > 0; $i--) {

        $hi  = $i-1;
        $low = 0;
        while($hi>=$low){
            $mid = ($hi+$low)/2;
            if($ary_nums[$mid]==$ary_nums[$i]-$diff){
                $count++;
                break;
            }
            if($ary_nums[$mid]<$ary_nums[$i]-$diff){
                 $low = $mid+1;
            }
            else{
                 $hi  = $mid-1;
            }
        }
    }
}