重新排列也可被其整除的数字

Question

给定数字 n，我们需要重新排列其所有数字，以使新的排列可以被 n 整除。此外，新数字不应等于 x。如果无法进行这种重新排列，请打印 -1。

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

简单方法：找到给定 n 的所有排列，然后检查它是否可被 n 整除，还检查新排列不应该等于 n。

有效方法：假设 y 是我们的结果，则 y = m * n ​，我们也知道 y 必须是 n 的数字重排，因此我们可以说根据给定条件限制 m(乘数) ​。

• y 的位数与 n 的位数相同。因此，m 必须小于 10。
• y 不能等于 n。因此，m 将大于 1。

因此，我们得到的乘数 m 在[2,9]范围内。因此，我们将找到所有可能的 y，然后检查 y 是否应具有与 n 相同的数字。

C++

// CPP program for finding rearrangement of n
// that is divisible  by n
#include
using namespace std;
  
// perform hashing for given n
void storeDigitCounts(int n, vector &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 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 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;
}

Python3

# 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

输出：

30105