# Friends Ages

Hashing

Medium

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given `N` ages of students of a college and some conditions which determine whether `A` can `Friend Request` `B` or not. Determine the total no. of `Friend Requests` that can be made.

Conditions:

`age[B] <= 0.5* age[A] + 7`

`age[B] > 100` && `age[A] <100`

`age[B] > age[A]`

NOTE:

1. if `A` requests `B`, `B` does not necessarily request
`A`.

2. The student will not friend request themselves.

See original problem statement here

#### For Example :

``````Input :  17 18 19

Output : 3

Explanation : Friend requests that are made are 18 -> 17 , 19 -> 17 , 19 -> 18.``````

#### BRUTE FORCE METHOD:

1. This is the simplest approach where we run two nested loops i by referring online programming courses.

2. For each element,we run a loop and check for the conditions and accordingly increment the `count`.

3. `Time Complexity` of this solution will be `O(N^2)`.

#### EFFICIENT METHOD:

1. The idea is to use `Hashing`.

2. Instead of processing all `20000` people, we can process pairs of `(age, count)` representing how many people are there of that age.

3. According to the `Constraints`, since there are only `120` possible ages this means that there can be a `Maximum` of `120` pairs. Processing `120` elements is much faster than processing `20000` elements.

4. For each pair `(ageA, countA)` and `(ageB, countB)`, if the conditions are satisfied with respect to age, then `countA` * `countB`
pairs of people made friend requests.

5. If `(ageA = ageB)`, then we over counted and we should have `countA` * `(``countA` `-` 1`)` pairs of people making friend requests
instead, as you cannot friend request yourself.

#### ILLUSTRATION:

``````A[] = [17, 18, 19]

Step 1 : Construct pairs of age and their count

(17, 1) (18, 1) (19, 1)

Step 2 : Pick a pair and check if it satisfies conditions with other pairs taken one by one. Similarly do it with all such pairs.

If Condition Satisfied between two ages :
Check if there ages are equal :
if Yes, increment count by countA (countA - 1)
if No, increment count by countA * countB

for (17, 1) and (17, 1) => Yes (All conditions met)
also, ageA = ageB
count = count + countA *(countA - 1) = 0 + 1 *( 1 - 1) = 0

for (17, 1) and (18, 1) => No
17 cannot friend request 18 as (17 < 18)

for (17, 1) and (19, 1) => No
17 cannot friend request 19 as (17 < 19)

for (18, 1) and (17, 1) => Yes (All conditions met)
count = count + countA * countB = 0 + 1 * 1 = 1

for (18, 1) and (18, 1) => Yes (All conditions met)
also, ageA = ageB
count = count + countA *(countA - 1) = 1 +  1 *( 1 - 1) = 1 + 0 = 1

for (18, 1) and (19, 1) => No
18 cannot friend request 19 as (18 < 19)

for (19, 1) and (17, 1) => Yes (All conditions met)
also, ageA is not equal to ageB
count = count + countA * countB = 1 + 1 * 1 = 2

for (19, 1) and (18, 1) => Yes (All conditions met)
also, ageA is not equal to ageB
count = count + countA * countB = 2 + 1 * 1 = 3

for (19, 1) and (19, 1) => Yes (All conditions met)
also, ageA = ageB
count = count + countA *(countA - 1) = 3 +  1*(1 - 1) = 3 + 0 = 3

Total of 3 Friend Requests can be made between these people.``````

#### SOLUTIONS:

```#include <stdio.h>

int main()
{
int n;
scanf("%d",&n);
int ages[n];
for(int i=0;i<n;i++)
scanf("%d",&ages[i]);
int count={0};
for (int i=0;i<n;i++)
count[ages[i]]++;
int ans = 0;
for (int ageA = 0; ageA <= 120; ageA++)
{
int countA = count[ageA];
for (int ageB = 0; ageB <= 120; ageB++)
{
int countB = count[ageB];
if (ageA * 0.5 + 7 >= ageB) continue;
if (ageA < ageB) continue;
if (ageA < 100 && 100 < ageB) continue;
ans += countA * countB;
if (ageA == ageB) ans -= countA;
}
}

printf("%d\n",ans);
}

```
```#include <iostream>
using namespace std;

int main()
{
int n;
cin>>n;
int ages[n];
for(int i=0;i<n;i++)
cin>>ages[i];
int count={0};
for (int i=0;i<n;i++)
count[ages[i]]++;
int ans = 0;
for (int ageA = 0; ageA <= 120; ageA++)
{
int countA = count[ageA];
for (int ageB = 0; ageB <= 120; ageB++)
{
int countB = count[ageB];
if (ageA * 0.5 + 7 >= ageB) continue;
if (ageA < ageB) continue;
if (ageA < 100 && 100 < ageB) continue;
ans += countA * countB;
if (ageA == ageB) ans -= countA;
}
}

cout<<ans;
}

```
```import java.util.*;
import java.io.*;

public class Main {
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int ages[] = new int[n];
for(int i=0;i<n;i++)
ages[i] = sc.nextInt();
int count[] = new int;
for (int i=0;i<n;i++)
count[ages[i]]++;
int ans = 0;
for (int ageA = 0; ageA <= 120; ageA++)
{
int countA = count[ageA];
for (int ageB = 0; ageB <= 120; ageB++)
{
int countB = count[ageB];
if (ageA * 0.5 + 7 >= ageB) continue;
if (ageA < ageB) continue;
if (ageA < 100 && 100 < ageB) continue;
ans += countA * countB;
if (ageA == ageB) ans -= countA;
}
}

System.out.println(ans);
}
}

```