ArrayList pair sum Sorted and rotated

ArrayList pair sum Sorted and rotated
 avatar
sy07
java
a year ago
1.2 kB
5
Indexable
import java.util.ArrayList;

public class ArrayList_pair_sum_Sorted_and_rotated {
    // ---> 0(n)
    public static boolean pairsum(ArrayList<Integer> list, int target){
        int bp = -1;  // breaking point
        int n = list.size();
        for(int i=0; i<list.size(); i++){
            if(list.get(i) > list.get(i+1)){
                bp = i;
                break;
            }
        }
        int lp = bp+1; // smallest element
        int rp = bp-1;  // largest element

        while(lp != rp){
           if(list.get(lp) + list.get(rp) == target){
               return true;
           }
           if(list.get(lp) + list.get(rp) < target){
               lp = (lp+1)%n;
           }else{
               rp = (n+rp-1)%n;
           }
        }
        return false;
    }
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        // 11,15,6,8,9,10 - sorted and rotated
        list.add(11);
        list.add(15);
        list.add(6);
        list.add(8);
        list.add(9);
        list.add(10);
        int target = 100;

        System.out.println(pairsum(list,target));
    }
}
Editor is loading...
Leave a Comment