Минимальное количество переворачиваемых страниц для перехода на желаемую страницу

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

Для книги из N страниц задача состоит в том, чтобы вычислить минимальное количество переворотов, чтобы перейти к желаемой странице K. Мы можем начать перелистывать страницы с лицевой стороны книги (т.е. со страницы 1) или с обратной стороны книги (то есть страницы с номером N). Каждая страница имеет две стороны, переднюю и заднюю, за исключением первой страницы, которая имеет только обратную сторону, и последней страницы, которая может иметь только обратную сторону, в зависимости от количества страниц в книге.
Примеры :

 Ввод: N = 6 и K = 2.
Выход: 1.
Спереди (1) -> (2, 3), страница перевернута = 1.
Сзади: (6) -> (4, 5) -> (2,3), страница перевернута = 2.
Итак, минимальное количество перевернутых страниц = 1.

Ввод: N = 5 и K = 4.
Выход: 1.
Спереди (1) -> (2, 3) -> (4,5), страница перевернута = 2.
С обратной стороны, (4, 5) страница перевернута = 1. С обратной стороны это 2-я страница, так как 4 находится с другой стороны страницы 5, а страница 5 - первая с обратной стороны.
Итак, минимальное количество перевернутых страниц = 1.

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

The idea is to calculate distance of the desired page from the front and from the back of the book, minimum of this is the required answer. 
Now, Consider there is page 0, which is front of the first page. And if N is even, consider there is page N+1, which is back of the last page, so total number of pages are N+1. 
To calculate the distance, 
1. If K is even, front distance = (K – 0)/2 and back distance = (N – 1 – K)/2. 
2. If K is odd, front distance = (K – 1)/2 and back distance = (N – K)/2. 
 

C++

// C++ program to find minimum number of page
// turns to reach a page
#include<bits/stdc++.h>
using namespace std;
 
int minTurn(int n, int k)
{
    // Considering back of last page.
    if (n%2 == 0)
        n++;
 
    // Calculating Distance from front and
    // back of the book and return the min
    return min((k + 1)/2, (n - k + 1)/2);
}
 
// Driven Program
int main()
{
    int n = 6, k = 2;
    cout << minTurn(n,k) << endl;
    return 0;
}
 
// This code is modified by naveenkonda

Java

// Java program to find minimum
// number of page turns to
// reach a page
import java.io.*;
 
public class GFG
{
 
// Function to calculate
// minimum number of page
// turns required
static int minTurn(int n, int k)
{
     
    // Considering back of last page.
    if (n % 2 == 0)
        n++;
 
    // Calculating Distance from front and
    // back of the book and return the min
    Math.min((k + 1) / 2, (n - k + 1) / 2);
}
 
    // Driver Code
    static public void main (String[] args)
    {
        int n = 6, k = 2;
        System.out.println(minTurn(n, k));
    }
}
 
// This code is contributed by vt_m.

Python3

# Python3 program to find minimum number
# of page turns to reach a page
def minTurn(n, k):
     
    # Considering back of last page.
    if (n % 2 == 0):
        n += 1
 
    // Calculating Distance from front and
    // back of the book and return the min
    return min((k + 1) / 2, (n - k + 1) / 2)
 
# Driver Code
if __name__ == "__main__":
    n = 6
    k = 2
    print(int(minTurn(n, k)))
     
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to find minimum
// number of page turns to
// reach a page
using System;
 
public class GFG
{
 
// Function to calculate
// minimum number of page
// turns required
static int minTurn(int n, int k)
{
     
    // Considering back of last page.
    if (n % 2 == 0)
        n++;                       
 
    // Calculating Distance from front and
    // back of the book and return the min
    return Math.Min((k + 1) / 2,
                    (n - k + 1) / 2);
}
 
    // Driver Code
    static public void Main (String[] args)
    {
        int n = 6, k = 2;
        Console.WriteLine(minTurn(n, k));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to find minimum number
// of page turns to reach a page
 
function minTurn($n, $k)
{
    // Considering back of last page.
    if ($n % 2 == 0)
        $n++;
 
    // Calculating Distance from front and
    // back of the book and return the min
    return min(($k + 1) / 2,
               ($n - $k + 1) / 2);
}
 
// Driver Code
$n = 6; $k = 2;
echo minTurn($n, $k) ;
 
// This code is contributed by nitin mittal.
?>

Javascript

<script>
 
// Javascript program to find minimum
// number of page turns to
// reach a page
 
// Function to calculate
// minimum number of page
// turns required
function minTurn(n, k)
{
       
    // Considering back of last page.
    if (n % 2 == 0)
        n++;
   
    // Calculating Distance from front and
    // back of the book and return the min
    let x = Math.min((k + 1) / 2, (n - k + 1) / 2);
    return Math.floor(x);
}
      
// Driver code   
 
        let n = 6, k = 2;
        document.write(minTurn(n, k));
                   
</script>

Выход :

 1

Сложность времени: O (1)
Автор статьи - Анудж Чаухан (anuj0503). Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

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

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