Given a numerical string S, the task is to print all the permutations of the string which are divisible by N.
Examples:
Input: N = 5, S = “125”
Output: 125 215
Explanation:
All possible permutations are S are {125, 152, 215, 251, 521, 512}.
Out of these 6 permutations, only 2 {125, 215} are divisible by N (= 5).Input: N = 7, S = “4321”
Output: 4312 4123 3241
Approach: The idea is to generate all possible permutations and for each permutation, check if it is divisible by N or not. For each permutation found to be divisible by N, print them.
Below is the implementation of the above approach:
C++14
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to Swap two// charactersvoid swap_(char& a, char& b){ char temp; temp = a; a = b; b = temp;}// Function to generate all permutations// and print the ones that are// divisible by the Nvoid permute(char* str, int l, int r, int n){ int i; if (l == r) { // Convert string to integer int j = atoi(str); // Check for divisibility // and print it if (j % n == 0) cout << str << endl; return; } // Print all the permutations for (i = l; i < r; i++) { // Swap characters swap_(str[l], str[i]); // Permute remaining // characters permute(str, l + 1, r, n); // Revoke the swaps swap_(str[l], str[i]); }}// Driver Codeint main(){ char str[100] = "125"; int n = 5; int len = strlen(str); if (len > 0) permute(str, 0, len, n); return 0;} |
Java
// Java program to implement// the above approachclass GFG{// Function to Swap two// charactersstatic void swap_(char []a, int l, int i){ char temp; temp = a[l]; a[l] = a[i]; a[i] = temp;}// Function to generate all permutations// and print the ones that are// divisible by the Nstatic void permute(char[] str, int l, int r, int n){ int i; if (l == r) { // Convert String to integer int j = Integer.valueOf(String.valueOf(str)); // Check for divisibility // and print it if (j % n == 0) System.out.print(String.valueOf(str) + "\n"); return; } // Print all the permutations for(i = l; i < r; i++) { // Swap characters swap_(str, l, i); // Permute remaining // characters permute(str, l + 1, r, n); // Revoke the swaps swap_(str, l, i); }}// Driver Codepublic static void main(String[] args){ String str = "125"; int n = 5; int len = str.length(); if (len > 0) permute(str.toCharArray(), 0, len, n);}}// This code is contributed by amal kumar choubey |
Python3
# Python3 Program to implement# the above approach# Function to generate all # permutations and print # the ones that are# divisible by the Ndef permute(st, l, r, n): if (l == r): # Convert string # to integer p = ''.join(st) j = int(p) # Check for divisibility # and print it if (j % n == 0): print (p) return # Print all the # permutations for i in range(l, r): # Swap characters st[l], st[i] = st[i], st[l] # Permute remaining # characters permute(st, l + 1, r, n) # Revoke the swaps st[l], st[i] = st[i] ,st[l]# Driver Codeif __name__ == "__main__": st = "125" n = 5 length = len(st) if (length > 0): p = list(st) permute(p, 0, length, n);# This code is contributed by rutvik_56 |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to Swap two// charactersstatic void swap_(char []a, int l, int i){ char temp; temp = a[l]; a[l] = a[i]; a[i] = temp;} // Function to generate all permutations// and print the ones that are// divisible by the Nstatic void permute(char[] str, int l, int r, int n){ int i; if (l == r) { // Convert String to integer int j = Int32.Parse(new string(str)); // Check for divisibility // and print it if (j % n == 0) Console.Write(new string(str) + "\n"); return; } // Print all the permutations for(i = l; i < r; i++) { // Swap characters swap_(str, l, i); // Permute remaining // characters permute(str, l + 1, r, n); // Revoke the swaps swap_(str, l, i); }} // Driver Codepublic static void Main(string[] args){ string str = "125"; int n = 5; int len = str.Length; if (len > 0) permute(str.ToCharArray(), 0, len, n);}}// This code is contributed by rutvik_56 |
Javascript
<script>// Javascript program to implement// the above approach// Function to Swap two// charactersfunction swap_(a, l, i){ let temp; temp = a[l]; a[l] = a[i]; a[i] = temp;}// Function to generate all permutations// and print the ones that are// divisible by the Nfunction permute(str, l, r, n){ let i; if (l == r) { // Convert String to integer let j = parseInt((str).join("")); // Check for divisibility // and print it if (j % n == 0) document.write((str).join("") + "<br>"); return; } // Print all the permutations for(i = l; i < r; i++) { // Swap characters swap_(str, l, i); // Permute remaining // characters permute(str, l + 1, r, n); // Revoke the swaps swap_(str, l, i); }}// Driver Codelet str = "125";let n = 5;let len = str.length;if (len > 0) permute(str.split(""), 0, len, n);// This code is contributed by avanitrachhadiya2155</script> |
Output:
125 215
Time Complexity: O(N!)
Auxiliary Space: O(N)
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!
