Sunday, June 29, 2008

Array Difference

Given an array of size n.find 2 numbers from array whose difference is least.

Solution:

Sort the list and substract consecutive numbers to get the smallest difference.

Time : O(nlogn)
at

9 comments:

  1. Ashish ShuklaSunday, July 06, 2008

    This comment has been removed by the author.

    ReplyDelete
  2. GhotterSunday, July 06, 2008

    can u pls explain it more....your algorithm seems to be O(n) and also seems to be incorrect....

    ReplyDelete
  3. Ashish ShuklaSunday, July 06, 2008

    This comment has been removed by the author.

    ReplyDelete
  4. Ashish ShuklaSunday, July 06, 2008

    This comment has been removed by the author.

    ReplyDelete
  5. GhotterSunday, July 06, 2008

    I have written the following code...
    for the algo which u gave...
    The output should be 5 - 10 but it gives 60 50...

    public class JustLikeThat {

    public JustLikeThat() {
    }
    public static void main(String args[])
    {
    int n = 5;
    int[] arr = new int[5];
    arr[0] = 5;
    arr[1] = 90;
    arr[2] = 60;
    arr[3] = 50;
    arr[4] = 10;
    int temp = 0;
    for(int i = 2;i < n;i++)
    {
    if(diff(arr[0],arr[1]) == 0)
    break;
    if(diff(arr[i],arr[0])< diff(arr[i],arr[1]) && diff(arr[i],arr[0])< diff(arr[0],arr[1]))
    {
    //swap(arr[1],arr[i]);
    temp = arr[1];
    arr[1] = arr[i];
    arr[i] = temp;
    }
    if(diff(arr[i],arr[0]) >diff(arr[i],arr[1]) && diff(arr[i],arr[1])< diff(arr[0],arr[1]))
    {
    //swap(arr[1],arr[i]);
    temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    }
    }
    System.out.println(" "+arr[0] + " " + arr[1]);
    }
    static int diff(int i, int j)
    {
    return (i - j) > 0 ? (i - j): (j - i);
    }



    }

    ReplyDelete
  6. Ashish ShuklaSunday, July 06, 2008

    This comment has been removed by the author.

    ReplyDelete
  7. GhotterSunday, July 06, 2008

    Try 5 90 50 60 10 as the input.....

    ReplyDelete
  8. Ashish ShuklaSunday, July 06, 2008

    This comment has been removed by the author.

    ReplyDelete
  9. RahulThursday, January 15, 2009

    solution seems to be modified in this way:

    So, find the numbers which results shortest diff. then find those numbers in orig array and get the actual index.


    main(){
    int a[]={1,81,45, 48, 389, 6, 7 };
    int s=sizeof(a)/sizeof(*a);
    int *b=new int[s];
    memcpy( b, a , s*sizeof(int));
    int min,a1,a2;
    sort(a, a+s);
    min=a[1]-a[0];a1=0; a2=1;
    for(int i=0; i< s-1 ; i++){
    int t=a[i+1] - a[i];
    if(t < min){ min=t; a1=i; a2=i+1;}
    }
    }
    a1=a-find(b, b+s, a[a1]);
    a2=a-find(b, b+s, a[a2]);
    //a1,a2 is answer
    }

    ReplyDelete