title: Efficient way to find the number of all such triplets (from a given set of numbers) whose numbers are in A.P.?
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/13240330/fastest-algorithm-count-number-of-3-length-ap-in-array">fastest algorithm count number of 3 length AP in array</a>  </p>
  </blockquote>
  
  
  
  <p>I've been working on the following problem taken from CodeChef's Nov12 challenge. I tried it using the basic formula for checking whether three numbers a, b, c are in A.P., they are if c-b=b-a i.e. 2b=a+c. Here is the problem:</p>
  
  <p>First line of the input contains an integer N (3 ≤ N ≤ 100000). Then the following line contains N space separated integers A1, A2, …, AN and they have values between 1 and 30000 (inclusive).</p>
  
  <p>Output the number of ways to choose a triplet such that they are three consecutive terms of an arithmetic progression.
  Example</p>
  
  <p>Input:</p>
  
  <p>10</p>
  
  <p>3 5 3 6 3 4 10 4 5 2</p>
  
  <p>Output:
  9</p>
  
  <p>Explanation: </p>
  
  <p>The followings are all 9 ways to choose a triplet</p>
  
  <p>1 : (i, j, k) = (1, 3, 5), (Ai, Aj, Ak) = (3, 3, 3)</p>
  
  <p>2 : (i, j, k) = (1, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)</p>
  
  <p>3 : (i, j, k) = (1, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)</p>
  
  <p>4 : (i, j, k) = (3, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)</p>
  
  <p>5 : (i, j, k) = (3, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)</p>
  
  <p>6 : (i, j, k) = (4, 6, 10), (Ai, Aj, Ak) = (6, 4, 2)</p>
  
  <p>7 : (i, j, k) = (4, 8, 10), (Ai, Aj, Ak) = (6, 4, 2)</p>
  
  <p>8 : (i, j, k) = (5, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)</p>
  
  <p>The code I used is</p>
  
  <pre><code>#include&lt;stdio.h&gt;
  int scan() {
      int p=0;
      char c;
      c=getchar_unlocked();
      while(c&lt;'0' || c&gt;'9')
          c=getchar_unlocked();
      while(c&gt;='0' &amp;&amp; c&lt;='9'){
          p=(p&lt;&lt;3)+(p&lt;&lt;1)+c-'0';
          c=getchar_unlocked();
      }
      return(p);
  }
  int main() {
      int N, i, j, k, count=0;
      N=scan();
      int a[N];
      for(i=0;i&lt;N;i++)
          a[i]=scan();
      for(i=0;i&lt;N-2;i++)
          for(j=i+1;j&lt;N-1;j++)
              for(k=j+1;k&lt;N;k++)
                  if(a[k]+a[i]==2*a[j])
                      ++count;
      printf("%d\n", count);
      return 0;
   }
  </code></pre>
  
  <p>As you can see the constraints on variables, it is clear that we need fast and efficient algo. For the sake of safety I even used faster I/O but still the program runs out of time.
  It is clear that the algorithm is not that efficient, as I am using three nested loops. One other way that come to reduce the number of some k's is to break the k' loop as soon as a match is found, then I would have added a continue; below ++count and that is working but again NOT that efficient as the problem requires.</p>
  
  <p>Please tell me some fast algo to do this, or if I might learn some mathematical theorem here to find AP triplets quicker.</p>