Find out which group the number belongs to?
I was working on a coding problem and as part of it I got this problem:
We are given a number x, and we square it, so that the number becomes x ^ 2. Now we have numbers from 1 to x ^ 2, for example: if number = 4; then 4 ^ 2 = 16
1 ----->1
2 3 ----->2
4 5 6 ----->3
7 8 9 10 ----->4
11 12 13 ----->5
14 15 ----->6
16 ----->7
Now I am assigned the number k, and I need to tell which group it belongs to. Here 8 belongs to the 4th group.
What I thought starts at 1 and keep the count initialized to 1 and check if 1 <8? if so, add 2 to 1 (the previous amount), increase the number to 2 and check if 3 or 8? if yes, then add 3 to 3 (the previous amount), increase the count to 3 and check if 6 or 8, if yes, then add 4-6, increase the amount to 4 and check, 10 or 9? if not, then exit. So the group is not. is ie 4.
But is there any quicker method than my approach?
EDIT 1: I forgot to mention that in my ego, when the counter reaches the specified number, which is 4 in the previous example, I shouldn't add 5, but 3.for example:
If the number to search is 14, then
1<14 yes then add 2
3<14 yes then add 3
6<14 yes then add 4
10<14 yes then add **3** ---->here I need to add 3 instead of 5
13<14 yes then add **2** ---->here I need to add 2 instead of 6
15<14 No so output count.
it is possible to add 3 instead of 5 using an if condition, but is there any method where the added value is automatically incremented and then decremented based on the value of x (see example above to know what x refers to)
source to share
The top half of the rectangle is a triangle:
1 ----->1
2 3 ----->2
4 5 6 ----->3
7 8 9 10 ----->4
and the numbers on the right (1, 3, 6, 10) are called triangular numbers . An inverse formula (under the heading "Triangular Roots and Tests for Triangular Numbers") can be used for your problem:
def group(x, number):
if number <= x^2 / 2 :
return ceiling( (sqrt(8*number+1) - 1) / 2 )
else:
return 2*x - group(x, x^2+1-number)
source to share
In the first half, the group i
ends with a number i*(i+1)/2
. So let's say you are assigned a number n
c n <= x^2/2
, you need to find the smallest i
c i*(i+1)/2 <= n
.
Solution i*i+i-2n = 0
for i
gives: ((sqrt(1+8n)-1/2)
For example. n = 8
:i = ceil((sqrt(65)-1)/2) = 4
Of course, the case is a n > x^2/2
little more complicated.
source to share
First, assume for simplicity that x <= n ^ 2/2 and x belongs to the group t . Then:
t*(t-1)/2 < x <= t*(t+1)/2
Hence, we obtain two quadratic inequalities:
t^2 - t - 2x < 0
t^2 + t - 2x >= 0
Here D=1+8x
, and since t> 0, their general solution will be
t ∈ [ (-1-sqrt(D))/2; (1+sqrt(D))/2 )
Now remember that t is an integer (and is unique by definition), so we get the solution formula:
t = floor( 1+sqrt(D))/2 )
This was the solution for the case x <= n ^ 2/2 . Otherwise, we can solve this by running:
- x: = n ^ 2 - x + 1
- find t as described above
- t: = n - t + 1
Hope it helps.
source to share
The numbers on the right-hand diagonal are the so-called "triangular numbers", they have a formula n(n+1)/2
.
The numbers in the lower right diagonal are 16 minus the triangular number and have the formula x^2 - (2*x-n-1)(2*x-n)/2
.
So for k
and x
you are looking for the smallest n
, so the formula is greater than or equal k
, choosing which formula matches whether k
greater or less than x
th is the number of the triangle x(x+1)/2
(in this case 10). Since both functions are monotonic (always increasing), you can do this by solving the quadratic equation for n
(using the quadratic formula) in floating point and then rounding to the next integer (called the "ceiling").
To account for floating point imprecisions without much complication, you should check the result using integer arithmetic. It is possible that the floating point calculation will slightly exceed or miss the correct result and round to the wrong integer value. For small numbers, it won't be more than 1x, so the code to detect and fix is just simple, just compare k
with the value you get by putting the result n
in the formula and the values for n
on both sides.
source to share
First, you need to notice that the row xth
is exactly the middle row and has x elements in it. So what are the elements in this particular line - they are from [x(x+1)/2-x, x(x+1)/2]
. Thus, the algorithm looks like this:
- Check if the number to be searched is in the middle string less than or greater than this.
- If you type x on the middle line.
- If less than the middle line, then you need to notice that all lines end with triangular numbers. You can use a formula
ceil((sqrt(8x+1)-1)/2)
to get the exact string. -
If the number is larger than the middle row, then what you can do is think about the bottom triangle:
6 5 4
3 2
1
That is, all numbers are equal x^2+1-that number
. So now you will be looking x^2+1-number to be searched
in the bottom triangle with the most indicated formula. This gives the line number in inverted form. Let this number be k
. Then the meaning is in the correct form x-1+k+1
. Finally add x
to the value to move the answer to the bottom triangle. Hence, the answer becomes 2x+k
.
This is an O (1) solution to the problem.
source to share