CONCEPTS USED:
Hashing
DIFFICULTY LEVEL:
Medium
PROBLEM STATEMENT(
SIMPLIFIED)
:
Given
N
ages of students of a college and some conditions which determine whetherA
canFriend Request
B
or not. Determine the total no. ofFriend 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
requestsB
,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.
 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 only120
possible ages this means that there can be aMaximum
of120
pairs. Processing120
elements is much faster than processing20000
elements.For each pair
(ageA, countA)
and(ageB, countB)
, if the conditions are satisfied with respect to age, thencountA
*countB
pairs of people made friend requests.If
(ageA = ageB)
, then we over counted and we should havecountA
*(
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); }
#includeusing 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)
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.