Adobe Interview Question
Applications DevelopersCountry: India
Interview Type: In-Person
for files with millions of numbers: this can be modified as: after adding the least significant 3 bits of the number to the sum, since we have to check only least significant 3 bits of the sum in the end, we can do and operation between sum and binary(111).
In that way, at any time, we have store at max number 7 in the variable sum.
Correct me if i am wrong!!!
If there is a possibility of overflow then we must do this step. It's correct to avoid overflow.
Find sum of the numbers in each file keeping in mind that at any time the sum < 8. If sum >= 8 then sum = sum %8. Now the final remainder if 0 will mean the sum of numbers is divisible by 8.
This will be optimized using the following logic. The operation num%8 will have a value greater than 0 only if the least significant 3 bits of a number are set. This is because of the fact that least significant 3 bits represent 2^0=1, 2^1=2 and 2^2=4. Any other bit that is set will be a multiple of 8 (8,16,32...) and will be useless for num%8 operation as the result will be always 0.
- tarutrehan June 07, 2012So we can just add the least significant 3 bits to the sum.
sum = 0;
while (!EOF)
{
sum += num&0x7;
}
if (sum & 0x07)
// not divisible by 8
else
// divisible by 8.
So basically we have removed the % operator and substituted it with the much faster bitwise operator &. Also since we are using only the lower order 3 bits for sum calculations the possibility of overflow is also less (until it's told that we are dealing with thousands of numbers in each file)