Минимальные шаги, в которых N может быть получено путем сложения или вычитания на каждом шаге

Опубликовано: 16 Января, 2022

Для данного N выведите последовательность из минимального количества шагов, в которой N может быть получено, начиная с 0, путем сложения или вычитания номера шага.
Примечание : на каждом шаге мы можем прибавлять или вычитать число, равное номеру шага, из текущей позиции. Например, на шаге 1 мы можем добавить 1 или -1. Аналогично на шаге 2 мы добавляем 2 или -2 и так далее.
На диаграмме ниже показаны все возможные положения, которые могут быть достигнуты от 0 за 3 шага, выполнив указанные операции.

Примеры :

 Ввод: n = -4
Выход: Минимальное количество шагов: 3
        Последовательность шагов: 1-2-3
Пояснение : 
Шаг 1: На шаге 1 мы добавляем 1, чтобы перейти от 0 к 1.
Шаг 2: На шаге 2 мы добавляем (-2), чтобы перейти от 1 к -1.
Шаг 3: На шаге 3 мы добавляем (-3), чтобы перейти от -1 к -4.

Ввод: n = 11
Выход: минимальное количество шагов = 4. 
        Последовательность шагов: 1-2 3 4 5

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: подход к решению вышеуказанной проблемы заключается в том, чтобы отметить номера шагов, на которых мы должны вычесть или сложить, если N положительно или отрицательно соответственно. Если N положительно, добавляйте числа на каждом шаге, пока сумма не превысит N. Как только сумма превысит N, проверьте, является ли сумма-N четной или нет. Если сумма-N четная, то на шаге номер (сумма-N) / 2 должно выполняться вычитание. Если сумма-N нечетное число, проверьте, был ли последний шаг, на котором сумма превышала N, был четным или нечетным. Если это было странно, выполните еще один шаг, иначе выполните два шага. Если сумма = N на любом шаге, то добавление или вычитание на каждом шаге даст ответ.
Пусть N = 11, тогда 1 + 2 + 3 + 4 + 5 = 15 больше 11. Вычтите 15-11, чтобы получить 4, что эквивалентно выполнению вычитания на шаге 2. Следовательно, последовательность шагов равна 1-2 3 4 5
Пусть N = 12, тогда 1 + 2 + 3 + 4 + 5 = 15 больше 11. Вычтите 15-12, чтобы получить 3, что не может быть выполнено ни на одном шаге. Итак, добавьте еще два шага, один - 6- й и 7- й . Цель состоит в том, чтобы сделать сумму-N четной, поэтому выполните сложение на 6-м шаге и вычитание на 7-м шаге, в результате чего вычитается 1 из суммы. Теперь сумма-N четна, 14-12 = 2, что эквивалентно выполнению вычитания на шаге 1. Следовательно, последовательность шагов равна -1 2 3 4 5 6-7.
Пусть N = 20, тогда 1 + 2 + 3 + 4 + 5 + 6 больше 20. Вычтите 21-20, чтобы получить 1, поэтому прибавьте 7 к 21, чтобы получить 28. Выполнение сложения на следующем шаге будет выглядеть как (sum-n) странно. sum-N дает 8, что эквивалентно выполнению вычитания на шаге 4. Следовательно, последовательность шагов равна 1 2 3 -4 5 6 7.
Ниже приведена иллюстрация описанного выше подхода:

Сложность времени: O (sqrt (N))
Вспомогательное пространство: O (sqrt (N))
Примечание: sum = i * (i + 1) / 2 эквивалентно или больше N, что дает i как sqrt (N).

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.