All Questions
92
questions
0
votes
0
answers
48
views
Optimal Strategy for Identifying Lighter Balls: A Balance Scale Puzzle
There are n balls, among which m balls are lighter (and equally light with each other). We have a balance scale; how many times must we weigh at least, in order to find these m lighter balls? We ...
0
votes
2
answers
62
views
Finding the minimum value of K for non-repeated sums
Given a set $A$ containing 10 positive integers, with the largest element denoted as $K$, we calculate all possible sums of elements from set $A$, including sums of 2, 3, 4, and so on, up to all 10 ...
- 47.4k
0
votes
1
answer
1k
views
Project Euler Problem 338
I'm stuck on Project Euler problem 338. This is a cross post from StackOverflow where I initially posted, however, it was suggested that I post it here too since the problem mostly relies on math. The ...
CommunityBot
- 1
2
votes
2
answers
110
views
Counting integers $n \leq x$ such that $rad(n)=r$
Let $r$ be the largest square-free integer that divides $n$. Then $$r = \operatorname{rad}(n)=\prod_{\substack{p\mid n\\p\text{ prime}}}p$$ $r$ is called the "radical" of $n$, or the square-...
- 23
0
votes
1
answer
102
views
Subarray Sum Equals K - If the same prefix sum is encountered why does it follow 1,3,7,15,31 pattern?
This is an interesting property I have noticed in the problem:
Subarray Sum Equals K
The basic algorithm is as follows:
You start with calculating the prefix (running sum).
You check if the ...
- 145k
1
vote
0
answers
45
views
Counting the deduplicated list
You are given $2n$ positive integers $x_i, d_i$ ($1 \leq i \leq n$). Let $l := [x_1, 2x_1, ..., d_1x_1, x_2, 2x_2, ..., d_2x_2, ..., x_n, 2x_n, ..., d_nx_n]$. Let $s = set(l)$, i.e., the set by ...
- 1,008
0
votes
1
answer
223
views
Algorithm to compute number of combinations
I have to compute (m+n)!/(m!)(n!) where m>=n.
Due to overflow constraints, I cannot calculate (m+n)! as it might exceed size of variable (int). To overcome this difficulty, one solution is to do ...
- 3,772
1
vote
1
answer
366
views
Given an integer base 10, is there a known way of calculating how many 1s and 0s it has in binary without counting?
Example
Given the number $12045_{10}$,
how many 1s does it have in its binary representation?
how many 0s does it have in its binary representation?
Question
Is there a way of doing this that is ...
- 712
0
votes
0
answers
67
views
Greedy algorithm for variation of bin packing
Consider the bin packing problem where an input array of weights have to be packed in the minimum number of bins possible. Consider the two following restrictions. First, for any bin, a heavier weight ...
- 127
1
vote
0
answers
205
views
Find the number of compatibility relations of [n] containing k maximal irredundant set C n,k
Let [n] denote the set of n elements {1, 2, ... , n}. A relation on the set [n] is a subset of the Cartesian product [n] × [n]. Equivalence relations are relations that satisfy self-reflexivity, ...
- 11
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 ...
0
votes
0
answers
32
views
How to describe these combinatorial sets in general and prove their cardinality
The sets I am looking at are defined as follows: for $k=1$ the set is defined as:
$\Sigma_1:=\Big\{ \frac{1}{1},\frac{1}{3}\Big\}$
whereas for $k=2$ we have
$\Sigma_{2}:=\Big\{ \frac{1}{1},\frac{2}{1},...
CommunityBot
- 1
0
votes
1
answer
39
views
Combinatorial Minimization Problem for sets of rational numbers.
If we have the set
$\Bigg\{ \frac{1}{1},\frac{1}{2},\frac{1}{3},...,\frac{1}{k} \Bigg\}=:A$
for some $k\in \mathbb{N}$ (known). We pick some $a\in \mathbb{Q}$ such that we have
$\Bigg\{ \frac{a}{1},\...
- 15k
1
vote
1
answer
46
views
A combinatorial formula for different sums $a\cdot( k_1+ k_2+...+k_{n-1})+k_n$
I am looking for a combinatorial rule for the following: let $n \in \mathbb{N}$ and $k_1,k_2,...,k_n \in \mathbb{N}$ (these are known). Since we know what the sum $\sum_{j=1}^{n}k_i$ is, let's say ...
- 49.7k
1
vote
1
answer
89
views
How to determine the cardinality of this set?
I would like to determine the cardinality of this set (given that $a,b \in \mathbb{N}$ and we do not know which one is larger):
$\Big\{\frac{1}{1},\frac{2}{1},\frac{3}{1},...,\frac{a}{1},\frac{1}{2},\...
- 397k