{"id":418,"date":"2020-06-10T10:40:14","date_gmt":"2020-06-10T10:40:14","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=418"},"modified":"2022-03-28T23:59:59","modified_gmt":"2022-03-28T23:59:59","slug":"friends-ages","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/friends-ages\/","title":{"rendered":"Friends Ages"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Hashing<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given N<\/code> ages of students of a college and some conditions which determine whether A<\/code> can Friend Request<\/code> B<\/code> or not. Determine the total no. of Friend Requests<\/code> that can be made.<\/p>\n<\/blockquote>\n

Conditions<\/strong>:<\/p>\n

age[B] <= 0.5* age[A] + 7<\/code> <\/p>\n

age[B] > 100<\/code> && age[A] <100<\/code><\/p>\n

age[B] > age[A]<\/code><\/p>\n

NOTE<\/strong>:<\/p>\n

    \n
  1. \n

    if A<\/code> requests B<\/code>, B<\/code> does not necessarily request
    \nA<\/code>. <\/p>\n<\/li>\n

  2. \n

    The student will not friend request themselves.<\/p>\n<\/li>\n<\/ol>\n

    <\/strong><\/u><\/a><\/p>\n

    For Example :<\/h4>\n
    Input :  17 18 19\n\nOutput : 3\n\nExplanation : Friend requests that are made are 18 -> 17 , 19 -> 17 , 19 -> 18.<\/code><\/pre>\n
    SOLVING APPROACH:<\/h3>\n
    BRUTE FORCE METHOD:<\/h4>\n
    \n
      \n
    1. This is the simplest approach where we run two nested loops.<\/li>\n
    2. For each element,we run a loop and check for the conditions and accordingly increment the count<\/code>.<\/li>\n
    3. Time Complexity<\/code> of this solution will be O(N2<\/sup>)<\/li>\n<\/ol>\n<\/blockquote>\n
      EFFICIENT METHOD:<\/h4>\n
      \n
        \n
      1. \n
        The idea is to use Hashing<\/code>.<\/p>\n<\/li>\n
      2. \n
        Instead of processing all 20000<\/code> people, we can process pairs of (age, count)<\/code> representing how many people are there of that age.<\/p>\n<\/li>\n
      3. \n
        According to the Constraints<\/code>, since there are only 120<\/code> possible ages this means that  there can be a Maximum<\/code> of 120<\/code> pairs. Processing 120<\/code> elements is much faster than processing 20000<\/code> elements.<\/p>\n<\/li>\n
      4. \n
        For each pair (ageA, countA)<\/code> and (ageB, countB)<\/code>, if the conditions are satisfied with respect to age, then countA<\/code> * countB<\/code>
        \npairs of people made friend requests.<\/p>\n<\/li>\n
      5. \n
        If (ageA = ageB)<\/code>, then we over counted and we should have countA<\/code> * (<\/code>countA<\/code> -<\/code> 1)<\/code> pairs of people making friend requests
        \ninstead, as you cannot friend request yourself.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
        ILLUSTRATION:<\/h3>\n
        A[] = [17, 18, 19]\n\nStep 1 : Construct pairs of age and their count\n\n(17, 1) (18, 1) (19, 1)\n\nStep 2 : Pick a pair and check if it satisfies conditions with other pairs taken one by one. Similarly do it with all such pairs.\n\nIf Condition Satisfied between two ages :  \n  Check if there ages are equal : \n      if Yes, increment count by countA (countA - 1)\n      if No, increment count by countA * countB\n\nfor (17, 1) and (17, 1) => Yes (All conditions met)\n    also, ageA = ageB\n      count = count + countA *(countA - 1) = 0 + 1 *( 1 - 1) = 0\n\nfor (17, 1) and (18, 1) => No\n  17 cannot friend request 18 as (17 < 18)\n\nfor (17, 1) and (19, 1) => No\n  17 cannot friend request 19 as (17 < 19)\n\nfor (18, 1) and (17, 1) => Yes (All conditions met)\n  count = count + countA * countB = 0 + 1 * 1 = 1\n\nfor (18, 1) and (18, 1) => Yes (All conditions met)\n  also, ageA = ageB\n    count = count + countA *(countA - 1) = 1 +  1 *( 1 - 1) = 1 + 0 = 1\n\nfor (18, 1) and (19, 1) => No\n  18 cannot friend request 19 as (18 < 19)\n\nfor (19, 1) and (17, 1) => Yes (All conditions met)\n  also, ageA is not equal to ageB\n    count = count + countA * countB = 1 + 1 * 1 = 2\n\nfor (19, 1) and (18, 1) => Yes (All conditions met)\n  also, ageA is not equal to ageB\n    count = count + countA * countB = 2 + 1 * 1 = 3\n\nfor (19, 1) and (19, 1) => Yes (All conditions met)\n  also, ageA = ageB\n    count = count + countA *(countA - 1) = 3 +  1*(1 - 1) = 3 + 0 = 3\n\nTotal of 3 Friend Requests can be made between these people.<\/code><\/pre>\n
        SOLUTIONS:<\/h3>\n
        \t\t\t\t\t\t