В вопросе говорится, что вам дано число N, и вы должны разбить это число на k-значное число, при вычислении которого сумма этих k-значных чисел будет равна N.
Приведенный выше вопрос можно решить различными способами.
//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)
20.08.2023 18:21
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в 2023-2024 годах? Или это полная лажа?".
20.08.2023 17:46
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
19.08.2023 18:39
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в частности, магию поплавков и гибкость flexbox.
19.08.2023 17:22
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для чтения благодаря своей простоте. Кроме того, мы всегда хотим проверить самые последние возможности в наших проектах!
18.08.2023 20:33
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий их языку и культуре.
14.08.2023 14:49
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип предназначен для представления неделимого значения.