fork download
copy 
  1. from math import ceil
  2.  
  3. N = 9
  4. arr = [i for i in range(N)]
  5. nodes = set((i, i + 1) for i in range(N - 1))
  6. print("Initial array:", arr)
  7. print("Initial edges:", nodes)
  8.  
  9. def func(start, end):
  10.     if end - start <= 3:  # If the segment is small enough, connect all pairs directly.
  11.         for i in range(start, end + 1):
  12.             for j in range(i + 1, end + 1):
  13.                 nodes.add((i, j))
  14.         return [start, end]
  15.  
  16.     n = end - start + 1
  17.     k = int(ceil(n**0.5))  # Calculate the number of segments based on sqrt(n)
  18.     size = ceil(n / k)  # Ensure the size covers all elements to the end.
  19.  
  20.     last_end = start - 1
  21.     results = []
  22.  
  23.     for i in range(k):
  24.         new_start = last_end + 1
  25.         new_end = new_start + size - 1
  26.         if new_end >= end:  # Prevent the segment from exceeding the bounds.
  27.             new_end = end
  28.         results.extend(func(new_start, new_end))
  29.         last_end = new_end
  30.         if new_end == end:
  31.             break
  32.  
  33.     # Connecting all results segments fully (could be optimized if needed)
  34.     for i in range(len(results)):
  35.         for j in range(i + 1, len(results)):
  36.             nodes.add((results[i], results[j]))
  37.  
  38.     return results
  39.  
  40. func(0, N - 1)
  41. print("Edges after processing:", nodes)
  42. print("No. of new edges added:", len(nodes) - (N - 1))
  43.  
Success #stdin #stdout 0.04s 9776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Initial array: [0, 1, 2, 3, 4, 5, 6, 7, 8]
Initial edges: {(0, 1), (1, 2), (3, 4), (2, 3), (6, 7), (4, 5), (5, 6), (7, 8)}
Edges after processing: {(3, 4), (0, 2), (0, 5), (0, 8), (2, 5), (2, 8), (6, 8), (4, 5), (5, 6), (3, 6), (0, 1), (1, 2), (6, 7), (3, 5), (3, 8), (5, 8), (0, 3), (0, 6), (2, 3), (2, 6), (7, 8)}
No. of new edges added: 13
https://ideone.com/uUkRn1
language:
Python 3 (python  3.9.5)
created:
55 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!