Разбейте число Integer(int) на любое разрядное число так, чтобы сумма цифр была равна...

Разбить число Integer(int) на любое разрядное число так, чтобы сумма цифр была равна числу на Java

Q. Дано очень большое число N, разбейте его на r целых чисел так, чтобы их сумма равнялась исходному числу, и найдите количество способов сделать это.

В вопросе говорится, что вам дано число N, и вы должны разбить это число на k-значное число, при вычислении которого сумма этих k-значных чисел будет равна N.

Приведенный выше вопрос можно решить различными способами.

1. С помощью циклов.

//Given a N = 8, break it into 3 whole numbers such that 
//they sum up to the original number and find the number of ways to do so

import java.io.*;

class GFG {
    public static void main (String[] args) {
       int n = 8;
        int num = 0;
        for (int i = 0; i <= n; i++){
            for (int j = 0; j <= n; j++){
                for (int k = 0; k <= n; k++){
                    if (i + j + k == n){
                        num++;
                    }
                }
            }
        }
       System.out.println("Total : " + num);
    }
}

//output ----- Total : 45

//Time Complexity - O(n^3)
//Space Complexity - O(1)

2. С помощью математики.

Чтобы решить ее с помощью математического подхода, нам сначала нужно знать о методе Беггера/ теореме о многочленах в перестановках и комбинациях. Метод нищего гласит

"Если у вас с собой N монет и есть k нищих, то сколькими способами вы распределите монеты?".

Решением вышеприведенного утверждения является -

Итак, давайте решать с помощью уравнения. Предположим, у вас есть 3 нищих и у вас есть 8 монет, тогда мы можем распределить монеты между этими 3 в - или, Предположим, вам дали число 8, тогда как разбить его на трехзначное число так, чтобы сумма цифр была равна числу -.

//Given a number N = 8, break it into 3 whole numbers such that 
//they sum up to the original number and find the number of ways to do so

import java.io.*;

class GFG {
    public static void main (String[] args) {
      int n = 8;
      int k = 3;
      // (n+k-1)! / (k-1)!*(n)! = 10! / 2!*8!
      int num = (n+k-1)*(n+k-2) / 2;
      System.out.println("Total number of "+k+" digit number having sum equal to "+n+" = "+num);
    }
}


//Output ---- Total number of 3 digit number having sum equal to 8 = 45

//Time Complexity - O(1)
//Space Complexity - O(1)