Intercambios mínimos adyacentes de dígitos requeridos para hacer que N sea divisible por K

Dados dos números enteros N y K , la tarea es calcular el número mínimo de intercambios de dígitos adyacentes necesarios para hacer que el número entero N sea divisible por K

Ejemplos:

Entrada: N = 12345, K = 2
Salida: 1
Explicación: Los dígitos en el índice 3 y t se pueden intercambiar para que el número entero resultante sea N = 12354, que es divisible por 2. Por lo tanto, el número requerido de intercambios adyacentes es 1 que es lo mínimo posible.

Entrada: N = 10203456, K = 100
Salida: 9

Enfoque: el problema dado se puede resolver iterando a través de todas las permutaciones de dígitos del entero dado y verificando todos los enteros que son divisibles por K, el número mínimo de intercambios adyacentes requeridos para convertir el entero dado al entero actual. A continuación se detallan los pasos a seguir:

  • Convierte el entero dado en una string de caracteres str y ordena los caracteres en orden no decreciente.
  • Iterar a través de todas las permutaciones de str usando la función next_permutation() incorporada .
  • Si el número entero representado por la permutación actual es divisible por K , verifique la cantidad de intercambios necesarios para convertir N en el número entero actual usando este algoritmo.
  • Mantener el número mínimo de intercambios requeridos en una variable que es la respuesta requerida.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum number of
// swaps requires to convert s1 to s2
int CountSteps(string s1, string s2, int size)
{
    int i = 0, j = 0;
    int result = 0;
 
    // Iterate over the first string
    // and convert every element
    while (i < size) {
        j = i;
 
        // Find index element of which
        // is equal to the ith element
        while (s1[j] != s2[i]) {
            j += 1;
        }
 
        // Swap adjacent elements in
        // the first string
        while (i < j) {
 
            // Swap elements
            char temp = s1[j];
            s1[j] = s1[j - 1];
            s1[j - 1] = temp;
            j -= 1;
            result += 1;
        }
        i += 1;
    }
    return result;
}
 
// Function to find minimum number of adjacent
// swaps required to make N divisible by K
int swapDigits(int N, int K)
{
    // Convert the integer into string
    string str = to_string(N);
 
    // Sort the elements of the string
    sort(str.begin(), str.end());
 
    // Stores the count of swaps
    int ans = INT_MAX;
 
    // Iterate over all permutations
    // of the given string
    do {
        // If the current integer
        // is divisible by K
        if (stoi(str) % K == 0)
 
            // Update ans
            ans = min(ans,
                      CountSteps(to_string(N), str,
                                 str.length()));
 
    } while (next_permutation(str.begin(),
                              str.end()));
 
    // Return Answer
    return ans;
}
 
// Driver Code
int main()
{
    int N = 10203456;
    int K = 100;
    cout << swapDigits(N, K);
 
    return 0;
}

Java

// Java program for the above approach
 
import java.util.*;
 
public class MapPr {
 
    // Function for next permutation
    static char[] next_permutation(char[] arr)
    {
 
        // Find the length of the array
        int n = arr.length;
 
        // Start from the right most digit and
        // find the first digit that is smaller
        // than the digit next to it.
        int k = n - 2;
        while (k >= 0) {
            if (arr[k] < arr[k + 1])
                break;
 
            k -= 1;
        }
        int l;
        // Reverse the list if the digit that
        // is smaller than the digit next to
        // it is not found.
        if (k < 0)
            Collections.reverse(Arrays.asList(arr));
        else {
            // Find the first greatest element
            // than arr[k] from the end of the list
            for (l = n - 1; l > k; l--) {
                if (arr[l] > arr[k])
                    break;
            }
 
            // Swap the elements at arr[k] and arr[l]
            char temp = arr[l];
            arr[l] = arr[k];
            arr[k] = temp;
        }
        // Reverse the list from k + 1 to the end
        // to find the most nearest greater number
        // to the given input number
 
        int mid = (k + 1) + (arr.length - k - 1) / 2;
        int pos = arr.length - 1;
        for (int i = k + 1; i < mid; i++) {
            char temp = arr[i];
            arr[i] = arr[pos];
            arr[pos--] = temp;
        }
 
        return arr;
    }
 
    // Function to find minimum number of
    // swaps requires to convert s1 to s2
    static int CountSteps(char[] s1, char[] s2, int size)
    {
        int i = 0;
        int j = 0;
        int result = 0;
 
        // Iterate over the first string
        // and convert every element
        while (i < size) {
            j = i;
            // Find index element of which
            // is equal to the ith element
            while (s1[j] != s2[i])
                j += 1;
 
            // Swap adjacent elements in
            // the first string
            while (i < j) {
                // Swap elements
                char temp = s1[j];
                s1[j] = s1[j - 1];
                s1[j - 1] = temp;
                j -= 1;
                result += 1;
            }
            i += 1;
        }
        return result;
    }
 
    // Function to find minimum number of adjacent
    // swaps required to make N divisible by K
    static int swapDigits(int N, int K)
    {
        // Convert the integer into string
        char[] st = (String.valueOf(N)).toCharArray();
        char[] st2 = (String.valueOf(N)).toCharArray();
 
        // Sort the elements of the string
        Arrays.sort(st);
        Arrays.sort(st2);
 
        String st2s = new String(st2);
 
        // Stores the count of swaps
        int ans = Integer.MAX_VALUE;
 
        // Iterate over all permutations
        // of the given string
        // If the current integer
        // is divisible by K
        while (true) {
            st = next_permutation(st);
            String sts = new String(st);
            int sti = Integer.parseInt(sts);
            if (sti % K == 0) {
                ans = Math.min(
                    ans,
                    CountSteps(
                        (String.valueOf(N)).toCharArray(),
                        st, st.length));
            }
            if (sts.equals(st2s))
                break;
        }
 
        // Return Answer
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 10203456;
        int K = 100;
        System.out.println(swapDigits(N, K));
    }
}
 
// This code is contributed by phasing17

Python3

# Python 3 program for the above approach
import sys
 
# Function for next permutation
def next_permutation(arr):
 
    # Find the length of the array
    n = len(arr)
 
    # Start from the right most digit and
    # find the first digit that is smaller
    # than the digit next to it.
    k = n - 2
    while k >= 0:
        if arr[k] < arr[k + 1]:
            break
 
        k -= 1
 
    # Reverse the list if the digit that
    # is smaller than the digit next to
    # it is not found.
    if k < 0:
        arr = arr[::-1]
    else:
        # Find the first greatest element
        # than arr[k] from the end of the list
        for l in range(n - 1, k, -1):
            if arr[l] > arr[k]:
                break
 
        # Swap the elements at arr[k] and arr[l
        arr[l], arr[k] = arr[k], arr[l]
 
        # Reverse the list from k + 1 to the end
        # to find the most nearest greater number
        # to the given input number
        arr[k + 1:] = reversed(arr[k + 1:])
 
    return arr
 
# Function to find minimum number of
# swaps requires to convert s1 to s2
def CountSteps(s1,  s2,  size):
 
    i = 0
    j = 0
    result = 0
 
    # Iterate over the first string
    # and convert every element
    while (i < size):
        j = i
        # Find index element of which
        # is equal to the ith element
        while (s1[j] != s2[i]):
            j += 1
 
        # Swap adjacent elements in
        # the first string
        while (i < j):
 
            # Swap elements
            temp = s1[j]
            s1[j] = s1[j - 1]
            s1[j - 1] = temp
            j -= 1
            result += 1
        i += 1
    return result
 
# Function to find minimum number of adjacent
# swaps required to make N divisible by K
def swapDigits(N,  K):
 
    # Convert the integer into string
    st = str(N)
    st2 = str(N)
 
    # Sort the elements of the string
    st = list(st)
    st2 = list(st2)
    st.sort()
    st2.sort()
 
    # Stores the count of swaps
    ans = sys.maxsize
 
    # Iterate over all permutations
    # of the given string
    # If the current integer
    # is divisible by K
    while (next_permutation(st) != st2):
        if(int(''.join(st)) % K == 0):
            ans = min(ans,
                      CountSteps(list(str(N)), st,
                                 len(st)))
 
    # Return Answer
    return ans
   
# Driver Code
if __name__ == "__main__":
 
    N = 10203456
    K = 100
    print(swapDigits(N, K))
 
    # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG {
  // Function for next permutation
  static char[] next_permutation(char[] arr)
  {
 
    // Find the length of the array
    int n = arr.Length;
 
    // Start from the right most digit and
    // find the first digit that is smaller
    // than the digit next to it.
    int k = n - 2;
    while (k >= 0) {
      if (arr[k] < arr[k + 1])
        break;
 
      k -= 1;
    }
    int l;
    // Reverse the list if the digit that
    // is smaller than the digit next to
    // it is not found.
    if (k < 0)
      Array.Reverse(arr);
    else {
      // Find the first greatest element
      // than arr[k] from the end of the list
      for (l = n - 1; l > k; l--) {
        if (arr[l] > arr[k])
          break;
      }
 
      // Swap the elements at arr[k] and arr[l]
      var temp = arr[l];
      arr[l] = arr[k];
      arr[k] = temp;
 
      // Reverse the list from k + 1 to the end
      // to find the most nearest greater number
      // to the given input number
      Array.Reverse(arr, k + 1, arr.Length - k - 1);
    }
    return arr;
  }
 
  // Function to find minimum number of
  // swaps requires to convert s1 to s2
  static int CountSteps(char[] s1, char[] s2, int size)
  {
    int i = 0;
    int j = 0;
    int result = 0;
 
    // Iterate over the first string
    // and convert every element
    while (i < size) {
      j = i;
      // Find index element of which
      // is equal to the ith element
      while (s1[j] != s2[i])
        j += 1;
 
      // Swap adjacent elements in
      // the first string
      while (i < j) {
        // Swap elements
        var temp = s1[j];
        s1[j] = s1[j - 1];
        s1[j - 1] = temp;
        j -= 1;
        result += 1;
      }
      i += 1;
    }
    return result;
  }
 
  // Function to find minimum number of adjacent
  // swaps required to make N divisible by K
  static int swapDigits(int N, int K)
  {
    // Convert the integer into string
    char[] st = (Convert.ToString(N)).ToCharArray();
    char[] st2 = (Convert.ToString(N)).ToCharArray();
 
    // Sort the elements of the string
    Array.Sort(st);
    Array.Sort(st2);
 
    string st2s = new string(st2);
 
    // Stores the count of swaps
    int ans = Int32.MaxValue;
 
    // Iterate over all permutations
    // of the given string
    // If the current integer
    // is divisible by K
    while (true) {
      st = next_permutation(st);
      string sts = new string(st);
      int sti = Convert.ToInt32(sts);
 
      if (sti % K == 0)
        ans = Math.Min(
        ans,
        CountSteps(
          (Convert.ToString(N)).ToCharArray(),
          st, st.Length));
      if (sts == st2s)
        break;
    }
 
    // Return Answer
    return ans;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int N = 10203456;
    int K = 100;
    Console.Write(swapDigits(N, K));
  }
}
 
// This code is contributed by phasing17

Javascript

// JavaScript program for the above approach
 
// Function for next permutation
function next_permutation(arr)
{
 
    // Find the length of the array
    let n = arr.length;
 
    // Start from the right most digit and
    // find the first digit that is smaller
    // than the digit next to it.
    let k = n - 2;
    while (k >= 0)
    {
        if (arr[k] < arr[k + 1])
            break
 
        k -= 1
    }
 
    // Reverse the list if the digit that
    // is smaller than the digit next to
    // it is not found.
    if (k < 0)
        arr.reverse()
    else
    {
        // Find the first greatest element
        // than arr[k] from the end of the list
        for (var l = n - 1; l > k; l -- )
        {
            if (arr[l] > arr[k])
                break
        }
 
        // Swap the elements at arr[k] and arr[l]
        var temp = arr[l]
        arr[l] = arr[k]
        arr[k] = temp
 
        // Reverse the list from k + 1 to the end
        // to find the most nearest greater number
        // to the given input number
        let arr1 = arr.slice(k + 1);
        arr1.reverse();
        for (var i = k + 1; i < arr1.length; i++)
            arr[i] = arr1[i]
    }
    return arr;
}
     
 
// Function to find minimum number of
// swaps requires to convert s1 to s2
function CountSteps(s1,  s2,  size)
{
    let i = 0;
    let j = 0;
    let result = 0;
 
    // Iterate over the first string
    // and convert every element
    while (i < size)
    {
        j = i
        // Find index element of which
        // is equal to the ith element
        while (s1[j] != s2[i])
            j += 1
 
        // Swap adjacent elements in
        // the first string
        while (i < j)
        {
            // Swap elements
            let temp = s1[j]
            s1[j] = s1[j - 1]
            s1[j - 1] = temp
            j -= 1
            result += 1
        }
        i += 1
    }
    return result
}
 
// Function to find minimum number of adjacent
// swaps required to make N divisible by K
function swapDigits(N,  K)
{
    // Convert the integer into string
    st = N.toString()
    st2 = N.toString()
 
    // Sort the elements of the string
    st = st.split("")
    st2 = st2.split("")
    st.sort()
    st2.sort()
 
 
    // Stores the count of swaps
    ans = Number. MAX_VALUE
 
    // Iterate over all permutations
    // of the given string
    // If the current integer
    // is divisible by K
    while (next_permutation(st).join("") != st2.join(""))
    {
        if(parseInt(st.join("")) % K == 0)
            ans = Math.min(ans,  CountSteps((N.toString()).split(""), st, st.length))
        
    }
     
    // Return Answer
    return ans
}
 
// Driver Code
let N = 10203456
let K = 100
console.log(swapDigits(N, K))
 
// This code is contributed by phasing17
Producción

9

Complejidad de tiempo: O((log N)! * (log N) 2 )
Espacio auxiliar: O(log N)

Publicación traducida automáticamente

Artículo escrito por anushikasethh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *