[algogeeks] Re: A Nice Programming Challenge Question

2011-08-07 Thread Dave 
@Yasir: Sort the numbers. Then

int i = 0, j = 1, m, p = 0;
while( j  N )
{
m = a[j] - a[i];
if( m = K )
++p;
else if( m  K )
++j;
else
++i;
}
// answer = p

Complexity = O(n log n).

Dave

On Aug 7, 12:53 pm, Yasir yasir@gmail.com wrote:
 Guys,
 Let's try to find out an efficient solution for the following prob:

 Given N numbers , [N=10^5] we need to count the total pairs of
 numbers that have a difference of K. [K0 and K1e9]

 Input Format:
 1st line contains N  K.
 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.

 PS: Note that n is very large, so try to come up with an efficient
 solution. :)

 Source:http://www.interviewstreet.com/recruit/challenges/dashboard/

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: A Nice Programming Challenge Question

2011-08-07 Thread Yasir 
@Dave and Piyush.
Thanks.  Nice approach :)

Is further optimization possible?
(May be by increasing space complexity)

On Aug 7, 11:09 pm, Piyush Kapoor pkjee2...@gmail.com wrote:
 First sort the array.Then for each element,say x ,do a binary search to find
 the element y for which (y-x)=K or y=(x+K),if the elements are not distinct
 then the number of pairs will be the upper_bound()-lower_bound() for y.
 Complexity:O(nlogn)









 On Sun, Aug 7, 2011 at 11:23 PM, Yasir yasir@gmail.com wrote:
  Guys,
  Let's try to find out an efficient solution for the following prob:

  Given N numbers , [N=10^5] we need to count the total pairs of
  numbers that have a difference of K. [K0 and K1e9]

  Input Format:
  1st line contains N  K.
  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.

  PS: Note that n is very large, so try to come up with an efficient
  solution. :)

  Source:http://www.interviewstreet.com/recruit/challenges/dashboard/

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

 --
 *Regards,*
 *Piyush Kapoor,*
 *2nd year,CSE
 IT-BHU*

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: A Nice Programming Challenge Question

2011-08-07 Thread Shuaib Khan 
On Sun, Aug 7, 2011 at 11:06 PM, Dave dave_and_da...@juno.com wrote:

 @Yasir: Sort the numbers. Then

 int i = 0, j = 1, m, p = 0;
 while( j  N )
 {
m = a[j] - a[i];
if( m = K )
++p;
else if( m  K )
++j;
else
++i;
 }
 // answer = p


Looks like an infinite loop in there to me...




 Complexity = O(n log n).

 Dave

 On Aug 7, 12:53 pm, Yasir yasir@gmail.com wrote:
  Guys,
  Let's try to find out an efficient solution for the following prob:
 
  Given N numbers , [N=10^5] we need to count the total pairs of
  numbers that have a difference of K. [K0 and K1e9]
 
  Input Format:
  1st line contains N  K.
  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.
 
  PS: Note that n is very large, so try to come up with an efficient
  solution. :)
 
  Source:http://www.interviewstreet.com/recruit/challenges/dashboard/

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
Shuaib
http://www.bytehood.com
http://twitter.com/ShuaibKhan

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: A Nice Programming Challenge Question

2011-08-07 Thread sindhu 
@Dave: after p++ is executed hw will ur pgm continue??

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: A Nice Programming Challenge Question

2011-08-07 Thread Dave 
@Shuaib and Sindhu: Right. Take out the first else, or replace ++p
with {++p ; ++i; ++j}.

Dave

On Aug 7, 1:42 pm, Shuaib Khan aries.shu...@gmail.com wrote:
 On Sun, Aug 7, 2011 at 11:06 PM, Dave dave_and_da...@juno.com wrote:
  @Yasir: Sort the numbers. Then

  int i = 0, j = 1, m, p = 0;
  while( j  N )
  {
     m = a[j] - a[i];
     if( m = K )
         ++p;
     else if( m  K )
         ++j;
     else
         ++i;
  }
  // answer = p

 Looks like an infinite loop in there to me...







  Complexity = O(n log n).

  Dave

  On Aug 7, 12:53 pm, Yasir yasir@gmail.com wrote:
   Guys,
   Let's try to find out an efficient solution for the following prob:

   Given N numbers , [N=10^5] we need to count the total pairs of
   numbers that have a difference of K. [K0 and K1e9]

   Input Format:
   1st line contains N  K.
   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.

   PS: Note that n is very large, so try to come up with an efficient
   solution. :)

   Source:http://www.interviewstreet.com/recruit/challenges/dashboard/

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

 --
 Shuaibhttp://www.bytehood.comhttp://twitter.com/ShuaibKhan

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.