Найти суму чисел которые входят в диапазон между двумя числами

Question

Как найти суму чисел которые входят в диапазон между двумя числами? Суть задания: пользователь вводит два числа, затем программа находит между этими двумя числами, только те числа, которые имеют разные цифры. Нужно вывести сумму этих чисел которые входят у промежуток(вывод промежутка с числами есть у коде).

Фрагмент кода в который нужно это добавить:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, m, k = 0, p = 0, flag, i = 0, j, dig[10];
    do
    {
        printf("Enter m and n (m < n):\n");
        scanf("%d %d", &m, &n);
        if (m < n)
        {
            break;
        }
        else
            printf("\Error- m > n! Try again.\n\n");
    } while (k == 0);

    //printf("The sum of numbers in the interval [%d, %d] are:\n" );
    printf("Numbers in the interval [%d, %d] are:\n", m++, n--);
    for (k = m; k <= n; k++)
    {
        p = k;
        flag = 0;
        dig[i] = 0;
        i = 0;
        if (p < 10)
        { 
            continue;
        }   
        while (p > 0)
        { 
            dig[i] = p % 10;
            p = p / 10;
            i++;
        }
        dig[i] = -1;
        for (i = 0; dig[i] > -1; i++)
        { 
            for (j = i + 1; dig[j] > -1; j++)
            { 
                if (dig[i] == dig[j])
                { 
                    flag = 1;
                }
            }
        }

        if (flag == 0)
        {
            printf("%d\t", k);
        }
    }

    return 0;
}

Answer 1

#include <iostream>

using namespace std;

bool dif(int k) {
    int dig[10] = {0};

    while (k) {
        dig[k % 10]++;
        k /= 10;
        }

    for (int i = 0; i < 10; ++i)
        if (dig[i] > 1) return false;

    return true;
    }

int main() {
    int m, n, sum = 0;
    cin >> m >> n;

    for (int k = m; k <= n; k++) {
        if (dif(k)) sum += k;
        }

    cout << sum;
    }

Answer 2

Это интересная комбинаторная задача, я хочу её решить, пусть и четыре год спустя.

Найдём сумму чисел у которых фиксировано количество цифр и некоторый префикс. Например PPPPPXXXXX, где символ P обозначает цифры префикса, символ X – цифры суффикса. Пусть k – длина суффикса, n количество цифр для помещения в суффикс. Количество чисел такого формата равно числу размещений из n по k: A_n^k.

Суммировать их будем по разрядам. Сумма всех префиксов PPPPP·10^k·A_n^k.

Фиксируем значение и позицию одной цифры: PPPPPXXXDX, где D фиксированная цифра на позиции m (0 ≤ m < k). Таких чисел A_n-1^k-1, вклад одной цифры в одном числе D·10^m. Общая сумма D·10^m·A_n-1^k-1. Сумма по всем позициям m: D·(^{(10^k - 1)}/₉)·A_n-1^k-1. Множитель в середине – репьюнит из k единиц.

До сих под учтён вклад только одной конкретной цифры. Вклад всех цифр суммируется:
(^{(10^k - 1)}/₉)·A_n-1^k-1·∑{D}, где ∑{D} – сумма всех цифр, которые могут попасть в суффикс.

Общая сумма с префиксом и суффиксами:
PPPPP·10^k·A_n^k + (^{(10^k - 1)}/₉)·A_n-1^k-1·∑{D}

Все элементы этой формулы однозначно определяются префиксом PPPPP и длиной суффикса k:

множество цифр суффикса ({D}) определяется цифрами префикса;
n – число возможных цифр в суффиксе, то есть |{D}|.

Обозначим сумму всех чисел с префиксом PPPPP и суффиксом из k цифр как s(PPPPP, k).

Тогда сумма всех чисел меньших 10^m есть t(m) = t(m - 1) + ∑_1≤d≤9 s(d, m - 1).

Первое слагаемое отвечает за числа [0, 10^m-1). Второе слагаемое складывает числа в диапазонах [d·10^m-1, (d + 1)·10^m-1), где d пробегает все цифры, кроме нуля.

TODO: завершить теорию, добавить код.

БЛОГ НА HUSL

Найти суму чисел которые входят в диапазон между двумя числами

Ответы (2 шт):