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

×

MOALP - Editorial

PROBLEM LINK:

Practice

Contest

Author: Bhushan Khanale

Tester: D Teja Vardhan Reddy

Editorialist: Bhushan Khanale

DIFFICULTY:

EASY

PREREQUISITES:

Prefix array, hexadecimal number system.

PROBLEM:

The problem asks you ti find number of alphabets you can get through hexadecimal numbers in a given range $[L, R]$.

QUICK EXPLANATION:

The solution to the problem is very simple if you know about hexadecimal number systems. You can read about it here.

Then convert all numbers in the range to hexadecimal numbers and count the number of alphabets you get. Use prefix array to answer all testcases.

EXPLANATION:

First to convert decimal number into hexadecimal number you need to divide the number by $16$ (since this is base 16), and keep recording the remainder. Here as we are only concerned about the alphabets, we need to count the remainders which are $\geq 10$. This is because in hexadecimal number system the alphabets represent the numbers in the range $[10, 15]$. Hence the decimal numbers in that range will be represented by hexadecimal numbers $[A, F]$.

Since there are mutiple testcases, we only need to calculate this once and use prefix array which would keep count of total alphabets at every index. Then we can process each query with $O(1)$.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

Tester's solution can be found here.

This question is marked "community wiki".

asked 06 Feb, 16:43

bhushan_'s gravatar image

5★bhushan_
1027
accept rate: 9%

edited 07 Feb, 20:10

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,678
×22
×10

question asked: 06 Feb, 16:43

question was seen: 135 times

last updated: 07 Feb, 20:10