Editorialist: Raj Shah
DIFFICULTY:
EASY-MEDIUM
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 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