Рубрики

Минимум движется, чтобы достичь цели по бесконечной линии | Набор 2

Задана целевая позиция на бесконечной числовой линии (от -infinity до + infinity). Начиная с формы 0, вы должны достичь цели, двигаясь, как описано: На этом шаге вы можете сделать i шагов вперед или назад. Найдите минимальное количество ходов, необходимое для достижения цели.

Примеры :

Input : target = 3
Output : 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.

Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step  from 1 to -1.
On the third move we step from -1 to 2.

Подходить :
Идея аналогична обсуждаемой в O (n) подходе здесь .
Продолжайте добавлять сумму = 1 + 2 + .. + n> = цель. Решение этого квадратного уравнения дает наименьшее n, такое что sum> = target, т.е. решение для n в n (n + 1) / 2 — target> = 0 дает наименьшее n.
Если сумма == цель, ответ — n. Теперь следующий случай, когда сумма больше, чем цель. Найти разницу по тому, на сколько шагов индекс опережает цель, то есть сумму — цель.
Случай 1: разница даже тогда, ответ — n (потому что всегда будет движение, которое приведет к цели).
Случай 2: Разница нечетная, затем сделайте еще один шаг, то есть добавьте n + 1 к сумме и теперь снова возьмите разницу. Если разница даже в n + 1 — это ответ, иначе сделайте еще один ход, и это, безусловно, будет иметь значение, даже тогда ответ будет n + 2.

Пояснение: Разница странная. Цель нечетная или четная.
случай 1: n четно (1 + 2 + 3 +… + n), тогда добавление n + 1 делает четную разницу.
случай 2: n нечетно, тогда добавление n + 1 не имеет значения, поэтому сделайте еще один ход, то есть n + 2.

C ++

// код CPP для поиска минимальных ходов
// чтобы достичь цели
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска минимальных шагов
// чтобы достичь цели

int StepstoReachTarget(int target)

{

    // Обработка негативов

    // по симметрии

    target = abs(target);

  

    // Продолжайте двигаться, пока сумма

    // меньше, т.е. вычисляем n

    int n = ceil((-1.0 + sqrt(1 + 8.0 * target)) / 2);

    int sum = n * (n + 1) / 2;

  

    if (sum == target)

        return n;

  

    int d = sum - target;

  

    // случай 1: d четное

    if ((d & 1) == 0)

        return n;

  

    // d странно

    else

        return n + ((n & 1) ? 2 : 1);

}

  
// Код драйвера

int main()

{

    int target = 5;

    cout << StepstoReachTarget(target);

    return 0;

}

Джава

// Java-код для поиска минимальных ходов
// чтобы достичь цели

import java.lang.*;

  

class GFG {

      

    // Функция для поиска минимальных шагов

    // чтобы достичь цели

    static int StepstoReachTarget(int target)

    {

          

        // Обработка негативов

        // по симметрии

        target = Math.abs(target);

  

        // Продолжайте двигаться, пока сумма

        // меньше, т.е. вычисляем n

        int n = (int)Math.ceil((-1.0

              (int)Math.sqrt(1 + 8.0 *

                         target)) / 2);

                           

        int sum = n * (n + 1) / 2;

  

        if (sum == target)

            return n;

  

        int d = sum - target;

  

        // случай 1: d четное

        if ((d & 1) == 0)

            return n;

  

        // d странно

        else

            return n + ((n & 1) != 0 

                           ? 2 : 1);

    }

  

    // Код драйвера

    public static void main(String[] arg)

    {

        int target = 5;

        System.out.println(

             StepstoReachTarget(target));

    }

}

  
// Этот код предоставлен
// Смита Динеш Семвал

python3

# Python код для поиска минимума
# движется к цели

import math

  
# Функция поиска минимума
# шагов для достижения цели

def StepstoReachTarget(target) :

  

    # Обработка негативов

    # по симметрии

    target = abs(target)

  

    # Продолжайте двигаться, пока сумма

    # меньше, то есть вычисление n

    n = math.ceil((-1.0 + math.sqrt(1 +

                    8.0 * target)) / 2)

    sum = n * (n + 1) / 2

  

    if (sum == target) :

        return n

  

    d = sum - target

  

    # случай 1: d четное

    if ((d and 1) == 0) :

        return n

  

    # d странно

    else :

        if(n & 1) :

            return n + 2

        return n + 1

  
# Код драйвера

target = 5

print (StepstoReachTarget(target))

  
# Этот код предоставлен
# Маниш Шоу (manishshaw1)

C #

// C # код для поиска минимальных ходов
// чтобы достичь цели

using System;

  

class GFG {

      

    // Функция для поиска минимальных шагов

    // чтобы достичь цели

    static int StepstoReachTarget(int target)

    {

          

        // Обработка негативов

        // по симметрии

        target = Math.Abs(target);

  

        // Продолжайте двигаться, пока сумма

        // меньше, т.е. вычисляем n

        int n = (int)Math.Ceiling((-1.0 + 

                  (int)Math.Sqrt(1 + 8.0 *

                            target)) / 2);

                          

        int sum = n * (n + 1) / 2;

  

        if (sum == target)

            return n;

  

        int d = sum - target;

  

        // случай 1: d четное

        if ((d & 1) == 0)

            return n;

  

        // d странно

        else

            return n + ((n & 1) != 0

                        ? 2 : 1);

    }

  

    // Код драйвера

    public static void Main()

    {

        int target = 5;

        Console.Write(

            StepstoReachTarget(target));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP-код для поиска минимума
// движется к цели

  
// Функция для поиска минимума
// шаги для достижения цели

function StepstoReachTarget($target)

{

    // Обработка негативов $

    // по симметрии $

    $target = abs($target);

  

    // Продолжайте двигаться, пока сумма

    // меньше, т.е. вычисляем n

    $n = ceil((-1.0 + sqrt(1 + 

                8.0 * $target)) / 2);

    $sum = $n * ($n + 1) / 2;

  

    if ($sum == $target)

        return $n;

  

    $d = $sum - $target;

  

    // случай 1: d четное

    if (($d & 1) == 0)

        return n;

  

    // d странно

    else

        return $n + (($n & 1) ? 2 : 1);

}

  
// Код драйвера

$target = 5;

echo StepstoReachTarget($target);

  
// Этот код предоставлен anuj_67.
?>

Выход :

5

Рекомендуемые посты:

Минимум движется, чтобы достичь цели по бесконечной линии | Набор 2

0.00 (0%) 0 votes