Encuentre una permutación tal que el número de índices para los cuales mcd(p[i], i) > 1 sea exactamente K

Dados dos números enteros N y K , la tarea es encontrar una permutación de números enteros del rango [1, N] tal que el número de índices (indexación basada en 1) donde mcd(p[i], i) > 1 sea exactamente k _ Imprime -1 si tal permutación no es posible.

Ejemplos: 

Entrada: N = 4, K = 3 
Salida: 1 2 3 4 
mcd(1, 1) = 1 
mcd(2, 2) = 2 
mcd(3, 3) = 3 
mcd(4, 4) = 4 
Por lo tanto, hay son exactamente 3 índices donde mcd(p[i], i) > 1

Entrada: N = 1, K = 1 
Salida: -1

Enfoque: Aquí se pueden hacer un par de observaciones:  

1. mcd(i, i + 1) = 1
2. mcd(1, i) = 1
3. mcd(i, i) = i

Dado que mcd de 1 con cualquier otro número siempre será uno, K casi puede ser N – 1 . Considere la permutación donde p[i] = i , El número de índices donde mcd(p[i], i) > 1 será N – 1 . Tenga en cuenta que el intercambio de 2 elementos continuos (excepto 1) reducirá la cuenta de dichos índices en exactamente 2. Y el intercambio con 1 reducirá la cuenta en exactamente 1. 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 print the required permutation
void printPermutation(int n, int k)
{
 
    // Not possible
    if (k >= n || (n % 2 == 0 && k == 0)) {
        cout << -1;
        return;
    }
    int per[n + 1], i;
 
    // Initial permutation
    for (i = 1; i <= n; i++)
        per[i] = i;
 
    // Indices for which gcd(p[i], i) > 1
    // in the initial permutation
    int cnt = n - 1;
    i = 2;
    while (i < n) {
 
        // Reduce the count by 2
        if (cnt - 1 > k) {
            swap(per[i], per[i + 1]);
            cnt -= 2;
        }
 
        // Reduce the count by 1
        else if (cnt - 1 == k) {
            swap(per[1], per[i]);
            cnt--;
        }
        else
            break;
        i += 2;
    }
 
    // Print the permutation
    for (i = 1; i <= n; i++)
        cout << per[i] << " ";
}
 
// Driver code
int main()
{
    int n = 4, k = 3;
    printPermutation(n, k);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to print the required permutation
    static void printPermutation(int n, int k)
    {
 
        // Not possible
        if (k >= n || (n % 2 == 0 && k == 0))
        {
            System.out.print(-1);
            return;
        }
        int per[] = new int[n + 1], i;
 
        // Initial permutation
        for (i = 1; i <= n; i++)
        {
            per[i] = i;
        }
 
        // Indices for which gcd(p[i], i) > 1
        // in the initial permutation
        int cnt = n - 1;
        i = 2;
        while (i < n)
        {
 
            // Reduce the count by 2
            if (cnt - 1 > k)
            {
                swap(per, i, i + 1);
                cnt -= 2;
            }
             
            // Reduce the count by 1
            else if (cnt - 1 == k)
            {
                swap(per, 1, i);
                cnt--;
            }
            else
            {
                break;
            }
            i += 2;
        }
 
        // Print the permutation
        for (i = 1; i <= n; i++)
        {
            System.out.print(per[i] + " ");
        }
    }
 
    static int[] swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }
     
    // Driver code
    public static void main(String[] args)
    {
        int n = 4, k = 3;
        printPermutation(n, k);
    }
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 implementation of the approach
 
# Function to print the required permutation
def printPermutation(n, k):
 
    # Not possible
    if (k >= n or (n % 2 == 0 and
                   k == 0)):
        print(-1);
        return;
    per = [0] * (n + 1);
 
    # Initial permutation
    for i in range(1, n + 1):
        per[i] = i;
 
    # Indices for which gcd(p[i], i) > 1
    # in the initial permutation
    cnt = n - 1;
    i = 2;
    while (i < n):
 
        # Reduce the count by 2
        if (cnt - 1 > k):
             
            t = per[i];
            per[i] = per[i + 1];
            per[i + 1] = t;
             
            # swap(per[i], per[i + 1]);
            cnt -= 2;
 
        # Reduce the count by 1
        elif (cnt - 1 == k):
             
            # swap(per[1], per[i]);
            t = per[1];
            per[1] = per[i];
            per[i] = t;
            cnt -= 1;
        else:
            break;
        i += 2;
 
    # Print the permutation
    for i in range(1, n + 1):
        print(per[i], end = " ");
 
# Driver code
n = 4;
k = 3;
printPermutation(n, k);
 
# This code is contributed by mits

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to print the required permutation
    static void printPermutation(int n, int k)
    {
 
        // Not possible
        if (k >= n || (n % 2 == 0 && k == 0))
        {
            Console.Write(-1);
            return;
        }
        int []per = new int[n + 1] ;
        int i ;
 
        // Initial permutation
        for (i = 1; i <= n; i++)
        {
            per[i] = i;
        }
 
        // Indices for which gcd(p[i], i) > 1
        // in the initial permutation
        int cnt = n - 1;
        i = 2;
        while (i < n)
        {
 
            // Reduce the count by 2
            if (cnt - 1 > k)
            {
                swap(per, i, i + 1);
                cnt -= 2;
            }
             
            // Reduce the count by 1
            else if (cnt - 1 == k)
            {
                swap(per, 1, i);
                cnt--;
            }
            else
            {
                break;
            }
            i += 2;
        }
 
        // Print the permutation
        for (i = 1; i <= n; i++)
        {
            Console.Write(per[i] + " ");
        }
    }
 
    static int[] swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }
     
    // Driver code
    public static void Main()
    {
        int n = 4, k = 3;
        printPermutation(n, k);
    }
}
 
/* This code contributed by Ryuga */

<?php
// PHP implementation of the approach
 
// Function to print the required permutation
function printPermutation($n, $k)
{
 
    // Not possible
    if ($k >= $n || ($n % 2 == 0 &&
                     $k == 0))
    {
        echo -1;
        return;
    }
    $per[$n + 1] = array();
    $i;
 
    // Initial permutation
    for ($i = 1; $i <= $n; $i++)
        $per[$i] = $i;
 
    // Indices for which gcd(p[i], i) > 1
    // in the initial permutation
    $cnt = $n - 1;
    $i = 2;
    while ($i < $n)
    {
 
        // Reduce the count by 2
        if ($cnt - 1 > $k)
        {
             
            list($per[$i],
                 $per[$i + 1]) = array($per[$i + 1],
                                       $per[$i]);
            //swap(per[i], per[i + 1]);
            $cnt -= 2;
        }
 
        // Reduce the count by 1
        else if ($cnt - 1 == $k)
        {
             
            // swap(per[1], per[i]);
            list($per[1],
                 $per[$i]) = array($per[$i],
                                   $per[1]);
            $cnt--;
        }
        else
            break;
        $i += 2;
    }
 
    // Print the permutation
    for ($i = 1; $i <= $n; $i++)
        echo $per[$i], " ";
}
 
// Driver code
$n = 4;
$k = 3;
printPermutation($n, $k);
 
// This code is contributed by ajit.
?>

<script>
    // Javascript implementation of the approach
     
    // Function to print the required permutation
    function printPermutation(n, k)
    {
   
        // Not possible
        if (k >= n || (n % 2 == 0 && k == 0))
        {
            document.write(-1);
            return;
        }
        let per = new Array(n + 1);
        per.fill(0);
        let i ;
   
        // Initial permutation
        for (i = 1; i <= n; i++)
        {
            per[i] = i;
        }
   
        // Indices for which gcd(p[i], i) > 1
        // in the initial permutation
        let cnt = n - 1;
        i = 2;
        while (i < n)
        {
   
            // Reduce the count by 2
            if (cnt - 1 > k)
            {
                swap(per, i, i + 1);
                cnt -= 2;
            }
               
            // Reduce the count by 1
            else if (cnt - 1 == k)
            {
                swap(per, 1, i);
                cnt--;
            }
            else
            {
                break;
            }
            i += 2;
        }
   
        // Print the permutation
        for (i = 1; i <= n; i++)
        {
            document.write(per[i] + " ");
        }
    }
   
    function swap(arr, i, j)
    {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }
     
    let n = 4, k = 3;
      printPermutation(n, k);
 
</script>

1 2 3 4

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(N)