Обратимые числа

Опубликовано: 20 Января, 2022

Число называется обратимым, если сумма числа и его обратной стороны состояла только из нечетных цифр. Проблема в том, чтобы узнать, является ли число обратимым или нет.

Примеры:

 Ввод: 36 
Выход: обратимое число
поскольку 36 + 63 = 99 имеет только нечетные цифры.

Ввод: 409 
Выход: обратимое число
поскольку 409 + 904 = 1313 имеет только нечетные цифры.

Ввод: 35 
Выход: необратимое число
поскольку 35 + 53 = 88 имеет только нечетные цифры

Наивный метод

Вычислите обратное значение каждого числа и прибавьте его к числу. Если результат обратимый, увеличьте значение счетчика. Вычислите это для каждого числа от 1 до n.

Сложность времени: O (10 ^ n), так как он должен вычислять обратное значение каждого числа.

Метод продвижения

  • Однозначное число: любое однозначное число будет добавлено к самому себе, которое всегда будет четным числом, и поэтому нет никаких решений.
  • 2-значный номер: Обе цифры должны быть нечетными.
    • Если a + b> 10, то у нас есть переходящий остаток, и, следовательно, первая цифра результата будет иметь четность, отличную от второй цифры.
    • Таким образом, Решения могут быть сформированы только тогда, когда a + b <10 и a + b нечетное. Итак, всего возможно 20 таких номеров.
  • 3-х значный номер:
    • Среднюю цифру нужно прибавить к себе. Это означает, что третья цифра должна иметь переходящий остаток и быть нечетной.
    • Поскольку третья цифра нечетная, первая цифра также нечетная, если вторая цифра не имеет переноса, что происходит, когда вторая цифра меньше 5, что дает нам 20 вариантов для первого / третьего набора цифр и 5 вариантов для середина, итого 100 пар.
  • Номер из 4 цифр: есть две пары, скажем, внутренняя и внешняя пара.
    • Если внутренняя пара имеет переходящий остаток, то внешняя пара также должна иметь переходящий остаток.
    • В противном случае две внутренние пары будут иметь разную четность.
    • Если внутренняя пара имеет перенос, тогда внешняя пара будет иметь другую четность, поскольку первая цифра будет иметь перенос, который не будет получен последней цифрой.
    • Поэтому у нас есть решения только тогда, когда ни одна из пар не имеет переноса.
    • Итого: для внешней пары это дает нам 20 вариантов, которые мы видели в двухзначном случае. И это дает нам 30 случаев для внутренней пары, поскольку они также могут содержать ноль.
      Или всего получается 20 * 30 = 600 решений.
  • 5, 9, 13 .. число цифр: Нет решения как однозначное число.
  • 6, 8, 10 .. число цифр: То же, что и двухзначное число, т.е. если n = 2 * k, то общее решение = 20 * 30 ^ (k-1).
  • 7, 11, 15 .. число цифр: То же, что и трехзначное число, т.е. если n = 4k + 3, то общее решение = 100 * 500 ^ (k).

Обобщение решения:

  • Все четные цифры (2, 4, 6, 8 ..) имеют одинаковую формулу, поэтому мы можем обобщить
    что для некоторого целого числа k такого, что n = 2k, мы имеем 20 * 30 ^ (k-1) решений
    который представляет внешнюю пару вместе со всеми внутренними парами.
  • Для n (3, 7, 11 ..) формы 4k + 3 (k - целое число) мы имеем, что средняя цифра и
    внешняя пара дает нам 5 и 20 вариантов, как в случае с 3-значным числом.
    Затем у нас есть наборы внутренних пар, которые дают нам 20 и 25 решений.
    Это означает, что мы можем обобщить его до 20 * 5 * (20 * 25) ^ (k) = 100 * 500 ^ (k).
  • Для n формы 4k + 1, что означает 1, 5, 9 .. ни у одного из них нет решений.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Program To check if a number is reversible or not 

C++

// C++ program to check if a given
// number is reversible or not
#include <iostream>
#include <cmath>
using namespace std;
 
// Function to check reversible number
void checkReversible (int n)
{
    int rev = 0, rem;
 
    // Calculate reverse of n
    int flag = n;
    while (flag)
    {
        rem = flag % 10;
        rev *= 10;
        rev += rem;
        flag /= 10;
    }
 
    // Calculate sum of number
    // and its reverse
    int sum = rev + n;
 
    // Check for reverse number
    // reach digit must be odd
    while (sum && (rem % 2 != 0))
    {
        rem = sum % 10;
        sum /= 10;
    }
 
    if (sum == 0)
        cout << "Reversible Number";
    else
        cout << "Non-Reversible Number";
}
 
// Driver function
int main()
{
    int n = 36;
    checkReversible(n);
    return 0;
}

Java

// Java program to check if a given
// number is reversible or not
import java.io.*;
 
class GFG {
     
    // Function to check reversible number
    static void checkReversible (int n)
    {
        int rev = 0, rem = 0;
     
        // Calculate reverse of n
        int flag = n;
        while (flag>0)
        {
            rem = flag % 10;
            rev *= 10;
            rev += rem;
            flag /= 10;
        }
     
        // Calculate sum of number
        // and its reverse
        int sum = rev + n;
     
        // Check for reverse number
        // reach digit must be odd
        while (sum > 0 && (rem % 2 != 0))
        {
            rem = sum % 10;
            sum /= 10;
        }
     
        if (sum == 0)
            System.out.println("Reversible Number");
        else
            System.out.println("Non-Reversible Number");
    }
     
    // Driver function
    public static void main (String[] args)
    {
        int n = 36;
        checkReversible(n);
         
    }
}
// This code is contributed by vt_m.

Python3

# Python3 program to check if a given
# number is reversible or not
 
# Function to check reversible number
def checkReversible (n):
     
    rev = 0
   
    # Calculate reverse of n
    flag = n
     
    while (flag != 0):
        rem = flag % 10
        rev *= 10
        rev += rem
        flag //= 10
     
    # Calculate sum of number
    # and its reverse
    sum = rev + n
   
    # Check for reverse number
    # reach digit must be odd
    while (sum and ((rem % 2) != 0)):
        rem = sum % 10
        sum //= 10
     
    if (sum == 0):
        print("Reversible Number")
    else:
        print("Non-Reversible Number")
 
# Driver Code
n = 36
 
checkReversible(n)
 
# This code is contributed by sanjoy_62

C#

// C# program to check if a given
// number is reversible or not
using System;
 
class GFG {
     
    // Function to check reversible number
    static void checkReversible (int n)
    {
        int rev = 0, rem = 0;
     
        // Calculate reverse of n
        int flag = n;
        while (flag > 0)
        {
            rem = flag % 10;
            rev *= 10;
            rev += rem;
            flag /= 10;
        }
     
        // Calculate sum of number
        // and its reverse
        int sum = rev + n;
     
        // Check for reverse number
        // reach digit must be odd
        while (sum > 0 && (rem % 2 != 0))
        {
            rem = sum % 10;
            sum /= 10;
        }
     
        if (sum == 0)
        Console.WriteLine("Reversible Number");
        else
        Console.WriteLine("Non-Reversible Number");
    }
     
    // Driver function
    public static void Main ()
    {
        int n = 36;
          checkReversible(n);
         
    }
}
 
// This code is contributed by vt_m.

Выход:

 Обратимый номер

 Program To count total reversible numbers upto n

C++

// C++ program to find the count of
// reversible numbers upto a given number n
#include <iostream>
#include <cmath>
using namespace std;
 
// Function to calculate the count of reversible number
void countReversible (int n)
{
    int count = 0;
 
    // Calculate counts of
    // reversible number of 1 to n-digits
    for ( int i = 1; i <= n; i++)
    {
        // All four possible cases and their formula
        switch (i % 4)
        {
 
        // for i of form 2k
        case 0:
        case 2:
            count += 20 * pow( 30, ( i / 2 - 1));
            break;
 
        // for i of form 4k + 3
        case 3:
            count += 100 * pow ( 500, i / 4 );
            break;
 
        // for i of form 4k + 1 no solution
        case 1:
            break;
        }
    }
    cout << count;
}
 
// Driver function
int main()
{
    // count up-to 9 digit numbers (1 billion)
    int n = 9;
    countReversible(n);
    return 0;
}

Java

// Java program to find the count of
// reversible numbers upto a given number n
import java.io.*;
 
class GFG {
 
    // Function to calculate the count
    // of reversible number
    static void countReversible (int n)
    {
        int count = 0;
     
        // Calculate counts of
        // reversible number of 1 to n-digits
        for ( int i = 1; i <= n; i++)
        {
            // All four possible cases
            // and their formula
            switch (i % 4)
            {
     
            // for i of form 2k
            case 0:
            case 2:
                count += 20 * Math.pow( 30, ( i / 2 - 1));
                break;
     
            // for i of form 4k + 3
            case 3:
                count += 100 * Math.pow ( 500, i / 4 );
                break;
     
            // for i of form 4k + 1 no solution
            case 1:
                break;
            }
        }
        System.out.println(count);
    }
     
    // Driver function
    public static void main (String[] args)
    {
        // count up-to 9 digit numbers (1 billion)
        int n = 9;
        countReversible(n);
         
    }
}
// This code is contributed by vt_m.

C#

// C# program to find the count of
// reversible numbers upto a given number n
using System;
 
class GFG {
     
    // Function to calculate the
    // count of reversible number
    static void countReversible (int n)
    {
        int count = 0;
     
        // Calculate counts of
        // reversible number of 1 to n-digits
        for ( int i = 1; i <= n; i++)
        {
            // All four possible cases
            // and their formula
            switch (i % 4)
            {
     
            // for i of form 2k
            case 0:
            case 2:
                count += 20 * (int)Math.Pow( 30, ( i / 2 - 1));
                break;
     
            // for i of form 4k + 3
            case 3:
                count += 100 * (int)Math.Pow ( 500, i / 4 );
                break;
     
            // for i of form 4k + 1 no solution
            case 1:
                break;
            }
        }
        Console.WriteLine(count);
    }
     
    // Driver function
    public static void Main ()
    {
        // count up-to 9 digit numbers (1 billion)
        int n = 9;
        countReversible(n);
         
    }
}
 
// This code is contributed by vt_m.

Выход:

 608720

Сложность времени O (n)
Ссылка: Project Euler 145: Сколько обратимых чисел меньше одного миллиарда?

Эта статья предоставлена Шивамом Прадханом (anuj_charm). Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

РЕКОМЕНДУЕМЫЕ СТАТЬИ