Editorialist: Raj Shah
DIFFICULTY:
EASYMEDIUM
PREREQUISITES:
Basic Mathematics, Range Queries
PROBLEM LINK:
PROBLEM:

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.

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 
You have to find the number at a given index.
QUICK EXPLANATION:

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.

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.

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 Task1:
 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 Task2:
 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 Task3:
 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