Horje
Palindromic Selfie Numbers

Given a number x, find it’s palindromic selfie number according to selfie multiplicative rule. If such a number doesn’t exist, then print “No such number exists”. 
A Palindromic selfie number satisfies the selfie multiplicative rule such that there exists another number y with x * reverse_digits_of(x) = y * reverse_digits_of(y), with the condition that the number y is obtained by some ordering of the digits in x, i.e x and y should have same digits with different order.
Examples : 
 

Input : 1224
Output : 2142
Explanation :
Because, 1224 X 4221 = 2142 X 2412
And all digits of 2142 are formed by a different 
permutation of the digits in 1224
(Note: The valid output is either be 2142 or 2412)

Input : 13452
Output : 14532
Explanation :
Because, 13452 X 25431 = 14532 X 23541
And all digits of 14532 are formed by a different 
permutation of the digits in 13452

Input : 12345
Output : No such number exists
Explanation :
Because, with no combination of digits 1, 2, 3, 4, 5 
could we get a number that satisfies 
12345 X 54321 = number X reverse_of_its_digits

 

Approach : 
 

  • The idea is to break down the number and obtain all permutations of the digits in the number.
  • Then, the number and its palindrome are removed from the set of permutations obtained, which will form the LHS of our equality.
  • To check for RHS, we now iterate over all other permutations equating
 LHS = current_number X palindrome(current_number)
  • As soon as we get a match, we exit the loop with an affirmative message, else print “No such number available”.

Below is implementation of above approach : 
 

C++

// C++ program to find palindromic selfie numbers
#include <bits/stdc++.h>
 
using namespace std;
 
class palindrome_selfie {
  public:
   
  // To store all permutations of digits in the number
  set<int> all_permutes;
 
  int number; // input number
 
  palindrome_selfie(int num) { number = num; }
 
  // Function to reverse the digits of a number
  int palindrome(int num)
  {
    int reversednum = 0;
    int d;
    while (num > 0) {
      d = num % 10; // Extract last digit
 
      // Append it at the beg
      reversednum = reversednum * 10 + d;
      num = num / 10; // Reduce number until 0
    }
 
    return reversednum;
  }
   
  // Function that swaps the digits i and j in the num
  int swap(int num, int i, int j)
  {
    char temp;
 
    string charArray = to_string(num);
     
    // Swap the ith and jth character
    temp = charArray[i];
    charArray[i] = charArray[j];
    charArray[j] = temp;
 
    // Convert back to int and return
    return stoi(charArray);
  }
   
  // Function to get all possible permutations
  // of the digits in num
  void permute(int num, int l, int r)
  {
     
    // Adds the new permutation obtained in the set
    if (l == r)
      all_permutes.insert(num);
 
    else {
      for (int i = l; i <= r; i++) {
 
        // Swap digits to get a different ordering
        num = swap(num, l, i);
 
        // Recurse to next pair of digits
        permute(num, l + 1, r);
        num = swap(num, l, i); // Swap back
      }
    }
  }
   
  // Function to check palindromic selfie
  void palin_selfie()
  {
     
    // Length of the number required for
    // calculating all permutations of the digits
    int l = to_string(number).length() - 1;
 
    permute(number, 0, l); // Calculate all permutations
 
    /* Remove the number and its palindrome from
           the obtained set as this is the LHS of
           multiplicative equality */
    auto n1 = all_permutes.find(palindrome(number));
    auto n2 = all_permutes.find(number);
    all_permutes.erase(n1);
    all_permutes.erase(n2);
 
    bool flag = false; // Denotes the status result
 
    // Iterate over all other numbers
    for (auto it : all_permutes) {
      int number2 = it;
 
      // Check for equality x*palin(x) = y*palin(y)
      if (number * palindrome(number)
          == number2 * palindrome(number2)) {
        cout << "Palindrome multiplicative"
          << "selfie of " << number
          << " is  : " << number2 << endl;
 
        flag = true; // Answer found
        break;
      }
    }
 
    // If no such number found
    if (flag == false) {
      cout << "Given number has no palindrome selfie."
        << endl;
    }
  }
};
 
// Driver Function
int main()
{
  // First example, input = 145572
  palindrome_selfie example1(145572);
  example1.palin_selfie();
 
  // Second example, input = 19362
  palindrome_selfie example2(19362);
  example2.palin_selfie();
 
  // Third example, input = 4669
  palindrome_selfie example3(4669);
  example3.palin_selfie();
  return 0;
}
 
// This code is contributed by phasing17

Java

// Java program to find palindromic selfie numbers
import java.util.*;
 
public class palindrome_selfie {
    // To store all permutations of digits in the number
    Set<Integer> all_permutes = new HashSet<Integer>();
 
    int number; // input number
 
    public palindrome_selfie(int num)
    {
        number = num;
    }
 
    // Function to reverse the digits of a number
    public int palindrome(int num)
    {
        int reversednum = 0;
        int d;
        while (num > 0) {
            d = num % 10; // Extract last digit
 
            // Append it at the beg
            reversednum = reversednum * 10 + d;
            num = num / 10;  // Reduce number until 0
        }
 
        return reversednum;
    }
 
    // Function to check palindromic selfie
    public void palin_selfie()
    {
        // Length of the number required for
        // calculating all permutations of the digits
        int l = String.valueOf(number).length() - 1;
         
        this.permute(number, 0, l); // Calculate all permutations
         
        /* Remove the number and its palindrome from
           the obtained set as this is the LHS of
           multiplicative equality */
        all_permutes.remove(palindrome(number));
        all_permutes.remove(number);
 
        boolean flag = false; // Denotes the status result
 
        // Iterate over all other numbers
        Iterator it = all_permutes.iterator();
        while (it.hasNext()) {
            int number2 = (int)it.next();
 
            // Check for equality x*palin(x) = y*palin(y)
            if (number * palindrome(number) ==
                         number2 * palindrome(number2)) {
                System.out.println("Palindrome multiplicative" +
                                    "selfie of "+ number + " is  : "
                                     + number2);
 
                flag = true; // Answer found
                break;
            }
        }
 
        // If no such number found
        if (flag == false) {
            System.out.println("Given number has no palindrome selfie.");
        }
    }
 
    // Function to get all possible permutations
    // of the digits in num
    public void permute(int num, int l, int r)
    {
        // Adds the new permutation obtained in the set
        if (l == r)
            all_permutes.add(num);
 
        else {
            for (int i = l; i <= r; i++) {
 
                // Swap digits to get a different ordering
                num = swap(num, l, i);
 
                // Recurse to next pair of digits
                permute(num, l + 1, r);
                num = swap(num, l, i); // Swap back
            }
        }
    }
 
    // Function that swaps the digits i and j in the num
    public int swap(int num, int i, int j)
    {
        char temp;
 
        // Convert int to char array
        char[] charArray = String.valueOf(num).toCharArray();
 
        // Swap the ith and jth character
        temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
 
        // Convert back to int and return
        return Integer.valueOf(String.valueOf(charArray));
    }
 
    // Driver Function
    public static void main(String args[])
    {
        // First example, input = 145572
        palindrome_selfie example1 = new palindrome_selfie(145572);
        example1.palin_selfie();
 
        // Second example, input = 19362
        palindrome_selfie example2 = new palindrome_selfie(19362);
        example2.palin_selfie();
 
        // Third example, input = 4669
        palindrome_selfie example3 = new palindrome_selfie(4669);
        example3.palin_selfie();
    }
}

Python3

# Python3 program to find palindromic selfie numbers
 
# To store all permutations of digits in the number
class palindrome_selfie:
    def __init__(self, num):
        self.all_permutes = set();
        self.number = num;   # input number
     
    # Function to reverse the digits of a number
    def palindrome(self, num):
 
        reversednum = 0;
        while (num > 0):
            d = num % 10;   # Extract last digit
     
            # Append it at the beg
            reversednum = reversednum * 10 + d;
            num = (num // 10);  # Reduce number until 0
         
        return reversednum;
     
    # Function that swaps the digits i and j in the num
    def swap(self, num, i, j):
 
        charArray = list(str(num))
     
        # Swap the ith and jth character
        temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
     
        # Convert back to int and return
        return int("".join(charArray))
     
    # Function to get all possible permutations
    # of the digits in num
    def permute(self, num, l, r):
 
        # Adds the new permutation obtained in the set
        if (l == r):
            self.all_permutes.add(num);
     
        else:
            for i in range(l, r + 1):
     
                # Swap digits to get a different ordering
                num = self.swap(num, l, i);
     
                # Recurse to next pair of digits
                self.permute(num, l + 1, r);
                num = self.swap(num, l, i);      # Swap back
             
    # Function to check palindromic selfie
    def palin_selfie(self):
 
        # Length of the number required for
        # calculating all permutations of the digits
        l = len(str(self.number)) - 1
     
        self.permute(self.number, 0, l);      # Calculate all permutations
     
        # Remove the number and its palindrome from
        #       the obtained set as this is the LHS of
        #       multiplicative equality */
        self.all_permutes.remove(self.palindrome(self.number));
        self.all_permutes.remove(self.number);
     
        flag = False;   # Denotes the status result
     
        # Iterate over all other numbers
        for it in self.all_permutes:
            number2 = it;
     
            # Check for equality x*palin(x) = y*palin(y)
            if (self.number * self.palindrome(self.number) == number2 * self.palindrome(number2)):
                print("Palindrome multiplicative selfie of", self.number, "is  :" , number2);
     
                flag = True;    # Answer found
                break;
     
        # If no such number found
        if (flag == False):
            print("Given number has no palindrome selfie.");
 
# Driver Function
 
# First example, input = 19362
n2 = palindrome_selfie(19362);
n2.palin_selfie();
 
# Second example, input = 4669
n3 = palindrome_selfie(4669);
n3.palin_selfie();
 
# This code is contributed by phasing17

C#

// C# program to find palindromic selfie numbers
using System;
using System.Collections.Generic;
 
public class palindrome_selfie
{
    // To store all permutations of digits in the number
    HashSet<int> all_permutes = new HashSet<int>();
 
    int number; // input number
 
    public palindrome_selfie(int num)
    {
        number = num;
    }
 
    // Function to reverse the digits of a number
    public int palindrome(int num)
    {
        int reversednum = 0;
        int d;
        while (num > 0)
        {
            d = num % 10; // Extract last digit
 
            // Append it at the beg
            reversednum = reversednum * 10 + d;
            num = num / 10; // Reduce number until 0
        }
        return reversednum;
    }
 
    // Function to check palindromic selfie
    public void palin_selfie()
    {
        // Length of the number required for
        // calculating all permutations of the digits
        int l = String.Join("",number).Length - 1;
         
        this.permute(number, 0, l); // Calculate all permutations
         
        /* Remove the number and its palindrome from
        the obtained set as this is the LHS of
        multiplicative equality */
        all_permutes.Remove(palindrome(number));
        all_permutes.Remove(number);
 
        bool flag = false; // Denotes the status result
 
        // Iterate over all other numbers
        foreach (var number2 in all_permutes)
        {
 
            // Check for equality x*palin(x) = y*palin(y)
            if (number * palindrome(number) ==
                        number2 * palindrome(number2))
            {
                Console.WriteLine("Palindrome multiplicative" +
                                    "selfie of "+ number + " is : "
                                    + number2);
 
                flag = true; // Answer found
                break;
            }
        }
 
        // If no such number found
        if (flag == false)
        {
            Console.WriteLine("Given number has "+
                            "no palindrome selfie.");
        }
    }
 
    // Function to get all possible
    // permutations of the digits in num
    public void permute(int num, int l, int r)
    {
        // Adds the new permutation obtained in the set
        if (l == r)
            all_permutes.Add(num);
 
        else
        {
            for (int i = l; i <= r; i++)
            {
 
                // Swap digits to get a different ordering
                num = swap(num, l, i);
 
                // Recurse to next pair of digits
                permute(num, l + 1, r);
                num = swap(num, l, i); // Swap back
            }
        }
    }
 
    // Function that swaps the
    // digits i and j in the num
    public int swap(int num, int i, int j)
    {
        char temp;
 
        // Convert int to char array
        char[] charArray = String.Join("",num).ToCharArray();
 
        // Swap the ith and jth character
        temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
 
        // Convert back to int and return
        return int.Parse(String.Join("",charArray));
    }
 
    // Driver code
    public static void Main(String []args)
    {
        // First example, input = 145572
        palindrome_selfie example1 = new palindrome_selfie(145572);
        example1.palin_selfie();
 
        // Second example, input = 19362
        palindrome_selfie example2 = new palindrome_selfie(19362);
        example2.palin_selfie();
 
        // Third example, input = 4669
        palindrome_selfie example3 = new palindrome_selfie(4669);
        example3.palin_selfie();
    }
}
 
// This code contributed by Rajput-Ji

Javascript

// JavaScript program to find palindromic selfie numbers
 
// To store all permutations of digits in the number
 
let all_permutes;
let number;
function init(num)
{
    all_permutes = new Set();
 
    number = num; // input number
}
 
// Function to reverse the digits of a number
function palindrome(num)
{
    let reversednum = 0;
    let d;
    while (num > 0) {
        d = num % 10; // Extract last digit
 
        // Append it at the beg
        reversednum = reversednum * 10 + d;
        num = Math.floor(num / 10); // Reduce number until 0
    }
 
    return reversednum;
}
 
// Function that swaps the digits i and j in the num
function swap(num, i, j)
{
    let temp;
 
    let charArray = (num.toString()).split("");
 
    // Swap the ith and jth character
    temp = charArray[i];
    charArray[i] = charArray[j];
    charArray[j] = temp;
 
    // Convert back to int and return
    return parseInt(charArray.join(""));
}
 
// Function to get all possible permutations
// of the digits in num
function permute(num, l, r)
{
 
    // Adds the new permutation obtained in the set
    if (l == r)
        all_permutes.add(num);
 
    else {
        for (var i = l; i <= r; i++) {
 
            // Swap digits to get a different ordering
            num = swap(num, l, i);
 
            // Recurse to next pair of digits
            permute(num, l + 1, r);
            num = swap(num, l, i); // Swap back
        }
    }
}
 
// Function to check palindromic selfie
function palin_selfie()
{
 
    // Length of the number required for
    // calculating all permutations of the digits
    var l = (number.toString()).length - 1;
 
    permute(number, 0, l); // Calculate all permutations
 
    /* Remove the number and its palindrome from
           the obtained set as this is the LHS of
           multiplicative equality */
    all_permutes.delete(palindrome(number));
    all_permutes.delete(number);
 
    let flag = false; // Denotes the status result
 
    // Iterate over all other numbers
    for (var it of all_permutes) {
        let number2 = it;
 
        // Check for equality x*palin(x) = y*palin(y)
        if (number * palindrome(number)
            == number2 * palindrome(number2)) {
            console.log(
                "Palindrome multiplicative selfie of "
                + number + " is  : " + number2);
 
            flag = true; // Answer found
            break;
        }
    }
 
    // If no such number found
    if (flag == false) {
        console.log(
            "Given number has no palindrome selfie.");
    }
}
 
// Driver Function
 
// First example, input = 145572
init(145572);
palin_selfie();
 
// Second example, input = 19362
init(19362);
palin_selfie();
 
// Third example, input = 4669
init(4669);
palin_selfie();
 
// This code is contributed by phasing17

Output : 

Palindrome multiplicative selfie of 145572 is  : 157452
Given number has no palindrome selfie.
Palindrome multiplicative selfie of 4669 is  : 6496

Time complexity: O(n*n!) where n is the number of digits in the input number.

Auxiliary Space: O(n!)


 


Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Maximum rational number (or fraction) from an array Maximum rational number (or fraction) from an array
Average of odd numbers till a given odd number Average of odd numbers till a given odd number
Sum of fifth powers of the first n natural numbers Sum of fifth powers of the first n natural numbers
Program to compare two fractions Program to compare two fractions
Find the distance covered to collect items at equal distances Find the distance covered to collect items at equal distances

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 15



 

Horje