# Sum of Four Numbers Less Than Target - Amazon Top Interview Questions

### Problem Statement :

```You are given four lists of integers A, B, C, D and an integer target.

Return the number of different unique indices i, j, k, l such that A[i] + B[j] + C[k] + D[l] ≤ target.

Constraints

a ≤ 1,000 where a is the length of A
b ≤ 1,000 where b is the length of B
c ≤ 1,000 where c is the length of C
d ≤ 1,000 where d is the length of D

Example 1

Input

A = [2, 3]

B = [5, 2]

C = 

D = [1, 2]

target = 6

Output

3

Explanation

We can pick the following combinations:

[2, 2, 0, 1]
[2, 2, 0, 2]
[3, 2, 0, 1]

Example 2

Input

A = [1, 1]

B = 

C = 

D = 

target = 1

Output

2```

### Solution :

```                        ```Solution in C++ :

int solve(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D, int target) {
vector<int> v1;
vector<int> v2;
int res = 0;
for (int i : A) {
for (int j : B) {
v1.push_back(i + j);
}
}

for (int i : C) {
for (int j : D) {
v2.push_back(i + j);
cout << (i + j) << endl;
}
}

sort(v2.begin(), v2.end());

for (int i : v1) {
int l = 0, r = v2.size() - 1;
int pos = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (v2[mid] + i <= target) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}

res += pos + 1;
}
return res;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
private int ans = 0;
public int solve(int[] A, int[] B, int[] C, int[] D, int target) {
int[] prefixsumArr = new int;
Map<Integer, Integer> map = new HashMap();
int idx = 0;
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < B.length; j++) {
int val = A[i] + B[j];
map.put(val, map.getOrDefault(val, 0) + 1);
}
}
for (int key : map.keySet()) {
prefixsumArr[key] = map.get(key);
}
for (int i = 1; i < prefixsumArr.length; i++)
prefixsumArr[i] = prefixsumArr[i] + prefixsumArr[i - 1];

for (int i = 0; i < C.length; i++) {
for (int j = 0; j < D.length; j++) {
int val = C[i] + D[j];
int remain = target - val;
if (remain >= 0)
ans += prefixsumArr[remain];
}
}
return ans;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, A, B, C, D, target):
ab = sorted(a + b for a in A for b in B)
return sum(bisect_right(ab, target - c - d) for c in C for d in D)```
```

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty