JavaScript program to print all triples forming AP in a sorted array

AP is an arithmetic sequence in which the difference between two consecutive elements is always the same. We will print all triples in the sorted array that form the AP using three methods: the naive method, the binary search method, and the two-pointer method.

Problem Introduction

In this question, we get a sorted array, which means all elements are in increasing form. We have to find three elements in the array and form an AP. For example -

Given array: 1 5 2 4 3

From the given array, we have two triples: 1 2 3 and 5 4 3 because the difference between adjacent elements is equal. Also, as written, we only need to find triples, so we don't find any longer sequences.

Let's turn to the method of finding triples -

method

Naive method

In this method we just use a loop to move over the array and for each iteration we will run through another array for a larger number compared to the current index. Then we will implement a nested array again within the first nested array to find the elements that can form AP. Let's look at the code -

Example

// function to find all the triplets 
function findAP(arr){
   var n = arr.length
   // traversing over the array
   for(var i = 0; i< n;i++){
      for(var j = i+1;j<n;j++){
         for(var k = j+1; k < n; k++){
            if(arr[j] - arr[i] == arr[k] - arr[j]) {
               console.log("Triplet is: " + arr[i] + " " + arr[j] + " " + arr[k]);
            }
         }
      }
   }
}
// defining the array and calling the function 
arr = [1, 5, 2, 4, 3]
findAP(arr)

The time complexity of the above code is O(), where N is the size of the array.

The space complexity of the above code is O(1) because we are not using any extra space.

Follow the simple method

In the previous method, when we have two elements, we can find the third element because we have common differences, so to find the third element, instead of using linear search, we can use binary Search and reduce the time complexity of the above code-

Example

// function for binary search 
var binarySearch = function (arr, x, start, end) {
   if (start > end) return false;
   var mid=Math.floor((start + end)/2);
   if (arr[mid]===x) return true;
   if(arr[mid] > x)
      return binarySearch(arr, x, start, mid-1);
   else
      return binarySearch(arr, x, mid+1, end);
}
// function to find all the tripletes 
function findAP(arr){
   var n = arr.length
   // traversing over the array
   for(var i = 0; i< n;i++){
      for(var j = i+1;j<n;j++){
         // third element will be
         var third = 2*arr[j]-arr[i];
         if(binarySearch(arr,third,j+1,n)){
            console.log("Triplet is: " + arr[i] + " " + arr[j] + " " + third);
         }
      }
   }
}
// defining the array and calling the function 
arr = [1, 5, 2, 4, 3]
findAP(arr)

The time complexity of the above code is O(), where N is the size of the array.

The space complexity of the above code is O(1) because we are not using any extra space.

Efficient method

In this method we will use two pointers and find the element that has the same difference as the current position. Let's look at the code -

Example

// function to find all the triplets 
function findAP(arr){
   var n = arr.length
   
   // traversing over the array
   for(var i = 1; i< n;i++)    {
      var bptr = i-1
      var fptr = i+1
      while(bptr >= 0 && fptr < n)        {
         if(arr[i] - arr[bptr] == arr[fptr] - arr[i]){
            console.log("Triplet is: " + arr[bptr] + " " + arr[i] + " " + arr[fptr]);
            bptr--;
            fptr++;
         }
         else if(arr[i] - arr[bptr] > arr[fptr] - arr[i]){
            fptr++;
         }
         else{
            bptr--;
         }
      }
   }
}

// defining the array and calling the function 
arr = [1, 4, 7, 10, 13, 16]
findAP(arr)

The time complexity of the above code is O(N*N), where N is the size of the given array, and the space complexity of the above method is O(1) because we are not using any extra space. p>

Note - The first two methods are valid for any type of array, sorted or unsorted, but the last method only works for sorted arrays, if the array is unsorted, we It can be sorted one way or another, but this method is still the best among all the others.

in conclusion

In this tutorial, we implemented a JavaScript program to print all triples forming AP in a given sorted array. Ap is an arithmetic progression in which the difference between two consecutive elements is always the same. We have seen three methods: the naive method with time complexity O(N*N*N), the binary search method with time complexity O(N*N*log(N)), and the two-pointer method.

The above is the detailed content of JavaScript program to print all triples forming AP in a sorted array. For more information, please follow other related articles on the PHP Chinese website!