Создайте массив, следуя условию, чтобы ровно M префиксов имели положительную сумму

Вам даны два целых числа N и M (M ≤ N), задача состоит в том, чтобы создать массив длины N, следуя приведенным ниже условиям.

• |А _я | = i , Формально A[i] будет либо -i , либо i .
• Там должно быть ровно M массивов префиксов, так что сумма каждого массива префиксов должна быть больше нуля.

Примечание. Если аранжировок несколько, выведите любую допустимую аранжировку.

Примеры:

Input: N = 3, M = 3
Output: 1 2 3
Explanation: There are Exactly 3 prefix arrays having sum greater than zero, Which are:
First prefix arr[] : {1}, Sum=1 
Second prefix arr[] 1: {1, 2}, Sum=1+2=3
Third prefix arr[] = {1, 2, 3}, Sum=1+2+3=6 
It can be verified that the output arrangement follows all the constraints provided in the problem statement.

Input: N = 4, M = 2 
Output: 1 -2 3 -4 
Explanation: There are exactly 2 prefix arrays having sum greater than zero, Which are {1} and {1, -2, 3} having sum 1 and 2 respectively. 

Подход: Задача может быть решена на основе следующего наблюдения.

Try to keep the odd positioned elements positive and even positioned elements as negative and maintain count of positive prefixes(If the required number of positive sum prefix is at most N/2). Otherwise, place positive elements till the required number of positive prefix becomes less than the remaining array size. 

Выполните следующие действия, чтобы решить проблему:

• Создайте тип StringBuilder и переменная счетчика типа int для расположения.
• Запустить цикл из я = от 1 до N и выполните следующие шаги внутри цикла:
  • Если M не больше N/2:
    • Если i нечетное и count < M, добавить i в ans и увеличить счетчик, иначе append -i .
• В противном случае сделайте следующее:
  • Если i нечетное и count < NM, добавьте -i в ответ и увеличьте счетчик, иначе добавьте i .
• Распечатать ответ .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(1)

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам