All Questions
9
questions
0
votes
0
answers
109
views
Binary sequences of length $N$ including all numbers upto $N$ [duplicate]
Consider numbers $n$ and $N = 2^n$ and define a binary sequence $b = [b_0,\dots,b_{N-1}]$, $b_i \in \{0,1\}$, to be complete or to include all numbers upto $N$ when for each number $0 \leq i < N$ ...
- 18.2k
3
votes
1
answer
119
views
When will the algorithm stop. While $a>0$, do if $a<b$ then $(a,b)\rightarrow (2a,b-a)$ else $(a,b)\rightarrow (a-b,2b)$
I came to this question in the Problem Solving Strategies.
We start with the state $(a,b)$ where $a,b$ are positive integers. To this initial sate we apply the following algoritm
While $a>0$, do if ...
- 31
3
votes
0
answers
86
views
Given $n\in\mathbb{N}_{\geqslant 2}$, find the partition $(a_1,...,a_k)\in\mathbb{N}^k:\sum_{i=1}^k a_i=n$ of $n$ that maximizes $\prod_{i=1}^k a_i$
I am a solving programming question in Leetcode in which, given a number $n \in \mathbb{N}_{\geqslant 2}$, I have to find $(a_1, ..., a_k) \in \mathbb{N}^k$ such that $k \in \mathbb{N}$, $2 \leqslant ...
2
votes
0
answers
101
views
Modification of the subset sum problem - "perfect coverage" of the set with good solutions
I have a problem.
We have a set.
$S = (a_1, a_2 ... a_k)$ and an integer $x$.
We know that there is a sum of elements to $x$ in it.
We also know that:
if there is only one sum to $x$ then it must ...
- 489
9
votes
2
answers
899
views
Product of sums of all subsets mod $k$?
Input: set of $N$ integers and $k$ value (modulo)
Output: product of sum of all subsets of input set (modulo $k$)
e.g. for input {1,2,3} and $k = 20$, we have 1 * 2 * 3 * (1+2) * (1+3) * (2+3) * (1+...
- 489
6
votes
2
answers
3k
views
Jugs of Water Puzzle: Minimum Number of Operations
PUZZLE. Given two water jugs with capacities $a, b \in \mathbb{N}$, the goal is to measure exactly $c$ units of water only performing the following operations:
fill one of the jugs to it's capacity ...
- 341
0
votes
1
answer
642
views
Trailing zeroes in product of numbers with factorial power
I need to find the number of trailing zeroes in $1^{1!} \cdot 2^{2!} \cdot 3^{3!} \cdots N^{N!}$, where $N$ is natural number.
Assuming $N$ is very large, say $500$, where you cannot find factorial ...
- 235
0
votes
1
answer
1k
views
Calculating nCr mod M using inverse multiplicative factors
The method used for calculating nCr mod M is:
fact[n] = n * fact[n-1] % M
ifact[n] = modular_inverse(n) * ifact[n-1] % M
And then nCr is calculated as
...
9
votes
4
answers
4k
views
calculating n choose k mod one million
I am working on a programming problem where I need to calculate 'n choose k'. I am using the relation formula
$$
{n\choose k} = {n\choose k-1} \frac{n-k+1}{k}
$$
so I don't have to calculate huge ...
- 315