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 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[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);
  }
}



Space Complexity: O(A), the space used to store count
Previous post Substring Start End Same
Next post Arithmetic Progression

Leave a Reply

Your email address will not be published. Required fields are marked *