Pacific-Design.com

    
Home Index

1. Algorithms

2. Smallest Difference

Algorithms / Smallest Difference /

Find the smallest difference in given array

Scala - O(n log n)

val s=Console.readLine.split(",").map(_.toInt).sortBy(i=>i)
if(s.size<2)0 else s.tail.zip(s).map(x=>x._1-x._2).min

Java - O(n log n)

  1. Sort the array
  2. Check adjacent pairs of number
class SmallestDifferenceOfNumbers {
  
    public static int smallest(ArrayList<Integer> input) {
     
        Collections.sort(input);
        int min = input.get(1) - input.get(0);
        
        forint i=0; i < input.size() - 2; i++) {
            
            if( (input.get(i+1) - input.get(i) ) {
                min = input.get(i+1) - input.get(i);
                System.out.println(min);
            }               
        }
        return min;       
    }
  
    public static void main(String[] args) {
   
        smallest(new ArrayList<Integer>( Arrays.asList(-4, 2, 4, 6, 0) ) ) == 2;
   }
              
}

C++ - Time Complexity : O(n)

// C++ implementation of simple method to find
// minimum difference between any pair
#include <bits/stdc++.h>
using namespace std;

// Returns minimum difference between any pair
int findMinDiff(int arr[], int n)
{
    // Initialize difference as infinite
    int diff = INT_MAX;

    // Find the min diff by comparing difference
    // of all possible pairs in given array
    for (int i=0; i<n-1; i++)
        for (int j=i+1; j<n; j++)
            if (abs(arr[i] - arr[j]) < diff)
                diff = abs(arr[i] - arr[j]);

    // Return min diff
    return diff;
}

// Driver code
int main()
{
    int arr[] = {1, 5, 3, 19, 18, 25};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum difference is " << findMinDiff(arr, n);
    return 0;
}