Reordenación de un número que también es divisible por él

Dado un número n, necesitamos reorganizar todos sus dígitos de modo que el nuevo arreglo sea divisible por n. Además, el nuevo número no debe ser igual a x. Si no es posible tal reordenamiento, imprima -1. Ejemplos:

Input : n = 1035
Output : 3105
The result 3105 is divisible by
given n and has the same set of digits.

Input : n = 1782
Output : m = 7128

Enfoque simple: encuentre todas las permutaciones de n dado y luego verifique si es divisible por n o no, también verifique que la nueva permutación no sea igual a n. Enfoque eficiente: supongamos que y es nuestro resultado, entonces y = m * n, también sabemos que y debe ser un reordenamiento de dígitos de n, por lo que podemos decir que ahora restringimos m (el multiplicador) según las condiciones dadas. 1) y tiene el mismo número de dígitos que n. Entonces, m debe ser menor que 10. 2) y no debe ser igual a n. Entonces, m será mayor que 1. Entonces obtenemos el multiplicador m en el rango [2,9]. Así que encontraremos todas las y posibles y luego comprobaremos si y tiene los mismos dígitos que n o no. 

// CPP program for finding rearrangement of n
// that is divisible  by n
#include<bits/stdc++.h>
using namespace std;
 
// perform hashing for given n
void storeDigitCounts(int n, vector<int> &hash)
{
    // perform hashing
    while (n)
    {
        hash[n%10]++;
        n /= 10;
    }
}
 
// check whether any arrangement exists
int rearrange (int n)
{
    // Create a hash for given number n
    // The hash is of size 10 and stores
    // count of each digit in n.
    vector<int> hash_n(10, 0);
    storeDigitCounts(n, hash_n);
     
    // check for all possible multipliers
    for (int mult=2; mult<10; mult++)
    {
        int curr = n * mult;
         
        vector<int> hash_curr(10, 0);
        storeDigitCounts(curr, hash_curr);
         
        // check hash table for both.
        // Please refer below link for help
        // of equal()
        // https://www.geeksforgeeks.org/stdequal-in-cpp/
        if (equal(hash_n.begin(), hash_n.end(),
                             hash_curr.begin()))
            return curr;
    }
    return -1;
}
 
// driver program
int main()
{
    int n = 10035;
    cout << rearrange(n);
    return 0;
}

// Java program for finding rearrangement of n
// that is divisible  by n
import java.util.*;
 
class GFG
{
  // perform hashing for given n
  static int[] storeDigitCounts(int n)
  {
    int arr[] = new int[10];
    for (int i = 0; i < 10; i++)
      arr[i] = 0;
    // perform hashing
    while (n > 0)
    {
      arr[n % 10]++;
      n /= 10;
    }
    return arr;
  }
 
 
  // check whether any arrangement exists
  static int rearrange (int n)
  {
    // Create a hash for given number n
    // The hash is of size 10 and stores
    // count of each digit in n.
    int[] hash = storeDigitCounts(n);
 
    // check for all possible multipliers
    for (int mult=2; mult<10; mult++)
    {
      int curr = n*mult;
 
      int[] hash_curr = storeDigitCounts(curr);
 
      // check hash table for both.
      int ind;
      for (ind = 0; ind < 10; ind++)
      {
        if (hash_curr[ind] != hash[ind])
          break;
      }
      if (ind == 10)  return curr;
 
    }
    return -1;
  }
 
  // driver program
  public static void main(String[] args)
  {
    int n = 10035;
    System.out.println(rearrange(n));
  }
}
 
// This code is contributed by phasing17

# Python3 program for finding rearrangement
# of n that is divisible by n
 
# Perform hashing for given n
def storeDigitCounts(n, Hash):
 
    # perform hashing
    while n > 0:
     
        Hash[n % 10] += 1
        n //= 10
 
# check whether any arrangement exists
def rearrange(n):
 
    # Create a hash for given number n
    # The hash is of size 10 and stores
    # count of each digit in n.
    hash_n = [0] * 10
    storeDigitCounts(n, hash_n)
     
    # check for all possible multipliers
    for mult in range(2, 10):
     
        curr = n * mult
         
        hash_curr = [0] * 10
        storeDigitCounts(curr, hash_curr)
         
        # check hash table for both.
        if hash_n == hash_curr:
            return curr
     
    return -1
 
# Driver Code
if __name__ == "__main__":
 
    n = 10035
    print(rearrange(n))
     
# This code is contributed by Rituraj Jain

// C# program for finding rearrangement of n
// that is divisible  by n
using System;
using System.Collections.Generic;
 
class GFG
{
 
  // perform hashing for given n
  static int[] storeDigitCounts(int n)
  {
    int[] arr = new int[10];
    for (int i = 0; i < 10; i++)
      arr[i] = 0;
    // perform hashing
    while (n > 0) {
      arr[n % 10]++;
      n /= 10;
    }
    return arr;
  }
 
  // check whether any arrangement exists
  static int rearrange(int n)
  {
    // Create a hash for given number n
    // The hash is of size 10 and stores
    // count of each digit in n.
    int[] hash = storeDigitCounts(n);
 
    // check for all possible multipliers
    for (int mult = 2; mult < 10; mult++) {
      int curr = n * mult;
 
      int[] hash_curr = storeDigitCounts(curr);
 
      // check hash table for both.
      int ind;
      for (ind = 0; ind < 10; ind++) {
        if (hash_curr[ind] != hash[ind])
          break;
      }
      if (ind == 10)
        return curr;
    }
    return -1;
  }
 
  // driver program
  public static void Main(string[] args)
  {
    int n = 10035;
    Console.WriteLine(rearrange(n));
  }
}
 
// This code is contributed by phasing17

// JavaScript program for finding rearrangement
// of n that is divisible by n
 
// Perform hashing for given n
function storeDigitCounts(n, Hash)
{
    // perform hashing
    while (n > 0)
    {
        Hash[n % 10] += 1;
        n = Math.floor(n / 10);
    }
    return Hash;
}
 
// check whether any arrangement exists
function rearrange(n)
{
    // Create a hash for given number n
    // The hash is of size 10 and stores
    // count of each digit in n.
    let hash_n = new Array(10).fill(0);
    hash_n = storeDigitCounts(n, hash_n);
     
    // check for all possible multipliers
    for (var mult = 2; mult < 10; mult++)
    {
        let curr = n * mult;
         
        let hash_curr = new Array(10).fill(0);
        hash_curr = storeDigitCounts(curr, hash_curr) ;
         
        // check hash table for both.
        if (JSON.stringify(hash_curr)==JSON.stringify(hash_n))
            return curr ;
    }
     
    return -1;
}
 
// Driver Code
let n = 10035;
console.log(rearrange(n));
     
// This code is contributed by phasing17

Producción:

30105

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.