Given a number n, we need to rearrange all its digits such that the new arrangement is divisible by n. Also, the new number should not be equal to x. If no such rearrangement is possible, print -1. Examples:
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
Simple Approach : Find all the permutation of given n and then check whether it is divisible by n or not also check that new permutation should not be equal to n. Efficient Approach : Let’s suppose that y is our result then y = m * n, also we know that y must be a rearrangement of digits of n so we can say now restrict m (the multiplier) as per given conditions. 1) y has the same number of digits as n has. So, m must be less than 10. 2) y must not be equal to n. So, m will be greater than 1. So we get the multiplier m in the range [2,9]. So we will find all the possible y and then check that should y has the same digits as n or not.
C++
// CPP program for finding rearrangement of n// that is divisible by n#include<bits/stdc++.h>using namespace std;// perform hashing for given nvoid storeDigitCounts(int n, vector<int> &hash){ // perform hashing while (n) { hash[n%10]++; n /= 10; }}// check whether any arrangement existsint 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() if (equal(hash_n.begin(), hash_n.end(), hash_curr.begin())) return curr; } return -1;}// driver programint main(){ int n = 10035; cout << rearrange(n); return 0;} |
Java
// Java program for finding rearrangement of n// that is divisible by nimport 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
# 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 Codeif __name__ == "__main__": n = 10035 print(rearrange(n)) # This code is contributed by Rituraj Jain |
C#
// C# program for finding rearrangement of n// that is divisible by nusing 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
// 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 Codelet n = 10035;console.log(rearrange(n)); // This code is contributed by phasing17 |
Output:
30105
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
