Рубрики

Подсчитать числа в заданном диапазоне, чтобы сумма четных цифр была больше суммы нечетных цифр

Динамическое программирование, Математика

Даны два целых числа L и R, обозначающие диапазон [L, R]. Задача состоит в том, чтобы найти общее количество чисел в заданном диапазоне [L, R], сумма четных цифр которых больше суммы нечетных цифр.

Примеры:

Input : L=2 R=10
Output : 4
Numbers having the property that sum of even
digits is greater than sum of odd digits are: 2, 4, 6, 8

Input : L=2 R=17
Output : 7

Пререквизиты: Digit-DP

Подходить:
Во-первых, посчитайте необходимые числа до R, т.е. в диапазоне [0, R]. Чтобы получить ответ в диапазоне [L, R], решите для диапазона от нуля до R, а затем вычтите ответ для диапазона от нуля до L — 1. Определите состояния DP следующим образом:

  • Рассмотрим число как последовательность цифр, одно состояние — это позиция, в которой мы сейчас находимся. Эта позиция может иметь значения от 0 до 18, если мы имеем дело с числами до 10 ^ 18. В каждом рекурсивном вызове попытайтесь построить последовательность слева направо, поместив цифру от 0 до 9.
  • Первое состояние — это сумма четных цифр, которые были размещены до сих пор.
  • Второе состояние — это сумма нечетных цифр, которые были размещены до сих пор.
  • Другим состоянием является булева переменная Герметичность, которая сообщает, что число, которое мы пытаемся построить, уже стало меньше, чем R, так что в будущих рекурсивных вызовах мы можем поместить любую цифру от 0 до 9. Если число не стало меньше, максимальный предел цифра, которую мы можем поместить, является цифрой в текущей позиции в R.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ код для подсчета числа в диапазоне
// с большим количеством четных цифр
// чем сумма нечетных цифр
#include <bits/stdc++.h>

  
// как число может быть до 10 ^ 18
#define int long long

  

using namespace std;

  

vector<int> v;

  

int dp[18][180][180][2];

  

int memo(int index, int evenSum,

                      int oddSum, int tight)

{

    // Базовый вариант

  

    if (index == v.size()) {

        // проверяем, выполнено ли условие

        if (evenSum > oddSum)

            return 1;

        else

            return 0;

    }

  

    // Если этот результат уже вычислен

    // просто возвращаем

    if (dp[index][evenSum][oddSum][tight] != -1)

        return dp[index][evenSum][oddSum][tight];

  

    // Максимальный предел, до которого мы можем установить

    // цифра Если туго 0, значит номер имеет

    // уже стало меньше, чтобы мы могли разместить

    // любая цифра, иначе num [pos]

  

    int limit = (tight) ? v[index] : 9;

  

    int ans = 0;

  

    for (int d = 0; d <= limit; d++) {

        int currTight = 0;

  

        if (d == v[index])

            currTight = tight;

  

        // если текущая цифра нечетная

        if (d % 2 != 0)

            ans += memo(index + 1, evenSum,

                        oddSum + d, currTight);

  

        // если текущая цифра четная

        else

            ans += memo(index + 1, evenSum + d,

                        oddSum, currTight);

    }

  

    dp[index][evenSum][oddSum][tight] = ans;

    return ans;

}
// Функция для преобразования n в его
// цифровой вектор и использует функцию memo ()
// вернуть требуемое количество

int CountNum(int n)

{

    v.clear();

    while (n) {

        v.push_back(n % 10);

        n = n / 10;

    }

  

    reverse(v.begin(), v.end());

  

    // Инициализация DP

    memset(dp, -1, sizeof(dp));

    return memo(0, 0, 0, 1);

}

  
// Код драйвера

  
int32_t main()
{

    int L, R;

    L = 2;

    R = 10;

    cout << CountNum(R) - CountNum(L - 1) << "\n";

    return 0;

}

Джава

// Java-код для подсчета числа в диапазоне
// с большим количеством четных цифр
// чем сумма нечетных цифр

import java.util.*;

  

class GFG

{

  

    static Vector<Integer> v = new Vector<>();

  

    static int[][][][] dp = new int[18][180][180][2];

  

    static int memo(int index, int evenSum,

    int oddSum, int tight)

    {

        // Базовый вариант

  

        if (index == v.size()) 

        {

            // проверяем, выполнено ли условие

            if (evenSum > oddSum) 

            {

                return 1;

            } 

            else

            {

                return 0;

            }

        }

  

        // Если этот результат уже вычислен

        // просто возвращаем

        if (dp[index][evenSum][oddSum][tight] != -1) 

        {

            return dp[index][evenSum][oddSum][tight];

        }

  

        // Максимальный предел, до которого мы можем установить

        // цифра Если туго 0, значит номер имеет

        // уже стало меньше, чтобы мы могли разместить

        // любая цифра, иначе num [pos]

        int limit = (tight > 0) ? v.get(index) : 9;

  

        int ans = 0;

  

        for (int d = 0; d <= limit; d++) 

        {

            int currTight = 0;

  

            if (d == v.get(index)) 

            {

                currTight = tight;

            }

  

            // если текущая цифра нечетная

            if (d % 2 != 0) 

            {

                ans += memo(index + 1, evenSum,

                        oddSum + d, currTight);

            } // если текущая цифра четная

            else

            {

                ans += memo(index + 1, evenSum + d,

                        oddSum, currTight);

            }

        }

  

        dp[index][evenSum][oddSum][tight] = ans;

        return ans;

    }

    // Функция для преобразования n в его

    // цифровой вектор и использует функцию memo ()

    // вернуть требуемое количество

  

    static int CountNum(int n) 

    {

        v.clear();

        while (n > 0) 

        {

            v.add(n % 10);

            n = n / 10;

        }

  

        Collections.reverse(v);

  

        // Инициализация DP

        for (int i = 0; i < 18; i++)

        {

            for (int j = 0; j < 180; j++) 

            {

                for (int k = 0; k < 180; k++) 

                {

                    for (int l = 0; l < 2; l++)

                    {

                        dp[i][j][k][l] = -1;

                    }

                }

            }

        }

  

        return memo(0, 0, 0, 1);

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        int L, R;

        L = 2;

        R = 10;

        System.out.println(CountNum(R) - CountNum(L - 1));

  

    }

}

  
// Этот код предоставлен Принчи Сингхом

python3

# Python код для подсчета числа в диапазоне
# имея сумму четных цифр больше
# чем сумма нечетных цифр

  

def memo(index, evenSum, oddSum, tight):

  

    # Базовый вариант

    if index == len(v):

  

        # проверить, выполнено ли условие или нет

        if evenSum > oddSum:

            return 1

        else:

            return 0

  

    # Если этот результат уже вычислен

    # просто верни его

    if dp[index][evenSum][oddSum][tight] != -1:

        return dp[index][evenSum][oddSum][tight]

  

    # Максимальный предел, до которого мы можем установить

    цифра Если туго 0, значит номер имеет

    # уже стало меньше, чтобы мы могли разместить

    # любая цифра, иначе num [index]

    limit = v[index] if tight else 9

  

    ans = 0

  

    for d in range(limit + 1):

        currTight = 0

  

        if d == v[index]:

            currTight = tight

  

        # если текущая цифра нечетная

        if d % 2 != 0:

            ans += memo(index + 1, evenSum, 

                        oddSum + d, currTight)

  

        # если текущая цифра четная

        else:

            ans += memo(index + 1, evenSum + d, 

                            oddSum, currTight)

  

    dp[index][evenSum][oddSum][tight] = ans

    return ans

  
# Функция для преобразования n в его цифровой вектор
# и использует функцию memo () для возврата
# необходимое количество

def countNum(n):

    global dp, v

  

    v.clear()

    num = []

    while n:

        v.append(n % 10)

        n //= 10

  

    v.reverse()

  

    # Инициализировать дп

    dp = [[[[-1, -1] for i in range(180)] for j in range(180)]

        for k in range(18)]

    return memo(0, 0, 0, 1)

  
Код водителя

if __name__ == "__main__":

    dp = []

    v = []

  

    L = 2

    R = 10

    print(countNum(R) - countNum(L - 1))

  
# Этот код предоставлен
# sanjeev2552

C #

// C # код для подсчета числа в диапазоне
// с большим количеством четных цифр
// чем сумма нечетных цифр

using System.Collections.Generic;

using System;

  

class GFG

{

  

    static List<int> v = new List<int>();

  

    static int [,,,]dp = new int[18,180,180,2];

  

    static int memo(int index, int evenSum,

    int oddSum, int tight)

    {

        // Базовый вариант

  

        if (index == v.Count) 

        {

            // проверяем, выполнено ли условие

            if (evenSum > oddSum) 

            {

                return 1;

            } 

            else

            {

                return 0;

            }

        }

  

        // Если этот результат уже вычислен

        // просто возвращаем

        if (dp[index,evenSum,oddSum,tight] != -1) 

        {

            return dp[index,evenSum,oddSum,tight];

        }

  

        // Максимальный предел, до которого мы можем установить

        // цифра Если туго 0, значит номер имеет

        // уже стало меньше, чтобы мы могли разместить

        // любая цифра, иначе num [pos]

        int limit = (tight > 0) ? v[index] : 9;

  

        int ans = 0;

  

        for (int d = 0; d <= limit; d++) 

        {

            int currTight = 0;

  

            if (d == v[index]) 

            {

                currTight = tight;

            }

  

            // если текущая цифра нечетная

            if (d % 2 != 0) 

            {

                ans += memo(index + 1, evenSum,

                        oddSum + d, currTight);

            } // если текущая цифра четная

            else

            {

                ans += memo(index + 1, evenSum + d,

                        oddSum, currTight);

            }

        }

  

        dp[index,evenSum,oddSum,tight] = ans;

        return ans;

    }

      

    // Функция для преобразования n в его

    // цифровой вектор и использует функцию memo ()

    // вернуть требуемое количество

    static int CountNum(int n) 

    {

        v.Clear();

        while (n > 0) 

        {

            v.Add(n % 10);

            n = n / 10;

        }

  

        v.Reverse();

  

        // Инициализация DP

        for (int i = 0; i < 18; i++)

        {

            for (int j = 0; j < 180; j++) 

            {

                for (int k = 0; k < 180; k++) 

                {

                    for (int l = 0; l < 2; l++)

                    {

                        dp[i,j,k,l] = -1;

                    }

                }

            }

        }

  

        return memo(0, 0, 0, 1);

    }

  

    // Код драйвера

    public static void Main(String[] args) 

    {

        int L, R;

        L = 2;

        R = 10;

        Console.WriteLine(CountNum(R) - CountNum(L - 1));

  

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /

Выход:

4

Сложность времени: Максимум 18 * (180) * (180) * 2 вычислений при 0 <a, b <10 18

Рекомендуемые посты:

Подсчитать числа в заданном диапазоне, чтобы сумма четных цифр была больше суммы нечетных цифр

0.00 (0%) 0 votes