subject:"Re\: \[algogeeks\] Re\: GOOGLE Q1"

Re: [algogeeks] Re: GOOGLE Q1

2013-02-05 Thread Vandana Bachani

In the first pass create a difference array of size n-1 where n is the size
of the input array.
D[i] = A[i+1] - A[i]
Look for for the longest consecutive no. of times an element is repeated in
the difference array.

public void longestAP(int[] a, int n) {
 int[] diff = new int[n-1];
 for(int i = 0; i < n-1; i++) {
  diff[i] = a[i+1]-a[i];
 }
 int maxDiff = diff[0], maxi = 0, maxCount = 1;
 int currentDiff = -1, currentCount = 0, currenti = -1;
 for(int i = 1; i < n-1; i++) {
  if(diff[i] == maxDiff) { maxCount++; }
  else {
   if(diff[i] == currentDiff) { currentCount++; if (currentCount >
maxCount) { maxDiff = currentDiff; maxCount = currentCount; maxi =
currenti;}}
   else {
currentDiff = diff[i]; currenti = i; currentCount = 1;
   }
  }
 }
 System.out.print("Elements of the AP: ") ;
 for(int i = maxi; i <= maxi+maxCount; i++) {
  System.out.print(a[i]+" ");
 }
 System.out.println();
}

On Tue, Feb 5, 2013 at 5:33 PM, Ian Martin Ajzenszmidt  wrote:

>
>
> On Friday, 8 July 2011 04:13:38 UTC+10, Piyush Sinha wrote:
>
>
>> Given an array of integers A, give an algorithm to find the longest
>> Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik,
>> such that
>>
>> A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
>> largest possible.
>>
>> The sequence S1, S2, …, Sk is called an arithmetic progression if
>>
>> Sj+1 – Sj is a constant.
>>
> Click on the following links or copy and paste them  into your browser.
> Many interesting possibilities.
>
> https://www.google.com.au/search?client=ubuntu&channel=fs&q=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that+A[i1&ie=utf-8&oe=utf-8&redir_esc=&ei=GpQRUZXnJKaeiAen7oDYAw
>
>
> http://scholar.google.com/scholar?hl=en&q=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that++A[i1]%2C+A[i2]%2C+%E2%80%A6%2C+A[ik]+forms+an+arithmetic+progression%2C+and+k+is+the+largest+possible.&btnG=&as_sdt=1%2C5&as_sdtp=
>
>> --
>> *Piyush Sinha*
>> *IIIT, Allahabad*
>> *+91-8792136657*
>> *+91-7483122727*
>> *https://www.facebook.com/**profile.php?id=10655377926*
>>
>>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Vandana Bachani
Graduate Student, MSCE
Computer Science & Engineering Department
Texas A&M University, College Station

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: GOOGLE Q1

2012-11-17 Thread bharat b

http://theory.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf

On Fri, Nov 16, 2012 at 8:55 PM, rajesh pandey  wrote:

> I think its the stricter version of LIS ,  where when you  see for the
> increasing number  , just see the number which is greater with the number k
> than the previous one.
>
> Thanks ,
> Rajesh Pandey
>
>
> On Fri, Nov 16, 2012 at 7:55 PM, bharat b wrote:
>
>> @deepak : all the numbers in the array should be continuous or those k
>> elemenst can be any where ?
>>
>>
>> On Thu, Nov 15, 2012 at 2:18 PM, deepak mishra 
>> wrote:
>>
>>>
>>>
>>> On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:

 Given an array of integers A, give an algorithm to find the longest
 Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik,
 such that

 A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
 largest possible.

 The sequence S1, S2, …, Sk is called an arithmetic progression if

 Sj+1 – Sj is a constant.

 --
 *Piyush Sinha*
 *IIIT, Allahabad*
 *+91-8792136657*
 *+91-7483122727*
 *https://www.facebook.com/**profile.php?id=10655377926*

  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/umM2YKQz-9oJ.
>>>
>>> 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.
>>>
>>
>>  --
>> 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.
>>
>
>  --
> 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: GOOGLE Q1

2012-11-16 Thread rajesh pandey

I think its the stricter version of LIS ,  where when you  see for the
increasing number  , just see the number which is greater with the number k
than the previous one.

Thanks ,
Rajesh Pandey

On Fri, Nov 16, 2012 at 7:55 PM, bharat b wrote:

> @deepak : all the numbers in the array should be continuous or those k
> elemenst can be any where ?
>
>
> On Thu, Nov 15, 2012 at 2:18 PM, deepak mishra wrote:
>
>>
>>
>> On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:
>>>
>>> Given an array of integers A, give an algorithm to find the longest
>>> Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik,
>>> such that
>>>
>>> A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
>>> largest possible.
>>>
>>> The sequence S1, S2, …, Sk is called an arithmetic progression if
>>>
>>> Sj+1 – Sj is a constant.
>>>
>>> --
>>> *Piyush Sinha*
>>> *IIIT, Allahabad*
>>> *+91-8792136657*
>>> *+91-7483122727*
>>> *https://www.facebook.com/**profile.php?id=10655377926*
>>>
>>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/umM2YKQz-9oJ.
>>
>> 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.
>>
>
>  --
> 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.
>

-- 
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: GOOGLE Q1

2012-11-16 Thread bharat b

@deepak : all the numbers in the array should be continuous or those k
elemenst can be any where ?

On Thu, Nov 15, 2012 at 2:18 PM, deepak mishra wrote:

>
>
> On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:
>>
>> Given an array of integers A, give an algorithm to find the longest
>> Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik,
>> such that
>>
>> A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
>> largest possible.
>>
>> The sequence S1, S2, …, Sk is called an arithmetic progression if
>>
>> Sj+1 – Sj is a constant.
>>
>> --
>> *Piyush Sinha*
>> *IIIT, Allahabad*
>> *+91-8792136657*
>> *+91-7483122727*
>> *https://www.facebook.com/**profile.php?id=10655377926*
>>
>>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/umM2YKQz-9oJ.
>
> 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.
>

-- 
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: GOOGLE Q1

2012-11-15 Thread deepak mishra

sdfsdfsdfsdfsdf

On Monday, 11 July 2011 17:01:36 UTC+5:30, Sunny wrote:
>
> @Divye sir
> yeah that will work fine if D is in reasonable limits ..
>
> On Mon, Jul 11, 2011 at 4:26 PM, DK >wrote:
>
>> @Ritu: Your solution is incorrect.
>>
>> Consider
>>
>> 1 3 41 43 47 49 90 100 110
>>
>> Maximum repeated 'd' value:
>> '2' for the pairs (1,3), (41,43), (47,49) = 3 repeats. However, the 
>> sequences themselves are not part of an AP.
>> The longest AP is of size 3 - (90, 100, 110) with a d of 10.
>>
>>
>> --
>> DK
>>
>> http://twitter.com/divyekapoor
>> http://www.divye.in
>>
>>  -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit 
>> https://groups.google.com/d/msg/algogeeks/-/FnebaYc_FbIJ.
>>
>> To post to this group, send email to algo...@googlegroups.com
>> .
>> To unsubscribe from this group, send email to 
>> algogeeks+...@googlegroups.com .
>> For more options, visit this group at 
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> -- 
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/zUK_Qh6FshsJ.
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: GOOGLE Q1

2011-07-11 Thread DK

@Yogi: Your algo (though it seems N^2) is actually N^3.

According to your algorithm, you need to have a loop to select the starting 
value of the common difference of the AP.
As per what you've written, an implementation is:

for all distinct d values in the diff matrix { // O(N^2) loop
   Let location of d value be (i, j)
   length = 2;
repeat:
   for k in range (j...N-1) { // O(N) loop
   if(diff[j][k] == d) {
   length++;
   j = k;
   goto repeat;
   }
   }
}

The time complexity of this solution is O(number of distinct d values x 
(length of sequence - 1) x N).
For the case that all the diff values are distinct, the time complexity of 
this solution is O(N^3) (since length of sequence will be 2)
Please let me know if you have a way to implement this faster than O(N^3) or 
an alteration of the algorithm that brings down the complexity to O(N^2).
Alternatively, if you believe that this algo is O(N^2), could you please 
provide a complexity analysis supporting that?

--
DK

http://twitter.com/divyekapoor
http://www.divye.in

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/pKqqgqKxFzIJ.
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: GOOGLE Q1

2011-07-11 Thread Yogesh Yadav

with matrix this problem will be in O(n^2).

We don' have to just check the max number present in matrix. We have to
check as


array a[]= 1,2,3,4,5,6,8,10,12,14

diff[][]=  1  2  3  4  5  6  8  10  12  14
2  0  1  2  3  4  6   8   10  12
3 -1  0  1  2  3  5   79   11
4 -2  -1 0  1  2  4   68   10
5 0
6 0
80
   100
   12  0
   14   0


now in this diff[][] you have to search for if the diff[2][3] =1 then there
should be diff[3][i]=1 and then diff[i][j]=1 ...and so on ...this will give
n A.P of 6 elements

but check for diff[2][4]=2 then diff[4][6]=2 and so on...this will give
an A.P of 7

and its solvable in O(n^2)

On Mon, Jul 11, 2011 at 5:01 PM, sunny agrawal wrote:

> @Divye sir
> yeah that will work fine if D is in reasonable limits ..
>
>
> On Mon, Jul 11, 2011 at 4:26 PM, DK  wrote:
>
>> @Ritu: Your solution is incorrect.
>>
>> Consider
>>
>> 1 3 41 43 47 49 90 100 110
>>
>> Maximum repeated 'd' value:
>> '2' for the pairs (1,3), (41,43), (47,49) = 3 repeats. However, the
>> sequences themselves are not part of an AP.
>> The longest AP is of size 3 - (90, 100, 110) with a d of 10.
>>
>>
>> --
>> DK
>>
>> http://twitter.com/divyekapoor
>> http://www.divye.in
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/FnebaYc_FbIJ.
>>
>> 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.
>>
>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>  --
> 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.
>

-- 
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: GOOGLE Q1

2011-07-11 Thread sunny agrawal

@Divye sir
yeah that will work fine if D is in reasonable limits ..

On Mon, Jul 11, 2011 at 4:26 PM, DK  wrote:

> @Ritu: Your solution is incorrect.
>
> Consider
>
> 1 3 41 43 47 49 90 100 110
>
> Maximum repeated 'd' value:
> '2' for the pairs (1,3), (41,43), (47,49) = 3 repeats. However, the
> sequences themselves are not part of an AP.
> The longest AP is of size 3 - (90, 100, 110) with a d of 10.
>
>
> --
> DK
>
> http://twitter.com/divyekapoor
> http://www.divye.in
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/FnebaYc_FbIJ.
>
> 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.
>



-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

-- 
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: GOOGLE Q1

Re: [algogeeks] Re: GOOGLE Q1

Re: [algogeeks] Re: GOOGLE Q1

Re: [algogeeks] Re: GOOGLE Q1

Re: [algogeeks] Re: GOOGLE Q1

Re: [algogeeks] Re: GOOGLE Q1

Re: [algogeeks] Re: GOOGLE Q1

Re: [algogeeks] Re: GOOGLE Q1

8 matches

Site Navigation

Mail list logo

Footer information