# Tagged Questions

16 views

### Minimum moves to find the Ball in the Large Grid

Given N*M grid in which one cell contains a ball and all other cells are empty in all other boxes i am provided with one of these 8 directions towards the right position of ball.These are : ...
82 views

### Even or Odd for factorial

Moderator Note: This is a current contest question on codechef.com. Given $N$ and $M$ I need to tell whether $\left\lfloor \large\frac{N!}{M} \right\rfloor$ is even or odd.How to do this ...
17 views

### Check if sum is possible

Given a range $[L,R]$ I need to find weather a sum $S$ can be made by taking any number between this range i.e $L, L+1, L+2,\dotsc, R$ any number of times EXAMPLE: If $S=5$ and $L=2$ and $R=3$ then ...
25 views

### Maximise total amount

Suppose the price of car fluctuates each day, but on any single day the price is always the same. Suppose One person buy when the price was low and sell them when the price was high. But for each day ...
74 views

### Hockey Classics at Matheletics '13

I'm trying to solve a challenge from Matheletics '13: Micheal Nobbs is organizing a training camp for identifying new talents in Indian Hockey. The camp witnessed a total of ($3K+1$) players. Each of ...
31 views

### Last Digit Of N^M

Given $N,M$ What is the best way to find last digit of $N^M$ if both $N,M$ Can be as large as $10^{18}$? EXAMPLE : if $N=2$ and $M=4$ then answer would be $6$.
39 views

### Modify the Fibonacci series [duplicate]

We know that Fibonacci Numbers start with 0 and next element is 1 and F(n)=F(n-1)+F(n-2) to find nth term where n>=2 and F(0)=0 F(1)=1 . But what if we suppose the first 2 terms of fibonacci series ...
49 views

### Find more counterexample mathematically or algorithmically

Problem: Find integer $N$ such that it can NOT be expressed as $N=a^2+b^2+c^2$ or $N=a^2+b^2-c^2$ where integers $0<a^2,b^2,c^2\leq N$. For $N<100000$ there should be only 17 such integers. ...
77 views

### Count Numbers having $GCD$ equal to $X$

Given two integers $n,x$. Consider the interval $[l,r]$ with $l,r\in\mathbb Z$. I need to count the amount of numbers $y$ such that $l\leq y\leq r$ and $\gcd(n,y)=x$. For example if $n=10 ,x = 2$ and ...
28 views

### Minimum Number of piles

Suppose we have N stones. They have the same size and weight, but they might have different strength.The $i$-th stone can hold at most $x_i$ stones on its top (we'll call xi the strength of the ...
9 views

### Complete Maximum Number of tasks

Suppose I have 3 resources ( A,B and C).Now their are some tasks to be performed where each task require X amount of resource A ,Y amount of resource B and Z amount of resource C. At the begining I ...
83 views

### An alternate analysis to the (worst-case) run time of the euclidean algorithm

I was trying to figure out the running time of the euclidean algorithm. The analysis that I found on Wikipedia and CLRS both analyze the run time of the euclidean algorithm using the Fibonacci ...
63 views

### Moving the Robot

A robot is located on an infinite plane. At the beginning, the robot starts at the coordinates $(0, 0)$. The robot can then make several steps. The steps are numbered starting from $0$. In each ...
353 views

### Algorithms for Finding the Prime Factorization of an Integer

As practice, I am currently writing a program that takes a given integer $n$ as input, and then finds the (unique) prime factorization of $n$, provided $n$ is composite. My question is about ...
123 views

### Create a number by multi by $2$ and divide by $3$ (integer part)

How can I create a given postitive integer $N$ by multi by $2$ and divide by $3$ (integer part) ? (Write a computer program is allowed) For example: $$100 = 2*2*2*2*2*2*2*2*2*2*2/3/3/3/3*2*2$$ (The ...
64 views

$N$ students are to be provided with gifts We know that the $i$'th student wants to get at least $a_i$ gifts. The teacher wants to give distinct gifts meaning if he give $x$ gifts to one student then ...
58 views

### Light the Room Optimally

Suppose i have A candles.When I lights up a new candle, it first burns for an hour and then it goes out. I can make B went out candles into a new candle. As a result, this new candle can be used like ...
156 views

### Numbers permutation

Given $n$ numbers and $k$ positions I want the total number of permutations of these n numbers on these $k$ positions if repetition is allowed and if the following two arrangements are considered ...
116 views

### The number 3211000 is 7-special

Define a positive integer $k$ to be $n$-special if it satisfies the following properties: It has $n$ digits (0, 1, ..., 9) The 1st digit is equal to the number of 0's in the decimal representation ...
135 views

### When do repeated intervals of time overlap?

I have two time intervals A and B that occur in time at a start time and occur until an end time. These time intervals however repeat in time from their start time until another end time. So each ...
135 views

### Identifying Ways of Dividing an Area into Merged Regions

Suppose an area is divided into N irregular regions. Unless N is very small there will be many ways in which a new division of the area can be obtained by merging adjacent regions. I want to ...
96 views

### Euclidean Algorithm Question

So I have been asked to find $d=(a,b)$ when $a=1109$ and $b=4999$ and express $d$ as a linear combination of $a$ and $b$ Well I have worked out that $d=1$ but I am struggling to express $d$ as a ...
82 views

### Smallest integer which cannot be derived from set of numbers

Let's assume that I have k number of ns (e.g. 6,6 , k = 2 , n = 6) I'd like to find the ...
68 views

### Count of numbers with the given prime factors in a range [duplicate]

Given two primes: $p$ and $q$, $p \neq q$ and $n \in N$ find count of numbers $u$, so that $u \leq n$ and $u = p^k q^l$; $k, l \in N$. If we'd given with just one prime $p$ this count would be ...
67 views

### pair wise AND operation between two set of elements

I have two sets of size say $m$ and $n$. I wanted to find the sum of all pair-wise AND operation between the elements of both the sets. Suppose, if set $A=\{1,2,3\}$ and set $B=\{8,9\}$. I want to ...
42 views

### Calculating modular inverses with limited multiplication

Question Given $\alpha_1,\dots,\alpha_k \in \mathbb{Z}_n^\ast$, I want to compute $\alpha_1^{-1},\dots,\alpha_k^{-1}$ by computing only one multiplicative inverse and less than $3k$ multiplications ...
112 views

### Bound on total divisions of Euclid's Algorithm.

Question Suppose $\lambda$ is a positive integer and I want to show that there exists integers $a,b$ such that $a > b > 0$, $\lambda \geq \log_2b/\log_2\phi$, and Euclid's Algorithm on $a,b$ ...
266 views

### Find an algorithm to compute $(1! \cdot 2! \cdot3!\cdots n! ) \,\%\, x$.

You need to find the product of first n factorials $1! \cdot 2! \cdots n!$ modulo $109546051211.$ $1 \le n \le 10^7$. I need a fast algorithm for this.
54 views

### Improving Montgomery product

I am reading the paper "A Cryptographic Library for the Motorola DSP56000" (http://link.springer.com/content/pdf/10.1007%2F3-540-46877-3_21.pdf) which describes a trick to speed-up calculation of the ...
64 views

### $n$-Bit Strings Not Containing $010$

So, I am asked to consider the number of $n$-bit strings that don't contain $010$ by considering the following $m$-leading-zero cases for $m\geq 0$, where $m\in \mathbb{N}$: $1\cdots$ $01\cdots$ ...
103 views

### Paths Within a Lattice

So, I'm reading this proof: Lemma 4.2. The SchrÃ¶der numbers $(r(n):n\geq0))$ satisfy $$r(n)=r(n-1)+\sum_{k=0}^{n-1}r(k)r(n-1-k)\text{ for }n\geq1,\text{ with } r(0)=1$$ Proof. The SchrÃ¶der number ...
94 views

### Is the extended Euclidean algorithm optimal for computing modular inverses?

Is there an algorithm that can compute modular inverses in less than $O(n^{2})$? If not, is the Euclidean algorithm provably optimal?
111 views

### Minimum number of moves to equalize a list

Given a list of $n$ integers. In one move we can either decrease exactly one element by $1,2$ or $5$. What is the minimum number of moves required to equalize the list? For example: If the list is ...
426 views

168 views

### is there a relation between divisors(n) and divisors($n^2$)?
Can we generate divisors($n^2$) in case that we already have divisors(n) ? or at least can we predict how many integers are in divisors($n^2$) ? while divisors(n) is the list of integers (not ...