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
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