My friend Albi is a teacher. At the beginning of each lesson, her students form a line and enter the class one by one. As they enter, each student shakes her hand. Albi enters the students’ names in a list in the order in which they enter the classroom. After work, she analyzes the list to get a hint of the connections and relationships in the class.
Albi has a hunch that the ages of the students can tell her a lot. She has a list of the ages of her
students in the order they entered the classroom, and she wants to calculate the number of pairs of students such that their age difference is exactly
1, and the youngest student in the pair entered before the oldest. Please help my friend!
students = [2, 4, 3, 4, 6], the output should be
studentsAge(students) = 2.
There are two pairs of students Albi would be interested in:
students = [5, 4, 9, 10], the output should be
studentsAge(students) = 1.
The only interesting pair of students in
- [time limit] 4000ms (py)
- [input] array.integer students
The ages of the students in the order they entered the classroom.
1 ≤ students.length ≤ 105,
0 ≤ students[i] ≤ 105.
- [output] integer
An integer with the answer for Albi.
def studentsAge(s): m=*5**9 c=0 for x in s: c+=m[x-1] m[x]+=1 return c
There are multiple ways to solve this problem. Smarter way is to use a dictionary and store how many times each element is seen. However, to achieve the shortest solution (62 character in Python), we need a less efficient approach. Instead of a dictionary, create an array of size 10^5 and use this array to count each element.
For each element x in array, we need how many times x-1 is seen before that. So, for each element, we sum up this number and return it. The reason the array is initialized with length 5^9 is to decrease 1 character from 10^6.