CODEWITHSUNDEEP
pythonalgorithmmath
John
John

Reputation: 27

Line arrangement problem. (Could someone propose a more time efficient solution?)

Positive integers starting from 1 are arranged in lines. The i-th line has i numbers in it. For example, these would be the first four lines:

1 | 2, 3 | 4, 5, 6 |7, 8, 9, 10

Write a function that takes the argument "L" and returns the L-th line of this arrangement.

This was my approach:

def find_line(l):
    array = []
    x = 1
    for i in range(1, l + 1):
        while len(array) != I:
            array.append(x)
            x += 1 
            if i == l:
                return array
            else:
                array = []

Upvotes: 3

Views: 97

Answers (3)

Hacke
Hacke

Reputation: 225

So okay,I want show the mathematics behind it. Lets calculate the expression for last term for a line number n.

1 |   2  |    3    |      4     | .....line numbers
--+------+---------+------------+------
1 | 2, 3 | 4, 5, 6 | 7, 8, 9, 10| .....values

for n=1 (i.e. line number 1) , last=1 so last(1) = 1.
Now lets say last(n) denotes the last value in line n, then:-
last(n) = last(n-1) + n
for example, for 4th line, n=4, we have
last(4) = last(3) + 4 = 6 + 4 Thus , unfolding the recurrence, we have:-

last(n) = last(n-1) + n
        = (last(n-2) + n-1) + n
        = last(1) + 2 + 3 + ....+ n-1 + n
        = 1 + 2 + 3 + ....+ n-1 + n
        = n*(n+1)/2

Thus, 

last(n) = n*(n+1)/2

Since there are n values in nth line, so we can get start for nth line as:-

start(n) = last(n) - n + 1
OR
start(n) = n*(n-1)/2 + 1

Alternately, you can also get start(n) as:-

start(n) = start(n-1) + n-1
         = start(n-2) + n-2 + n-1
         = start(1) + 1 + 2 + 3 + ....+ n-2 + n-1
         = 1 + (1 + 2 + 3 + ... + n-2 + n-1)
         = 1 + (n-1)*n/2
start(n) = n*(n-1)/2 + 1

Rest you can run a loop

loop from i=0 to i=n-1 :
     print( start(n) + i )

Upvotes: 2

Mark
Mark

Reputation: 92460

You don't need the loops. You can directly calculate he first number in the group by taking the sum of the series with:

start =  1 + (n * (n + 1)) // 2

If you want n to start at 1 rather than 0 you need to subtract from n.

def group(n):
    n -= 1
    start =  1 + (n * (n + 1)) // 2
    return list(range(start, start + n +1))

# try it on first 10 numbers: 
for i in range(1, 10):
    print(group(i))

This will print:

[1]
[2, 3]
[4, 5, 6]
[7, 8, 9, 10]
[11, 12, 13, 14, 15]
[16, 17, 18, 19, 20, 21]
[22, 23, 24, 25, 26, 27, 28]
[29, 30, 31, 32, 33, 34, 35, 36]
[37, 38, 39, 40, 41, 42, 43, 44, 45]

You can use join or similar if you need strings.

Upvotes: 5

Muhammad Usman
Muhammad Usman

Reputation: 29

def find_line(l):
  starting_num = 1
  res = []
  for count in range (l):
   starting_num += count

   res = list(range(starting_num, starting_num+l))

  return res

Testing the function for l=5:

print(find_line(5))
[11, 12, 13, 14, 15]

Upvotes: 1

Related Questions