biswamails
BAN USERAny number divisible by 2 & 5, must have '0' at it's unit's place.
so, the 'n'-th no. divisible by 2,3,5 must have '0' at it's units place.
And, a no. is divisible by 3, if sum of digits is 3 or is divisible by 3.
Here is the pattern for nos., divisible by 3:
3 6 9 12 15 18 21 24 27 30 ...
If you observe, the pattern starts repeating after every 10 numbers. we can put them in buckets
so we have
in bucket 0: 3 - 30
in bucket 1: 33 - 60
in bucket 2: 63 - 90
and so on.
Now to find the 'n'-th no. divisible by 2,3,5, we can use the above patterns and do the following:
bucket = n/10;
index_within_bucket=n%10;
the_number=(bucket*3*10 + index_within_bucket*3)*10;
/*
Assume the interviewer here expects to also have the merged array to stay sorted, after merge. Else, the problem is pretty straight forward.
*/
private static int[] Merge(int[] A, int[] B)
{
if(A==null || B==null || A.count==0 || B.count==0)
return A; // Nothing to do.
//Assume A has exact no. of empty spaces to Accomodate B, at the end.
int sizeFullA=A.count;
int sizeA=A.count - B.count; // A.size - element places for B at the end.
int sizeB=B.count;
int ptrA=sizeA-1; // Maintain 2 temporary ptrs for A & B starting from last element
int ptrB=sizeB-1;
for(int i=sizeFullA-1;i>=0&& ptrB>=0;i--)
{
if(
ptrA<0 || Copy over the B elements, if A is exhausted.
B[ptrB]>A[ptrA]) // If B the current element in B is larger, copy the B elemnt to i-index
{
A[i}=B[ptrB];
ptrB--;
}
else
{
A[i]=A[ptrA];
ptrA--;
}
}
return A;
}
@ugly: the question is 2,3 'and' 5.
- biswamails May 30, 2010the link talks about 2,3 'or' 5.