ArrayList pair sum Sorted and rotated
ArrayList pair sum Sorted and rotatedsy07
java
a year ago
1.2 kB
17
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