oxygen
BAN USERInterested in recursive programs, algorithms, information security, compression and computer graphics.
- » Resume
- 0of 0 votes
AnswersGiven two dices labeled 1 to 6. Take 1 dice and relabel it such that the sum of the two dice's is between 1 and 12. This sum occurs with equal probability. How will you relabel it ?
- oxygen| Report Duplicate | Flag | PURGE
Expedia Software Engineer / Developer Brain Teasers
p & p^2+8 are primes, if p not equal to 2.
p*(p^2 + 8) is not prime as it is factored into prime numbers......(p^3+p*8)
To make it prime, we need to convert p*8 into something not divisble by p,
We take 2 in this case. So, it makes (p^3+2^4) a prime....this cannot be factored furthur.
Can someone comment on the solution ?
i think with 3 additional similar size arrays, it might be possible to construct B.
array B1: Walk A, calculate B1[i] = a[i-1] * a[i+1] (should be O(n))
array B2: Walk A calculate B2[i] = B2[i-1] * a[i] (should be O(n))
array B3: Walk A calculate B3[n-i] = B3[n-i+1] * a[i] (should be O(n))
B[i] = B1[i] * B2[i-2] * B3[i+2]
basically, idea would be to exclude the number itself so construct B1 by doing that.
then keep multiplications from [0-(i-2)] and [i+2 to n] in B2 and B3. this shall leave the
item at i behind.
Note:- Solution given by a Friend of mine
Dear Anand,
- oxygen September 10, 2007Two observations:
1. Try solving for this example: B = 1 2, A = 1 3 2 3 2 2 2 1 2, with your solution.
when i = 0
for B[0] = 1, we get index 0 in sorted order, i.e. ANS[0] = 0
when i = 1
for B[1] = 2, we get index 2 in sorted order, i.e. ANS[1] = 2
Even if we tried doing insertion sort on ANS, we would end up with ANS[0] = 0, ANS[1] = 2
window l = 0, k = 2
Observe ! There is a better 'smaller' window 1 2 in the end.
So, why did you miss it ?
2. You are trying to sort within a loop. In that case, the time complexity should be geater than O(n^2), depending on the sorting algorithm.
This can be brought down to O(n^2) by using count sort, but how do you implement the same ?