Как найти последнюю ненулевую цифру факториала

Reb0ot

1 / 1 / 0

Регистрация: 11.09.2021

Сообщений: 118

Вывести последнюю ненулевую цифру факториала

13.12.2021, 12:51. Показов 2429. Ответов 13

Метки нет (Все метки)

Алгоритм работает неправильно на числах 15, 25 и т.д. В остальном всё нормально

C++

#include <iostream>
 
using namespace std;
 
int main()
{
  int n;
  unsigned long res = 1;
    cin >> n;
    for(int i = 2; i <= n; ++i)
    {
        res *= i;
        while(res % 10 == 0)
            res /= 10;
        res %= 10;
    }
    cout << res;
}

FFPowerMan

2019 / 1123 / 475

Регистрация: 11.10.2018

Сообщений: 5,727

13.12.2021, 13:12

Здравствуйте. Так надо, наверное, сначала факториал вычислить, а потом уже последнюю цифру брать.

Добавлено через 3 минуты
Вот так

C++

#include <iostream>
using namespace std;
 
int main()
{
int n;
unsigned long d = 1;
 
//cin >> n;
n = 5;
for(int i = 2; i <= n; ++i)
    d *= i;
cout << "d = " << d << 'n';
 
while(d%10 == 0)
    d /= 10;
d %= 10;
cout << d;
}

1 / 1 / 0

Регистрация: 11.09.2021

Сообщений: 118

13.12.2021, 13:53

[ТС]

FFPowerMan, проблема осталась. При вводе 25 оно выводит 6, хотя в факториале 25 нет этой цифры

_Ivana

4816 / 2276 / 287

Регистрация: 01.03.2013

Сообщений: 5,944

Записей в блоге: 27

13.12.2021, 13:54

Сообщение от FFPowerMan

Так надо, наверное, сначала факториал вычислить

Не надо. Не влезет у тебя факториал в ансигнед лонг.

C++

int f(int n) {
    int r = 1;
    for(int i=2; i<=n; i++) {
        r *= i;
        while (r%10 == 0) r /= 10;
        r %= 10;
    }
    return r;
}

1 / 1 / 0

Регистрация: 11.09.2021

Сообщений: 118

13.12.2021, 14:00

[ТС]

FFPowerMan, понял, в unsigned long не может хранить такие большие данные

Добавлено через 2 минуты
_Ivana, та же проблема, выводит 5 у факториала 25, хотя 5 находится на 3 ненулевых знака левее

Добавлено через 50 секунд
и при этом, 15 не работает, хотя в варианте FFPowerMan, у 15 выводило правильную цифру — 8

4023 / 3280 / 920

Регистрация: 25.03.2012

Сообщений: 12,263

Записей в блоге: 1

13.12.2021, 14:01

FFPowerMan, что за ерунда? Как раз всё правильно человек делает, а ты в лоб задачу решить хочешь!

ram876

685 / 392 / 200

Регистрация: 19.12.2016

Сообщений: 1,593

13.12.2021, 14:17

Код не мой, в нете нашел и немного подправил.

Кликните здесь для просмотра всего текста

C++

// C++ program to compute factorial of big numbers
#include<iostream>
using namespace std;
#include <string>
 
// Maximum number of digits in output
#define MAX 500
 
int multiply(int x, int res[], int res_size);
 
// This function finds factorial of large numbers
// and prints them
std::string factorial(int n)
{
    int res[MAX];
    std::string str;
    // Initialize result
    res[0] = 1;
    int res_size = 1;
 
    // Apply simple factorial formula n! = 1 * 2 * 3 * 4...*n
    for (int x=2; x<=n; x++)
        res_size = multiply(x, res, res_size);
 
    cout << "Factorial of given number is n";
    for (int i=res_size-1; i>=0; i--)
        str += to_string(res[i]);
        return str;
}
 
// This function multiplies x with the number
// represented by res[].
// res_size is size of res[] or number of digits in the
// number represented by res[]. This function uses simple
// school mathematics for multiplication.
// This function may value of res_size and returns the
// new value of res_size
int multiply(int x, int res[], int res_size)
{
    int carry = 0; // Initialize carry
 
    // One by one multiply n with individual digits of res[]
    for (int i=0; i<res_size; i++)
    {
        int prod = res[i] * x + carry;
 
        // Store last digit of 'prod' in res[]
        res[i] = prod % 10;
 
        // Put rest in carry
        carry = prod/10;
    }
 
    // Put carry in res and increase result size
    while (carry)
    {
        res[res_size] = carry%10;
        carry = carry/10;
        res_size++;
    }
    return res_size;
}
 
// Driver program
int main()
{
    std::string str = factorial(25);
    std::cout <<str;
    auto it = str.end();
    while(*--it == '0');
    std::cout << "n" << "last no zero number is " << *it;
    return 0;
}

1 / 1 / 0

Регистрация: 11.09.2021

Сообщений: 118

13.12.2021, 14:25

[ТС]

ram876, спасибо, а почему мой код неправильно считал с 15, 25, но при этом остальные числа в этом диапазоне выводились правильно?

ram876

685 / 392 / 200

Регистрация: 19.12.2016

Сообщений: 1,593

13.12.2021, 14:33

Думаю, у вас было переполнение. Вот так посмотрите максимальное значение, которое может принять unsigned long int:

Кликните здесь для просмотра всего текста

C++

#include <iostream>
#include <climits>
int main()
{
    std::cout<<ULONG_MAX;
    return 0;
}

Байт

Диссидент

27472 / 17160 / 3783

Регистрация: 24.12.2010

Сообщений: 38,662

13.12.2021, 14:38

Сообщение от _Ivana

Не надо.

я тоже так думаю. Небольшая модификация

C++

int f(int n) {
    int r = 1;
    for(int i=2; i<=n; i++) {
       int ii = i;
       while (ii%10==0) ii /= 10;
        ii = ii%10;
        r *= ii;
        while (r%10 == 0) r /= 10;
        r %= 10;
    }
    return r;
}

1 / 1 / 0

Регистрация: 11.09.2021

Сообщений: 118

13.12.2021, 14:43

[ТС]

Байт, с 15 и выше не работает

повар1

784 / 591 / 317

Регистрация: 24.02.2017

Сообщений: 2,088

13.12.2021, 15:09

C++

#include <iostream>
using namespace std;
 
int main() {
    long long n,d=1;
 
    cin>>n;
    for(int i=2;i<=n;i++){
       d=d%1000*i;
       while(1){
          if(d%10!=0)break;
          d/=10;
       }
    }
    cout<<d%10;
    return 0;
}

_Ivana

4816 / 2276 / 287

Регистрация: 01.03.2013

Сообщений: 5,944

Записей в блоге: 27

13.12.2021, 20:18

Сообщение от Reb0ot

_Ivana, та же проблема

Да, поспешил с алгоритмом, ошибся. Вот исправленный

C++

int f(int n) {
    int r = 1, d2 = 0, d5 = 0;
    for(int i=2; i<=n; i++) {
        int j = i;
        while (j%2 == 0 && j > 1) { j /= 2; d2++; }
        while (j%5 == 0 && j > 1) { j /= 5; d5++; }
        r = (r*j)%10;
    }
    for(int i=0; i<(d2-d5); i++) r = (r*2)%10;
    return r;
}

Сообщение от Reb0ot

а почему мой код неправильно считал с 15, 25, но при этом остальные числа в этом диапазоне выводились правильно?

Потому что с остальными случайно повезло не нарваться на перемножение 2 и 5:

Код

(12 % 10) * 5 = 10 -> 1
12 * 5 = 60 -> 6

ЗЫ и мой алгоритм имел точно такую же ошибку

0 / 0 / 0

Регистрация: 15.09.2022

Сообщений: 2

22.09.2022, 12:46

Спасибо

IT_Exp

Эксперт

87844 / 49110 / 22898

Регистрация: 17.06.2006

Сообщений: 92,604

22.09.2022, 12:46

Помогаю со студенческими работами здесь

Как найти и вывести последнюю цифру дробного числа (количество знаков после запятой не известно)
Добрый день, впервые решил обратится за помощью.
Не подскажете ли, как найти и вывести последнюю…

Если число трёхзначное, то вывести первую цифру числа, если нет — последнюю
N — натуральное число.Если оно трёхзначное — вывести первую цифру числа,если нет — последнюю.

Определить является ли заданное число трёхзначным, если нет, вывести его последнюю цифру, а если да, первую
Помогите пожалуйста, срочно. Нужно определить является ли число трёхзначным, если нет, вывести его…

Найти последнюю ненулевую цифру факториала n
Помогите решить задачу:
Нужно найти последнюю ненулевую цифру числа n! . 1<n<1000000. Помгите…

Определить последнюю ненулевую цифру факториала
Задача определить последнюю не нулевую цифру факториала из предоставляемого числа N
В моём…

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Источник

Given a number n, find the last non-zero digit in n!.
Examples:

Input  : n = 5
Output : 2
5! = 5 * 4 * 3 * 2 * 1 = 120
Last non-zero digit in 120 is 2.

Input  : n = 33
Output : 8

A Simple Solution is to first find n!, then find the last non-zero digit of n. This solution doesn’t work for even slightly large numbers due to arithmetic overflow.
A Better Solution is based on the below recursive formula

Let D(n) be the last non-zero digit in n!
If tens digit (or second last digit) of n is odd
    D(n) = 4 * D(floor(n/5)) * D(Unit digit of n) 
If tens digit (or second last digit) of n is even
    D(n) = 6 * D(floor(n/5)) * D(Unit digit of n)

Illustration of the formula:
For the numbers less than 10 we can easily find the last non-zero digit by the above simple solution, i.e., first computing n!, then finding the last digit.
D(1) = 1, D(2) = 2, D(3) = 6, D(4) = 4, D(5) = 2,
D(6) = 2, D(7) = 4, D(8) = 2, D(9) = 8.

D(1) to D(9) are assumed to be precomputed.

Example 1: n = 27 [Second last digit is even]:
D(27) = 6 * D(floor(27/5)) * D(7)
      = 6 * D(5) * D(7)
      = 6 * 2 * 4 
      = 48
Last non-zero digit is  8

Example 2: n = 33 [Second last digit is odd]:
D(33) = 4 * D(floor(33/5)) * D(3)
      = 4 * D(6) * 6
      = 4 * 2 * 6
      = 48
Last non-zero digit is 8

How does the above formula work?
The below explanation provides intuition behind the formula. Readers may Refer http://math.stackexchange.com/questions/130352/last-non-zero-digit-of-a-factorial for complete proof.

14! = 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 
                     6 * 5 * 4 * 3 * 2 * 1

Since we are asked about last non-zero digit, 
we remove all 5's and equal number of 2's from
factors of 14!.  We get following:

14! = 14 * 13 * 12 * 11 * 2 * 9 * 8 * 7 *
                           6 * 3 * 2 * 1

Now we can get last non-zero digit by multiplying
last digits of above factors!

In n! a number of 2’s are always more than a number of 5’s. To remove trailing 0’s, we remove 5’s and equal number of 2’s.
Let a = floor(n/5), b = n % 5. After removing an equal number of 5’s and 2’s, we can reduce the problem from n! to 2^a * a! * b!
D(n) = 2^a * D(a) * D(b)
Implementation:

C++

#include<bits/stdc++.h>

using namespace std;

int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};

int lastNon0Digit(int n)

{

if (n < 10)

return dig[n];

if (((n/10)%10)%2 == 0)

return (6*lastNon0Digit(n/5)*dig[n%10]) % 10;

else

return (4*lastNon0Digit(n/5)*dig[n%10]) % 10;

}

int main()

{

int n = 14;

cout << lastNon0Digit(n);

return 0;

}

C

#include<stdio.h>

int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};

int lastNon0Digit(int n)

{

if (n < 10)

return dig[n];

if (((n/10) % 10) % 2 == 0)

return (6*lastNon0Digit(n/5)*dig[n%10]) % 10;

else

return (4*lastNon0Digit(n/5)*dig[n%10]) % 10;

}

int main()

{

int n = 14;

printf("%d",lastNon0Digit(n));

return 0;

}

Java

class GFG

{

static int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};

static int lastNon0Digit(int n)

{

if (n < 10)

return dig[n];

if (((n / 10) % 10) % 2 == 0)

return (6 * lastNon0Digit(n / 5)

* dig[n % 10]) % 10;

else

return (4 * lastNon0Digit(n / 5)

* dig[n % 10]) % 10;

}

public static void main (String[] args)

{

int n = 14;

System.out.print(lastNon0Digit(n));

}

Python3

dig= [1, 1, 2, 6, 4, 2, 2, 4, 2, 8]

def lastNon0Digit(n):

if (n < 10):

return dig[n]

if (((n//10)%10)%2 == 0):

return (6*lastNon0Digit(n//5)*dig[n%10]) % 10

else:

return (4*lastNon0Digit(n//5)*dig[n%10]) % 10

return 0

n = 14

print(lastNon0Digit(n))

C#

using System;

class GFG {

static int []dig = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};

static int lastNon0Digit(int n)

{

if (n < 10)

return dig[n];

if (((n / 10) % 10) % 2 == 0)

return (6 * lastNon0Digit(n / 5) *

dig[n % 10]) % 10;

else

return (4 * lastNon0Digit(n / 5) *

dig[n % 10]) % 10;

}

public static void Main ()

{

int n = 14;

Console.Write(lastNon0Digit(n));

}

PHP

<?php

$dig = array(1, 1, 2, 6, 4,

2, 2, 4, 2, 8);

function lastNon0Digit($n)

{

global $dig;

if ($n < 10)

return $dig[$n];

if ((($n / 10) % 10) % 2 == 0)

return (6 * lastNon0Digit($n / 5) *

$dig[$n % 10]) % 10;

else

return (4 * lastNon0Digit($n / 5) *

$dig[$n % 10]) % 10;

}

$n = 14;

echo(lastNon0Digit($n));

?>

Javascript

<script>

let dig = [1, 1, 2, 6, 4, 2, 2, 4, 2, 8];

function lastNon0Digit(n)

{

if (n < 10)

return dig[n];

if ((parseInt(n / 10, 10) % 10) % 2 == 0)

return (6 * lastNon0Digit(parseInt(n / 5, 10))

* dig[n % 10]) % 10;

else

return (4 * lastNon0Digit(parseInt(n / 5, 10))

* dig[n % 10]) % 10;

}

let n = 14;

document.write(lastNon0Digit(n));

</script>

Time complexity: O(log n)

Space complexity: O(log n)

A Simple Solution based on recursion having worst-case Time Complexity O(nLog(n)).

Approach:-

It is given that you have to find the last positive digit. Now a digit is made multiple of 10 if there are 2 and 5. They produce a number with last digit 0.

Now what we can do is divide each array element into its shortest divisible form by 5 and increase count of such occurrences.

Now divide each array element into its shortest divisible form by 2 and decrease count of such occurrences. This way we are not considering the multiplication of 2 and a 5 in our multiplication(number of 2’s present in multiplication result upto n is always more than number of 5’s).

Multiply each number(after removing pairs of 2’s and 5’s) now and store just last digit by taking remainder by 10.

Now call recursively for smaller numbers by (currentNumber – 1) as parameter.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void callMeFactorialLastDigit(int n, int result[], int sumOf5)

{

int number = n;

if (number == 1)

return;

while (number % 5 == 0) {

number /= 5;

sumOf5++;

}

while (sumOf5 != 0 && (number & 1) == 0) {

number >>= 1;

sumOf5--;

}

result[0] = (result[0] * (number % 10)) % 10;

callMeFactorialLastDigit(n - 1, result, sumOf5);

}

int lastNon0Digit(int n)

{

int result[] = { 1 };

callMeFactorialLastDigit(n, result, 0);

return result[0];

}

int main()

{

cout << lastNon0Digit(7) << endl;

cout << lastNon0Digit(12) << endl;

return 0;

}

C

#include <stdio.h>

void callMeFactorialLastDigit(int n, int result[], int sumOf5)

{

int number = n;

if (number == 1)

return;

while (number % 5 == 0) {

number /= 5;

sumOf5++;

}

while (sumOf5 != 0 && (number & 1) == 0) {

number >>= 1;

sumOf5--;

}

result[0] = (result[0] * (number % 10)) % 10;

callMeFactorialLastDigit(n - 1, result, sumOf5);

}

int lastNon0Digit(int n)

{

int result[] = { 1 };

callMeFactorialLastDigit(n, result, 0);

return result[0];

}

int main()

{

printf("%dn",lastNon0Digit(7));

printf("%d",lastNon0Digit(12));

return 0;

}

Java

import java.io.*;

class GFG {

public static void

callMeFactorialLastDigit(int n, int[] result,

int sumOf5)

{

int number = n;

if (number == 1)

return;

while (number % 5 == 0) {

number /= 5;

sumOf5++;

}

while (sumOf5 != 0 && (number & 1) == 0) {

number >>= 1;

sumOf5--;

}

result[0] = (result[0] * (number % 10)) % 10;

callMeFactorialLastDigit(n - 1, result, sumOf5);

}

public static int lastNon0Digit(int n)

{

int[] result = { 1 };

callMeFactorialLastDigit(n, result, 0);

return result[0];

}

public static void main(String[] args)

{

System.out.println(lastNon0Digit(7));

System.out.println(lastNon0Digit(12));

}

Python3

def callMeFactorialLastDigit(n, result, sumOf5):

number = n

if number == 1:

return

while (number % 5 == 0):

number = int(number / 5)

sumOf5 += 1

while (sumOf5 != 0 and (number & 1) == 0):

number >>= 1

sumOf5 -= 1

result[0] = (result[0] * (number % 10)) % 10

callMeFactorialLastDigit(n - 1, result, sumOf5)

def lastNon0Digit(n):

result = [ 1 ]

callMeFactorialLastDigit(n, result, 0)

return result[0]

print(lastNon0Digit(7))

print(lastNon0Digit(12))

C#

using System;

class GFG {

static void

callMeFactorialLastDigit(int n, int[] result,

int sumOf5)

{

int number = n;

if (number == 1)

return;

while (number % 5 == 0) {

number /= 5;

sumOf5++;

}

while (sumOf5 != 0 && (number & 1) == 0) {

number >>= 1;

sumOf5--;

}

result[0] = (result[0] * (number % 10)) % 10;

callMeFactorialLastDigit(n - 1, result, sumOf5);

}

static int lastNon0Digit(int n)

{

int[] result = { 1 };

callMeFactorialLastDigit(n, result, 0);

return result[0];

}

static void Main() {

Console.WriteLine(lastNon0Digit(7));

Console.WriteLine(lastNon0Digit(12));

}

Javascript

<script>

function callMeFactorialLastDigit(n, result, sumOf5)

{

let number = n;

if (number == 1)

return;

while (number % 5 == 0) {

number /= 5;

sumOf5++;

}

while (sumOf5 != 0 && (number & 1) == 0) {

number >>= 1;

sumOf5--;

}

result[0] = (result[0] * (number % 10)) % 10;

callMeFactorialLastDigit(n - 1, result, sumOf5);

}

function lastNon0Digit(n)

{

let result = [ 1 ];

callMeFactorialLastDigit(n, result, 0);

return result[0];

}

document.write(lastNon0Digit(7) + "</br>");

document.write(lastNon0Digit(12));

</script>

Time complexity :- O(N)

Space complexity :- O(1)

we used single element array (int[] result = {1}) instead of integer as Java is Strictly Pass by Value!. It does not allow pass by reference for primitive data types. That’s why I used a single element array so that the recursive function can change the value of variable(result here). If we would have taken (int result = 1) then this variable remain unaffected.

This article is contributed by Niteesh kumar & KaaL-EL. If you like GeeksforGeeks 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 GeeksforGeeks 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.

Last Updated :
29 Mar, 2023

Like Article

Save Article

Источник

Считаем факториал по модулю 10 просто перемножив все числа от 1 до N. Возникает проблема с последними нулями. Зная в какой степени в число войдёт 5 (2 войдет в большей степени), мы знаем количество последних нулей. Теперь, перед умножением на очередной множитель, будем делить его на 2 и на 5, пока он делится или пока количество делений на 2 и на 5 не достигнет количества нулей. Это решение за O(n).

Источник

Мой код не проходит проверку на время. Нужно уложиться в 0.2 секунды, но в итоге 6 из 20 тестов, мой код превышает лимит времени.
Даже если я меняю его без использования модуля math, с помощью цикла for, либо же рекурсии, все равно не проходит

import math
    n=int(input())
    a=math.factorial(n)
    f=a%10
    while f==0:
        a=a//10
        f=a%10
    print(f)

Единственный код который проходит тест по времени приведен ниже. Но этот код писал не я, поэтому я не особо понимаю логику действий, и тот кто написал его, тоже не в силах объяснить

n = int(input())
m = 0
f = 1
for i in range(1, n + 1):
    while i % 2 == 0:
        i //= 2
        m += 1
    while i % 5 == 0:
        i //= 5
        m -= 1
    f = f * i % 10
f = (f << m) % 10
print(f)

Я хотел бы разобраться со вторым кодом и понять алгоритм(имею ввиду к чему там остаток от деления на 2, на 5 и на 10), либо ускорить первый код, что бы он прошел тест по времени, если это возможно. Если кто то может помочь с чем либо из этого, буду благодарен!

Суть самой задачи: напишите программу определения последней ненулевой цифры факториала

Входные данные: Задано число n(1<=n<=32767)

Ограничение по времени 0.2 сек

Ограничение по памяти 64мб

Источник

#python #factorial

Вопрос:

Я пишу код для решения следующего вопроса о кодовых войнах: https://www.codewars.com/kata/5f79b90c5acfd3003364a337/train/python

Моя идея состоит в том , чтобы взять все целые 1 to n числа и взять последнюю цифру каждого из этих целых чисел (строка 0), умножить их вместе и вернуть «последнюю» ненулевую цифру результата:

 def last_digit(n):
    factorials = []
    factorials_n = 1
    for i in range(1,n   1):
        i = str(i)
        i = i[::-1]
        for j in i:
            if j == "0":
                break
            factorials.append(j)
            break              


    # at this point factorials contains the first non-zero integers of each integer in reverse
    for i in factorials:
        factorials_n = factorials_n * int(i)

    factorials_n = str(factorials_n)
    factorials_n = factorials_n[::-1]


    for i in factorials_n:
        if i != "0":
            return int(i)

Код проходит ряд тестов, но не 387 (returns 6, should be 2) выполняется для 1673 (returns 2 should be 4) и. Я пытался выполнять инструкции печати в качестве отладки, но код кажется прекрасным, возможно, в какой — то момент логика дает сбой- есть идеи?

1. Каков наименьший вход n, если результат неверен?

2. Вы проверили, что содержание factorials правильно? Я подозреваю, что это не так.

3. Вам нужно использовать математику, а не грубую силу.

4. Или, может быть, сначала грубая сила, чтобы найти явно правильное решение в качестве эталона, а затем математика, чтобы сделать его эффективным, оставаясь правильным.

5. @mkrieger1 для меньших значений n факториалы верны, поэтому я полагаю, что для больших они тоже верны!

Ответ №1:

Проблема здесь в логике. Поскольку вы отбрасываете все случаи, когда число заканчивается на 0, мы не приходим к правильному ответу.

Рассмотрим 2 х 8 х 30. Чтобы получить последнюю цифру факториала, достаточно было бы умножить последние цифры, но чтобы найти последнюю ненулевую цифру, вместо этого вам нужно вычислить 2 x 8 x 3.

Используя это решение в качестве справочного, вот что вы можете сделать:

 def last_digit(n):
    # factorials = []
    # factorials_n = 1
    last = 1
    d2 = 0
    for i in range(1,n   1):
       
        ii = i
        print(ii)
        while(ii%2==0):
            d2  =1
            ii = ii/2
        
        while(ii%5==0):
            d2 -=1
            ii = ii/5
        print(d2)
        last = (last * ii)
        print(last)
    
    for i in range(0,d2):
        last = (last *2)

    return int(last)

Ответ №2:

Ваш код проходит тесты для чисел до 24, он терпит неудачу при ненулевой цифре от 25! дает неправильный ответ, который продвигается вперед для последующих чисел.

А также мы можем просто использовать оператор по модулю, чтобы получить самую последнюю цифру вместо преобразования ее в строковый
пример: 1234 % 10 равно 4 (что является последней цифрой)

Мое решение:

 def last_digit(n):

    factorial = 1
    
    for i in range(1, n   1):
    
        # compute the factorial
        prod = factorial * i
        
        # keep dividing the product by 10 until the last digit is a !0 digit
        while prod % 10 == 0:
            prod = prod // 10
            
        # only store the last 3 digits of the computed product.
        # You can keep more digits to get accurate results for
        # when the numbers are higher than 10000
        factorial = prod % 1000
    
    # return the last digit
    return factorial % 10

Как я уже говорил ранее, когда последняя !0 цифра из 24! ( 6 ) умножается на 25, выводится 150, что после удаления 0 дает 5, но вместо этого должно быть 4. Следовательно, чтобы решить эту проблему, мы сохраняем по крайней мере последние 3 цифры вместо только последней цифры.

 Example:   6 * 25 =   150 => 5 (last !0 digit)
         936 * 25 = 23400 => 4 (last !0 digit)

PS: !0 = ненулевое значение

1. Я не уверен, что сохранение 3 вместо 1 цифры рано или поздно не приведет к такой же проблеме.

2. Это, конечно, столкнется с той же проблемой, но на данный момент будет работать для всех тестовых случаев, упомянутых в постановке проблемы

3. Привет, Ахмед, спасибо за решение, все это имеет смысл. Один вопрос: почему мы сохраняем три цифры, а не только 1? На мой взгляд, это не повлияет ни на какие дальнейшие умножения? (До тех пор, пока одна цифра, конечно, не равна 0 — и она не будет основана на вашем коде!)

4. Вы можете сохранить столько цифр, сколько захотите, но 3-это минимум, чтобы пройти все необходимые тесты в программе. Как я уже объяснял ранее, умножение на 3 цифры даст вам гораздо более точную ненулевую последнюю цифру, чем умножение только на 1 цифру. Аналогично, умножение на целое число(со всеми цифрами) даст вам более точный результат, чем при использовании только 3 цифр.

Источник

Вывести последнюю ненулевую цифру факториала

C++

C

Java

Python3

C#

PHP

Javascript

C++

C

Java

Python3

C#

Javascript

Вопрос:

Комментарии:

Ответ №1:

Ответ №2:

Комментарии:

Не пропустите также: