Pasos necesarios para visitar M puntos en orden en un anillo circular de N puntos

Dado un número entero ‘n’, considere un anillo circular que contenga ‘n’ puntos numerados del ‘1’ al ‘n’ tal que pueda moverse de la siguiente manera:

1 -> 2 -> 3 -> ….. -> n -> 1 -> 2 -> 3 -> ……

Además, dada una array de números enteros (de tamaño ‘m’), la tarea es encontrar la cantidad de pasos necesarios para llegar a cada punto de la array en orden, comenzando en ‘1’.
Ejemplos: 

Input: n = 3, m = 3, arr[] = {2, 1, 2}
Output: 4
The sequence followed is 1->2->3->1->2

Input: n = 2, m = 1, arr[] = {2}
Output: 1
The sequence followed is 1->2

Enfoque: Denotemos la posición actual por cur y la siguiente posición por nxt . Esto nos da 2 casos: 

1. Si cur es más pequeño que nxt , puede moverse a él en pasos nxt – cur .
2. De lo contrario, primero debe llegar al punto n en n – pasos cur , y luego puede pasar a nxt en pasos cur .

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the steps required
int findSteps(int n, int m, int a[])
{
 
    // Start at 1
    int cur = 1;
 
    // Initialize steps
    int steps = 0;
    for (int i = 0; i < m; i++) {
 
        // If nxt is greater than cur
        if (a[i] >= cur)
            steps += (a[i] - cur);
        else
            steps += (n - cur + a[i]);
 
        // Now we are at a[i]
        cur = a[i];
    }
    return steps;
}
 
// Driver code
int main()
{
    int n = 3, m = 3;
    int a[] = { 2, 1, 2 };
    cout << findSteps(n, m, a);
}

// Java implementation of the approach
class GFG
{
     
// Function to count the steps required
static int findSteps(int n, int m,
                     int a[])
{
 
    // Start at 1
    int cur = 1;
 
    // Initialize steps
    int steps = 0;
    for (int i = 0; i < m; i++)
    {
 
        // If nxt is greater than cur
        if (a[i] >= cur)
            steps += (a[i] - cur);
        else
            steps += (n - cur + a[i]);
 
        // Now we are at a[i]
        cur = a[i];
    }
    return steps;
}
 
// Driver code
public static void main(String []args)
{
    int n = 3, m = 3;
    int a[] = { 2, 1, 2 };
    System.out.println(findSteps(n, m, a));
}
}
 
// This code is contributed by ihritik

// C# implementation of the approach
using System;
 
class GFG
{
// Function to count the
// steps required
static int findSteps(int n,
                     int m, int []a)
{
 
    // Start at 1
    int cur = 1;
 
    // Initialize steps
    int steps = 0;
    for (int i = 0; i < m; i++)
    {
 
        // If nxt is greater than cur
        if (a[i] >= cur)
            steps += (a[i] - cur);
        else
            steps += (n - cur + a[i]);
 
        // Now we are at a[i]
        cur = a[i];
    }
    return steps;
}
 
// Driver code
public static void Main()
{
    int n = 3, m = 3;
    int []a = { 2, 1, 2 };
    Console.WriteLine(findSteps(n, m, a));
}
}
 
// This code is contributed by ihritik

# Python3 implementation of the approach
 
# Function to count the steps required
def findSteps(n, m, a):
 
    # Start at 1
    cur = 1
 
    # Initialize steps
    steps = 0
    for i in range(0, m):
 
        # If nxt is greater than cur
        if (a[i] >= cur):
            steps += (a[i] - cur)
        else:
            steps += (n - cur + a[i])
 
        # Now we are at a[i]
        cur = a[i]
     
    return steps
 
# Driver code
n = 3
m = 3
a = [2, 1, 2 ]
print(findSteps(n, m, a))
 
# This code is contributed by ihritik

<?php
// PHP implementation of the approach
 
// Function to count the steps required
function findSteps($n, $m, $a)
{
 
    // Start at 1
    $cur = 1;
 
    // Initialize steps
    $steps = 0;
    for ($i = 0; $i < $m; $i++)
    {
 
        // If nxt is greater than cur
        if ($a[$i] >= $cur)
            $steps += ($a[$i] - $cur);
        else
            $steps += ($n - $cur + $a[$i]);
 
        // Now we are at a[i]
        $cur = $a[$i];
    }
    return $steps;
}
 
// Driver code
$n = 3;
$m = 3;
$a = array(2, 1, 2 );
echo findSteps($n, $m, $a);
 
// This code is contributed by ihritik
?>

<script>
 
// Javascript implementation of the approach
 
// Function to count the steps required
function findSteps(n, m, a)
{
 
    // Start at 1
    var cur = 1;
 
    // Initialize steps
    var steps = 0;
    for (var i = 0; i < m; i++) {
 
        // If nxt is greater than cur
        if (a[i] >= cur)
            steps += (a[i] - cur);
        else
            steps += (n - cur + a[i]);
 
        // Now we are at a[i]
        cur = a[i];
    }
    return steps;
}
 
// Driver code
var n = 3, m = 3;
var a = [ 2, 1, 2 ];
document.write( findSteps(n, m, a));
 
</script>

4

Complejidad de tiempo: O(M)

Espacio Auxiliar: O(1)