  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

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

### SOLVING APPROACH:

#### BRUTE FORCE METHOD:

1. This is the simplest approach where we run two nested loops.
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(N2)

#### 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
#include

int main()
{
int n;
scanf("%d",&n);
int ages[n];
for(int i=0;i= 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
using namespace std;

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

cout<
```
```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= ageB) continue;
if (ageA < ageB) continue;
if (ageA < 100 && 100 < ageB) continue;
ans += countA * countB;
if (ageA == ageB) ans -= countA;
}
}

System.out.println(ans);
}
}
```
```# your code goes heren = int(input())
l = list(map(int,input().split()))
count = [0 for i in range(121)]

for i in l:
count[i] += 1

ans = 0

for ageA in range(121):

countA = count[ageA]
for ageB in range(121):
countB = count[ageB]
if ageA*0.5 + 7 >= ageB:
continue
if ageA < ageB:
continue
if ageA < 100 and 100 < ageB:
continue

ans += countA * countB
if ageA == ageB:
ans -= countA
print(ans)

```

Space Complexity: `O(A)`, the space used to store count

[forminator_quiz id="444"]

This article tried to discuss Hashing. Hope this blog helps you understand and solve the problem. To practice more problems on Hashing you can check out MYCODE | Competitive Programming.