#### CONCEPTS USED:

Hashing

#### DIFFICULTY LEVEL:

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:

if

`A`

requests`B`

,`B`

does not necessarily request

`A`

.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.
```

#### SOLVING APPROACH:

#### BRUTE FORCE METHOD:

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

For each element,we run a loop and check for the conditions and accordingly increment the

`count`

.

`Time Complexity`

of this solution will be`O(N^2)`

.

#### EFFICIENT METHOD:

The idea is to use

`Hashing`

.Instead of processing all

`20000`

people, we can process pairs of`(age, count)`

representing how many people are there of that age.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.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.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[121]={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[121]={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[121]; 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); } }