Hello Everyone,
I am back. I shall continue posting a few more questions. I would like to point out that most of these questions have not been made up by me; they have been flicked from wonderful sources :)
--------------------------------------------------------------------------------------------------------------
Q. Why is the size of an empty class not zero?
Ans. This is basically to ensure that the addresses of two difference objects will be different. Go here to read more about this.
--------------------------------------------------------------------------------------------------------------
Q. Rama has n cigarettes. He smokes them one by one keeping the butts as he smokes. Once he has k butts, he can roll over a new cigarette. Given n and k, how many cigarettes can he smoke?
Ans. For example if n = 29 and k = 8, then lets says peter can smoke x cigarettes. x=29+(extra). Now peter has 29 butts. He needs 8 butts for a cigarette. So he can smoke 3 cigarettes more(29/8); x=32. He used 24 butts for 3 cigarettes. So he has 5 butts left out. Also, the 3 cigarettes that he smoked(extra). So he has 8 butts and thus he smokes one more. So x=33. Now he has one butt left out and he cannot do anything with that. So basically he smokes 33 cigarettes.
One could easily write an iterative algorithm. But here I shall show a really nice way of solving this problem. The recurrence relation is pretty straightforward and simple.
N = n + f(n,k)
f(n,k) = n/k + f(n%k + n/k , k)
If expanded, f(n,k)
= n/k + ((n/k)+(n%k))/k + (((n/k)+(n%k))/k+((n/k)+(n%k))%k)/k + ...
= n/k + n/k^2 + (n%k)/k + n/k^3 + (n%k)/k^2 + ...
We know that (n%k)/k is 0 because a/b here refers to the floor value of a/b. So we have...
f(n,k) = n/k + n/k^2 + n/k^3 + n/k^4 + ...
Therefore f(n) = Sigma n/(k^t) where t = {t | k^t <= n} f(n,k) = n/k*(1/k^t - 1)/(1/k - 1) = n/k*((1-k^t)/k^t)/((1-k)/k) = n * (k^t -1) / (k^t * (k-1)) Now k^t is less than or equal to n. Therefore f(n,k) = (n-n/k^t)/(k-1) Since k^t is less than or equal to n, n/k^t =1. Therefore f(n,k) = (n-1)/(k-1) . Let me illustrate the formula with the above example itself. n = 29 and k = 8. Answer = n + (n-1)/(k-1) = 29 + (29-1)/(8-1) = 33. --------------------------------------------------------------------------------------------------
Q. Given a number n, find the nth number f(n) whose cube ends in 888. (192 is the first number whose cube ends in 888). f(n) must be found in O(1).
Ans. It is said that the cube ends in 888. Without any loss of generality:- n^3 = 1000y + 888 (Note that 1000y + 888 is a number whose cube ends in 888) We know if the cube of a number ends in 888, then the number ends in 2. Therefore, (10x+2)^3 = 1000y + 888 (Now we need to find x and append a 2 at the end)
8(5x+1)^3 = 1000y + 888
(125x^3 + 75x^2 + 15x + 1) = 125y + 111 (dividing above equation by 8)
125x^3 + 75x^2 + 15x = 125y + 110
125x^3 + 75x^2 + 15x = 125y + 125 - 15
75x^2 + 15x + 15 = 125y + 125 - 125x^3
75x^2 + 15x + 15 = 125(y+1-x^3)
75x^2 + 15x + 15 = 125k (A multiple of 125)
15(5x^2 + x + 1) = 125k
3(5x^2 + x + 1) = 25k
3 * something is a multiple of 25, therefore clearly, something = multiple of 25
5x^2 + x + 1 = 25k
Let x=25t+r (r is between 0 and 24)
Substituting for x, we will get
5r^2 + r + 1 = 25k
So we need to find r between 0 and 24, which when substituted in 5r^2 + r + 1, would yield a multiple of 25. By trial, we get r as 19.
Therefore x = 25t + 19
The final algo would look like:-
INPUT n
x = 25(n-1) + 19
x = (x*10) + 2 //append a 2 at the end
OUTPUT x
I am back. I shall continue posting a few more questions. I would like to point out that most of these questions have not been made up by me; they have been flicked from wonderful sources :)
--------------------------------------------------------------------------------------------------------------
Q. Why is the size of an empty class not zero?
Ans. This is basically to ensure that the addresses of two difference objects will be different. Go here to read more about this.
--------------------------------------------------------------------------------------------------------------
Q. Rama has n cigarettes. He smokes them one by one keeping the butts as he smokes. Once he has k butts, he can roll over a new cigarette. Given n and k, how many cigarettes can he smoke?
Ans. For example if n = 29 and k = 8, then lets says peter can smoke x cigarettes. x=29+(extra). Now peter has 29 butts. He needs 8 butts for a cigarette. So he can smoke 3 cigarettes more(29/8); x=32. He used 24 butts for 3 cigarettes. So he has 5 butts left out. Also, the 3 cigarettes that he smoked(extra). So he has 8 butts and thus he smokes one more. So x=33. Now he has one butt left out and he cannot do anything with that. So basically he smokes 33 cigarettes.
One could easily write an iterative algorithm. But here I shall show a really nice way of solving this problem. The recurrence relation is pretty straightforward and simple.
N = n + f(n,k)
f(n,k) = n/k + f(n%k + n/k , k)
If expanded, f(n,k)
= n/k + ((n/k)+(n%k))/k + (((n/k)+(n%k))/k+((n/k)+(n%k))%k)/k + ...
= n/k + n/k^2 + (n%k)/k + n/k^3 + (n%k)/k^2 + ...
We know that (n%k)/k is 0 because a/b here refers to the floor value of a/b. So we have...
f(n,k) = n/k + n/k^2 + n/k^3 + n/k^4 + ...
Therefore f(n) = Sigma n/(k^t) where t = {t | k^t <= n} f(n,k) = n/k*(1/k^t - 1)/(1/k - 1) = n/k*((1-k^t)/k^t)/((1-k)/k) = n * (k^t -1) / (k^t * (k-1)) Now k^t is less than or equal to n. Therefore f(n,k) = (n-n/k^t)/(k-1) Since k^t is less than or equal to n, n/k^t =1. Therefore f(n,k) = (n-1)/(k-1) . Let me illustrate the formula with the above example itself. n = 29 and k = 8. Answer = n + (n-1)/(k-1) = 29 + (29-1)/(8-1) = 33. --------------------------------------------------------------------------------------------------
Q. Given a number n, find the nth number f(n) whose cube ends in 888. (192 is the first number whose cube ends in 888). f(n) must be found in O(1).
Ans. It is said that the cube ends in 888. Without any loss of generality:- n^3 = 1000y + 888 (Note that 1000y + 888 is a number whose cube ends in 888) We know if the cube of a number ends in 888, then the number ends in 2. Therefore, (10x+2)^3 = 1000y + 888 (Now we need to find x and append a 2 at the end)
8(5x+1)^3 = 1000y + 888
(125x^3 + 75x^2 + 15x + 1) = 125y + 111 (dividing above equation by 8)
125x^3 + 75x^2 + 15x = 125y + 110
125x^3 + 75x^2 + 15x = 125y + 125 - 15
75x^2 + 15x + 15 = 125y + 125 - 125x^3
75x^2 + 15x + 15 = 125(y+1-x^3)
75x^2 + 15x + 15 = 125k (A multiple of 125)
15(5x^2 + x + 1) = 125k
3(5x^2 + x + 1) = 25k
3 * something is a multiple of 25, therefore clearly, something = multiple of 25
5x^2 + x + 1 = 25k
Let x=25t+r (r is between 0 and 24)
Substituting for x, we will get
5r^2 + r + 1 = 25k
So we need to find r between 0 and 24, which when substituted in 5r^2 + r + 1, would yield a multiple of 25. By trial, we get r as 19.
Therefore x = 25t + 19
The final algo would look like:-
INPUT n
x = 25(n-1) + 19
x = (x*10) + 2 //append a 2 at the end
OUTPUT x
1 comments:
Thanks ...
Post a Comment