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