Обратимые числа
Число называется обратимым, если сумма числа и его обратной стороны состояла только из нечетных цифр. Проблема в том, чтобы узнать, является ли число обратимым или нет.
Примеры:
Ввод: 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 .. ни у одного из них нет решений.
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 и многому другому, см. Полный курс подготовки к собеседованию .