Friends Ages

Last Updated on March 28, 2022 by Ria Pathak

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:

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(N²)

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[121]={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)

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