text: # Construct a distinct elements array with given size, sum and element upper bound in Python
  
  Suppose we have one size variable N, we also have one variable SUM this is the total sum of all elements available in the array and another variable K such that there is no element in array is greater than K, We have to find one orthogonal array where all elements in the array are distinct. If there is no solution return -1.
  
  So, if the input is like N = 4, SUM = 16 K = 9, then the output will be [1,2,4,9]
  
  To solve this, we will follow these steps −
  
  • minimum_sum := (N *(N + 1)) / 2
  
  • maximum_sum := (N * K) -(N *(N - 1)) / 2
  
  • if minimum_sum > SUM or maximum_sum < SUM, then
  
  • return -1
  
  • res := one array of size N + 1 and fill with 0 to N
  
  • sum := minimum_sum
  
  • i := N
  
  • while i >= 1, do
  
  • x := sum + (K - i)
  
  • if x < SUM, then
  
  • sum := sum +(K - i)
  
  • res[i] := K
  
  • K := K - 1
  
  • otherwise,
  
  • res[i] := res[i] +(SUM - sum)
  
  • sum := SUM
  
  • come out from the loop
  
  • i := i - 1
  
  • return res
  
  ## Example
  
  Let us see the following implementation to get better understanding −
  
  Live Demo
  
  def get_arr(N, SUM, K):
  minimum_sum = (N * (N + 1)) / 2
  maximum_sum = (N * K) - (N * (N - 1)) / 2
  if (minimum_sum > SUM or maximum_sum < SUM):
  return -1
  res = [i for i in range(N + 1)]
  sum = minimum_sum
  i = N
  while(i >= 1):
  x = sum + (K - i)
  if (x < SUM):
  sum = sum + (K - i)
  res[i] = K
  K -= 1
  else:
  res[i] += (SUM - sum)
  sum = SUM
  break
  i -= 1
  return res
  N = 4
  SUM = 16
  K = 9
  print(get_arr(N, SUM, K))
  
  ## Input
  
  4, 16, 9
  
  ## Output
  
  [0, 1, 2, 4.0, 9]
  
  Updated on: 27-Aug-2020
  
  108 Views