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 ...
- 143
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 ...
- 1,035
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 ...
- 345
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-...
- 1,022
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 ...
- 4,124
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},...
user830143
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},\...
user830143
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 ...
user830143
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},\...
user830143
3
votes
1
answer
159
views
Expected value of function applied to randomly constructed binary number
I recently came up with this question when playing around with binary numbers and tried coding up a solution to it:
Let $b$ be a string of 1s and 0s. Split the string into seperate parts such that the ...
- 31
1
vote
0
answers
71
views
Worst-case minimization of size of intersection of an offset set with a given set
Consider the set of first $N$ natural numbers i.e., $S_N$ = $\{1,2,3, \dots,N\}$. Let $S^k$ be a finite subset of $S_N$, where $|S^k|$ = $k$. We define another set $O$ whose elements $\in$ $\{0,1,2,\...
- 104
2
votes
1
answer
1k
views
Greedy algorithms: why does no optimal solution for smaller coins mean that the greedy algorithm must work?
I'm reading Competitive Programmer’s Handbook. They take the Euro to perform analysis on a greedy algorithm.
For example, if the coins are the euro coins (in cents)
{1,2,5,10,20,50,100,200} and n ...
- 149
2
votes
3
answers
209
views
Iterating over all squarefree composites $\lt L$
I need to iterate over all integers that are:
Composite
Squarefree
Smaller than a limit $L$
And see for each one if it has a certain property (in addition to these 3). Then I need to sum all such ...
- 1,022
2
votes
1
answer
163
views
Find two subsets with a common sum in two sequences
For a positive integer $n$ and two integer sequences $a_1,a_2...a_n$ and $b_1,b_2...b_n$ where $\forall i$, $a_i,b_i \in [1,n]$, I want to find two non-empty subsets, one in each sequence, with the ...
- 232
4
votes
1
answer
195
views
Combinations of red and black balls
Given $N$ Identical Red balls and $M$ Identical Black balls, in how many ways we can arrange them such that not more than $K$ adjacent balls are of same color.
Example : For $1$ Red ball and $1$ ...
- 41
0
votes
1
answer
64
views
Construct a positive decimal number of length $n$ or less that is divisible by $2^n-1$ for n in $Z^+_0$
I got this question on a discrete mathematics test and I no idea on how to solve it:
Create a method for constructing a positive decimal number of length $n$ or less with digits from set $\{0,1,8,9\...
1
vote
0
answers
57
views
What does the 8 stand for in the Cantor pairing function?
What does the "8" stand for in the Cantor pairing function (which assigns a natural number to each pair of natural numbers)?
Can I change it, or is it constant?
The other function for getting the ...
- 17
5
votes
2
answers
191
views
Pigeonhole principle based algorithm
I was trying to solve this problem.
http://olympiads.hbcse.tifr.res.in/olympiads/wp-content/uploads/2016/09/inmosol-15.pdf
INMO-2015 P6. From a set of $11$ square integers, show that one can choose ...
0
votes
1
answer
39
views
Groups with the same amount
Let there be an array of digits $ [0,0,1,1,2,2,\ldots,9,9] $, how many ways to split this array into two subarrays, so that the sum of numbers in the subarrays is different by a multiple of $11$?
...
- 1,074
1
vote
2
answers
216
views
Given an integer, how many ways can you divide into unequal portions
I have been thinking about this problem for a while but have been unable to formalize a complete answer.
Given an integer $n \geq 3$, how many different sets can you sum the integer elements in the ...
- 111
5
votes
2
answers
656
views
Construct $4 \times 4$ magic square with fixed "1"
The method I have found to generate $4\times 4$ magic squares gives me a result in which the number "1" is at of the corners of the square. How can we extend this to a method to generate a magic ...
- 2,760
1
vote
1
answer
168
views
Generative function for Goldbach's conjecture
I have written a procedure that, given an integer n, it comes out the polynomial with its coefficients are prime and odd $\leq $ n
For example, procedure(5)= $x^{5}+x^{3}+x^{2}$, procedure(10)=$x^{7}+...
- 580
2
votes
2
answers
114
views
How to check if $k$ divides $\binom {n - 1} {k - 1}$ cheaply?
I'm writing a computer algorithm to do binomial expansion in C#. You can view the code here; I am using the following identity to do the computation:
$$
\dbinom n k = \frac n k \dbinom {n - 1} {k - 1}...
- 353
1
vote
0
answers
57
views
Number of subsets with constraint
How many subsets $P$ of $\{1, 2, ..., n\}$ are there such that if $x$ belongs to $P$ then $2x$ and $3x$ don't belong to $P$? For example, if $n = 4$ then there are $8$ such subsets (empty subset + $\{...
- 1,591
2
votes
0
answers
86
views
Find subset of size $k$ such that it maximizes the metric distance of the elements.
Suppose I have a set $A=\{a_1,a_2,...,a_n\}$ and a metric $f$ on $A$. I want to extract a subset $B$ of size $k$ such that it maximizes the sum of the distances between every possible pair in B. i.e. ...
- 2,457
0
votes
1
answer
79
views
Maximizing sum of metric function on a set (Adaptation of Hungarian Algorithm)
Suppose I have a set of unique elements $A=\{a_1, a_2, ..., a_n\}$. Suppose I also have a metric function $f:A\times A \rightarrow R^+$. I want to choose $k$ elements from $A$ (i.e. $a_{i_1},a_{i_2}, ....
- 2,457
1
vote
2
answers
465
views
Finding number of Coprime tuples from $1$ to $N$
Given $N$ Integers $A_1,A_2....A_N$, and a function $$F(i,j)=A_i*A_j mod P$$
$P =599*601$ both of which are prime.
I need to find out the number of integer 4-tuples $(a, b, c, d)$ there are such ...
- 113
2
votes
0
answers
514
views
Number of arrays with adjacent elements coprime?
An array of integers is called m-coprime if the following conditions are both satisfied:
All the integers in the array are positive divisors of m.
Each pair of adjacent elements in the array is ...
- 29
3
votes
1
answer
309
views
Algorithm to partition a multiset into $K$ equal sized multisets
How can I partition a multiset of integers, $A$, of size $N=MK$, into $K$ equal-sized multisets, $G_1,G_2,\ldots,G_K$, such that $\sum_i \mathrm{\lvert \min(G_i)\rvert}$ is maximized? Here, $\min(G)$ ...
- 53
1
vote
2
answers
496
views
In AB + BC + AC = N, how can I find all possibilities for A, B and C in less than n³ computational time?
The problem is the one on the title. Given a N, find all possibilies for A, B and C that make this true: $AB+BC+AC = N$when $A \ge B \ge C$.
This code in C do the job:
...
- 123
7
votes
1
answer
830
views
Alice and Bob make all numbers to zero game
Alice and Bob are playing a number game in which they write $N$ positive integers. Then the players take turns, Alice took first turn.
In a turn :
A player selects one of the integers, divides it ...
- 235
1
vote
4
answers
669
views
Is there any Algorithm to Write a Number $N$ as a Sum of $M$ Natural Numbers?
I have a number $N$ (for example $N=64$).
Is there any algorithm to find all the feasible ways for writing the number $N$ as a sum of $M$ positive numbers?
(For example $M=16$) --- Repetition is ...
- 2,123
2
votes
1
answer
3k
views
Count arrays with each array elements pairwise coprime
Given two integers $N$ and $M$ , How to find out number of arrays A of size N, such that :
Each of the element in array, $1 ≤ A[i] ≤ M$
For each pair i, j ($1 ≤ i < j ≤ N$)
$GCD(A[i], A[j]) = 1$...
- 235
1
vote
1
answer
1k
views
Alice and bob xor nim game
Alice and Bob are playing a game. The rules of this game are as follows:
Initially, there are $N$ piles of stones, numbered $1$ through $N$. The i-th pile contains $A[i]$ stones.
The players take ...
- 235
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
Using Backtracking Algorithm to determine all the subsets of integers
I'm asked to use the backtracking algorithm to determine all the subsets of integers whose sum is equal to 'w'(Lower case)
In this case I'm given that:
where a set of postive ...
- 159
2
votes
1
answer
2k
views
How to check if any subset of a given set of numbers can sum up to a given number
Given a number, say $x$, and a set of numbers made up of only $k$ different numbers, where each of the $k$ numbers is repeated $n_1,n_2,\dots n_k$ times. How do I tell if it is possible to find a ...
- 121
0
votes
1
answer
1k
views
Finding number of subarrays not including certain pairs
How many contiguous subarrays of an array exist such that they do not contain certain pairs of positions of the array?
For eg. if array ={11,22,33,45}
and if we do not want to include say position ...
- 133
4
votes
1
answer
2k
views
Expected value when die is rolled $N$ times
Suppose we have a die with $K$ faces with numbers from 1 to $K$ written on it, and integers $L$ and $F$ ($0 < L \leq K$). We roll it $N$ times. Let $a_i$ be the number of times (out of the $N$ ...
- 235
3
votes
1
answer
267
views
A result of Erdos: the multiplicative persistence of $n$ is at most $c\ln(\ln n)$
Multiply all the digits of a number $n$ by each other, repeating with the product until a single digit is obtained. The number of steps required is known as the multiplicative persistence of $n$.
...
- 5,824
1
vote
1
answer
208
views
Count connected components after $M$ marbles removed
There are $N$ marbles in a line, numbered $1$ through $N$ from left to right. We need to count numbers of ways to remove exactly $M$ marbles such that there are exactly $C$ remaining connected ...
- 27
0
votes
2
answers
80
views
Count bulbs in ON state [duplicate]
A room has N (1 to N inclusive) bulbs and N switches. N people go in one by one. 1st person goes in and toggles none of the switches. 2nd person goes in and toggles all switches other than the ...
- 129
1
vote
0
answers
67
views
Count good numbers that are multiple of 7 upto M
Given a number of $N$ digits with $A[1]$ denoting the first digit , $A[2]$ second digit and $A[n]$ last digit from left to right. It is called good number if
...
- 129
0
votes
1
answer
193
views
count subsets with given constraints
We are given N elements . We need to count number of such subsets that satisfy following conditions :
If ith element is present then (i-1) and (i+1) can't be present.
Additon of any of the other ...
- 23
0
votes
1
answer
218
views
Find largest number that satisfy given constraints
Let's define $F(x)$ for positive integer $x$ as a product of factorials of its digits. For example, $F(135) = 1!*3!*5!=720$
Now Given a decimal number $A$ consisting of $N$ digits that contains at ...
- 245