ZIO05003 - Editorial

editorial
, , , , , ,
1

Editorialist: Raj Shah

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Basic Mathematics, Range Queries

PROBLEM LINK:

ZIO2005 Problem 3

PROBLEM:

  1. There is a unique sequence of positive numbers that starts with the number 1 in the first position and has the following properties.

    • Each value in the sequence is greater than or equal to every value that appears earlier in the sequence.
    • If the value at position k in the sequence is m, then the number k appears exactly m times in the sequence.

  2. The first few numbers in this sequence are

    Position 1 2 3 4 5 6 7 8 9 10 11 12
    Sequence value 1 2 2 3 3 4 4 4 5 5 5 6

  3. You have to find the number at a given index.

QUICK EXPLANATION:

  1. You have to store a table containing the frequency of numbers, range of numbers, the number of indices that frequency covers, and total indices covered until that frequency.

  2. Steps to construct the table:

    • Write down the frequency in increasing order.
    • The size of the range of that frequency will be the frequency of the frequency as a number.
    • The start of the range will be the end of the previous range +1.
    • Range End = Range Start + Size - 1
    • Total numbers covered by that frequency = Size * Frequency
    • Indices covered = Indices covered till previous frequency + numbers covered by this frequency
    • The base row will be filled by all 1’s.

  3. Following is the table.

Frequency Range Start Range End Total Numbers Indices Covered
1 1 1 1 1
2 2 3 4 5
3 4 5 6 11
4 6 8 12 23
5 9 11 15 38
6 12 15 24 62
7 16 19 28 90
8 20 23 32 122
9 24 28 45 167
10 29 33 50 217
11 34 38 55 272
12 39 44 72 344
13 45 50 78 422
14 51 56 84 506
15 57 62 90 596
16 63 69 112 708
17 70 76 119 827
18 77 83 126 953
19 84 90 133 1086
20 91 98 160 1246

SOLUTIONS:

  • Solution to Task-1:

    • Position = 411
    • 411 lies at the frequency of 13.
    • Now (Indices Covered till 13 - Indices Covered till 12) are evenly distributed.
    • That’s why the floor(411 - Indices covered till 12) divided by 13 will give us the exact distance from 13’s range start for number at 411.
    • 411 - 344 = 67
    • [67/13] = 5
    • Answer = 45 + 5 = 50

  • Solution to Task-2:

    • Position = 1000
    • 1000 lies at the frequency of 19.
    • Now (Indices Covered till 19 - Indices Covered till 18) are evenly distributed.
    • That’s why the floor(1000 - Indices covered till 18) divided by 19 will give us the exact distance from 19’s range start for number at 1000.
    • 1000 - 953 = 47
    • [47/19] = 2
    • Answer = 84 + 2 = 86

  • Solution to Task-3:

    • Position = 1245
    • 1245 lies at the frequency of 20.
    • Now (Indices Covered till 20 - Indices Covered till 19) are evenly distributed.
    • That’s why the floor(1245 - Indices covered till 19) divided by 20 will give us the exact distance from 20’s range start for number at 1245.
    • 1245 - 1086 = 159
    • [159/20] = 7
    • Answer = 91 + 7 = 98