You are not logged in. Please login at www.codechef.com to post your questions!

×

GEEK03 - Editorial

Problem Link

Practice

Contest

Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

Difficulty

CAKEWALK

Prerequisites

Looping Techniques, Sorting Algorithms

Problem

Find the number of students remaining in the class if their name is recorded everytime they enter or leave the room.

Explanation

It is easy to see that at the end of the class only those students remain in the class who name was written an odd number of times.

To check the above condition, we can do a brute force by finding the number of times each name occurs and if it occurs an odd number of times, update the answer by $1$. To compare 2 names, we can simply iterate over them character by character and also check it their lengths are same or not.

One other efficient way is to sort all the student names. Then, same names occur as a subarray, so counting the frequency will be linear in this case as compared to quadratic in the previous case.

Time Complexity

$O(X * \log{X})$, per test case, where $|X|$ = Sum of lengths of all strings.

or $O(N * N * |S|)$, per test case, where $|S|$ = Maximum length of any string in the test case.

Space Complexity

$O(X)$, where $|X|$ = Sum of lengths of all strings.

Solution Links

Setter's solution

Setter's solution - 2

asked 20 Nov '17, 22:01

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

edited 26 Nov '17, 16:35

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,688
×801
×593
×4

question asked: 20 Nov '17, 22:01

question was seen: 305 times

last updated: 26 Nov '17, 16:35