1

I was given an array like this array(1,5,3,4,2);
Say k=2, I'm supposed to find out the count of pairs whose difference is 2. In this case it should return 3 because 5-3, 4-2, 3-1

Here's what I have tried. It works fine I'm looping through the array twice O(n^2) complexity, I'm wondering if there is a better way to achieve this. 

$arr = array(1,5,3,4,2); 
$k =2;
function find_pairs($arr, $k)
{
    $count = 0;
    for ($i=0 ; $i<= count($arr)-1 ; $i++)
    {
        for ($j=$i+1; $j <= count($arr)-1 ; $j++)
        {
            if ($arr[$i]-$arr[$j] == $k || $arr[$j]-$arr[$i]==$k)
            {
                $count++;
            }
        }
    }
    return $count;
}
echo find_pairs($arr, $k);

Thanks

Wild Widow
  • 2,359
  • 3
  • 22
  • 34

4 Answers4

1

Ofcourse, There are many ways:

Using Sorting:

Sort the array arr
Take two pointers, l and r, both pointing to 1st element
Take the difference arr[r] – arr[l]
If value diff is K, increment count and move both pointers to next element
if value diff > k, move l to next element
if value diff < k, move r to next element
return count

one with complexity of O(n) is :

1) Initialize count as 0.
2) Insert all distinct elements of arr[] in a hash map.  While inserting, 
   ignore an element if already present in the hash map.
3) Do following for each element arr[i].
   a) Look for arr[i] + k in the hash map, if found then increment count.
   b) Look for arr[i] - k in the hash map, if found then increment count.
   c) Remove arr[i] from hash table.

Anyways you can refer to this link for more info.

Navneet
  • 4,543
  • 1
  • 19
  • 29
  • This approach is not O(n). Actually, I don't think O(n) is even possible in this scenario. Best that can be done is O(n logn). Searching for any element in hashmap takes O(log n). – vish4071 Sep 04 '15 at 05:42
  • A simple hashing technique to use values as index can be used to search an element in constant time. – Navneet Sep 04 '15 at 05:48
0

Yes of course. Below is something you can use:

  • sort array (a, say and n elements)
  • search (binary) for a[i]+k for all elements from index 0 through n-2. No. of successful hits is your answer.

This has O(n log n) complexity.

vish4071
  • 5,135
  • 4
  • 35
  • 65
0

Yeah. You may use unordered_set. Elaboration is given below :

1. Insert the all elements of array into unordered_set.
2. Initialize count=0
3. for loop i=0 to i=n where n is the length of array
         if arr[i]+k is found then increment count
4. Return count.

The complexity of above procedure is O(N).

Php code Snippet: 

function find_pairs($a, $k) 
{
    $num = array_flip($a);
    $count = 0;
    foreach($num as $n => $_unused) 
    {
        if(isset($num[$n + $k])) 
        {
            $count++;
        }
    }
    return $count;
}
rashedcs
  • 3,588
  • 2
  • 39
  • 40
-1

Given an integer n, count and return the number of zeros that are present in the given integer using recursion.

def count0(n):
    if n==0:
        return 0
    if n%10==0:
        return 1+count0(int(n/10))
    else:
        return count0(int(n/10))

n=int(input())
print(count0(n))
kipzes
  • 694
  • 2
  • 10
  • 27
Shantanu singh
  • 1