## Amazon Interview Question

SDE1s**Country:**United States

**Interview Type:**Phone Interview

I came up with this solution.Is there anywhere I can test my solution.Could be a blunder. Any edits are welcome.

```
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Solution {
public static void main(String... args) {
Scanner in = new Scanner(System.in);
String line1 = in.nextLine();
String[] line1Args = line1.split(" ");
int n = Integer.valueOf(line1Args[0]);
int m = Integer.valueOf(line1Args[1]);
ArrayList<Integer> setValues = new ArrayList<>();
for (int looper = 0; looper < m; looper++) {
int temp = in.nextInt();
setValues.add(temp);
Collections.sort(setValues);
int sum = 0;
for(int i = 0;i<setValues.size();i++){
if(i == 0){
if(setValues.size() == 1){
sum+=1+n;
break;
}else{
sum = 1+(setValues.get(i+1)-1);
}
}
else if(i == setValues.size()-1){
sum+= (setValues.get(i-1)+1)+n;
}
else{
sum+=(setValues.get(i-1)+1)+(setValues.get(i+1)-1);
}
}
System.out.println(sum);
}
}
}
```

```
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Solution {
public static void main(String... args) {
Scanner in = new Scanner(System.in);
String line1 = in.nextLine();
String[] line1Args = line1.split(" ");
int n = Integer.valueOf(line1Args[0]);
int m = Integer.valueOf(line1Args[1]);
ArrayList<Integer> setValues = new ArrayList<>();
for (int looper = 0; looper < m; looper++) {
int temp = in.nextInt();
setValues.add(temp);
Collections.sort(setValues);
int sum = 0;
for(int i = 0;i<setValues.size();i++){
if(i == 0){
if(setValues.size() == 1){
sum+=1+n;
break;
}else{
sum = 1+(setValues.get(i+1)-1);
}
}
else if(i == setValues.size()-1){
sum+= (setValues.get(i-1)+1)+n;
}
else{
sum+=(setValues.get(i-1)+1)+(setValues.get(i+1)-1);
}
}
System.out.println(sum);
}
}
```

}

```
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Solution {
public static void main(String... args) {
Scanner in = new Scanner(System.in);
String line1 = in.nextLine();
String[] line1Args = line1.split(" ");
int n = Integer.valueOf(line1Args[0]);
int m = Integer.valueOf(line1Args[1]);
ArrayList<Integer> setValues = new ArrayList<>();
for (int looper = 0; looper < m; looper++) {
int temp = in.nextInt();
setValues.add(temp);
Collections.sort(setValues);
int sum = 0;
for(int i = 0;i<setValues.size();i++){
if(i == 0){
if(setValues.size() == 1){
sum+=1+n;
break;
}else{
sum = 1+(setValues.get(i+1)-1);
}
}
else if(i == setValues.size()-1){
sum+= (setValues.get(i-1)+1)+n;
}
else{
sum+=(setValues.get(i-1)+1)+(setValues.get(i+1)-1);
}
}
System.out.println(sum);
}
}
}
```

No need to sort

result = 1 + N + 2 * sum(x[i]) - min(x[i]) - max(x[i])

Example:

N = 10

x = {2,5,7,9}

1 + N = 11

sum(x[i]) = 2 + 5 + 7 + 9 = 23

min = 2

max = 9

result = 11 + 2 * 23 - 2 - 9 = 46

I believe this can be done in constant time if M comes in sorted order. Please, brief about this clarification.

- Popeye May 29, 2019