maitrasagnik
Right off the assembly line
A mathematician named Hardy had a paper with a list of numbers. His 5 year old son tore one half of the paper to make an aeroplane. When Hardy came across the torn piece of paper, he could not remember what the numbers meant. He tried to figure out the significance of the numbers but found that many numbers had only the initial portion and that the end portion was completely lost. Some numbers were unharmed and Hardy quickly figured out that they were powers of 2. He wanted to verify whether the incomplete numbers were also powers of 2. He selected a few numbers where the damage was the worst -- the digits missing were more than the available digits. In other words, the number of missing digits would be *at least* one more than the number of available digits.
You have to help Professor Hardy by writing a program, which does the following: for a given a number, find the next highest power of 2 with the same starting digits as the input. If the input has 2 digits, the original number would have at least 3 more digits (i.e., the output number will have at least 2 + 3 digits).
For example, if the input is 1, then the original number had at least 3 digits and started with ‘1’, i.e., the number must have been 128. If the input is 10, the original number must have been 1048576 (and not 1024, since the original number should have at least 5 digits and the next available power of 2 that starts with ‘10’ happens to be 1048576).
The output of the program should be the exponent of the original number. (If the original number is 128 = 2^7, then the output should be 7. If the original number is 1048576 = 2^20, then the output should be 20.)
If there are no matching powers of 2, the output should be "No solution". (Assume that all the original numbers could be represented by 4 bytes.)
The program must be able to take one or more files each containing numbers (one in each line) and find and print the corresponding output for each number on stdout. The output must be sorted numerically according to the input numbers.
HERE ARE SOME IMPORTANT REQUIREMENTS YOUR SOLUTION SHOULD “STRICTLY” ADHERE. AN IMPLEMENTATION WILL BE DISQUALIFIED IF IT DOES NOT MEET THESE REQUIREMENTS. PLEASE PAY ENOUGH ATTENTION, AND DO NOT ATTEMPT THIS QUESTION IF YOUR SOLUTION CANNOT MEET THESE REQUIREMENTS
Basic tests: Your program should pass at the least, the following test cases in order to qualify for further testing. So, please consider the following as the "basic" test-cases that the program should pass as a minimum requirement:
- input file has one or more numbers, output should be sorted
- multiple input files, output should be sorted
Boundary conditions: That apart, the program should work properly for the following boundary conditions:
- input file is not present (program shouldn’t crash/hang)
- input file is empty (program shouldn’t output anything, and shouldn’t crash/hang)
- input file has an arbitrarily long number (the program shouldn’t crash/hang)
- input file has negative numbers (ignore such numbers for processing)
Important: Provide a brief comment on top of your source code on what you think is the bottleneck (if any) when it comes to the performance aspect of your code.
Output format: Please have your output conform to the below requirement:
<input no> - <output no>
Each line should have the <input number>, followed by a <blank space>, followed by a <hyphen>, followed by a <blank space>, followed by the <output number>.
Portability considerations:
Your program should be portable. For example, do not use headers like conio.h and calls like itoa() that are not available on all platforms.
You have to help Professor Hardy by writing a program, which does the following: for a given a number, find the next highest power of 2 with the same starting digits as the input. If the input has 2 digits, the original number would have at least 3 more digits (i.e., the output number will have at least 2 + 3 digits).
For example, if the input is 1, then the original number had at least 3 digits and started with ‘1’, i.e., the number must have been 128. If the input is 10, the original number must have been 1048576 (and not 1024, since the original number should have at least 5 digits and the next available power of 2 that starts with ‘10’ happens to be 1048576).
The output of the program should be the exponent of the original number. (If the original number is 128 = 2^7, then the output should be 7. If the original number is 1048576 = 2^20, then the output should be 20.)
If there are no matching powers of 2, the output should be "No solution". (Assume that all the original numbers could be represented by 4 bytes.)
The program must be able to take one or more files each containing numbers (one in each line) and find and print the corresponding output for each number on stdout. The output must be sorted numerically according to the input numbers.
HERE ARE SOME IMPORTANT REQUIREMENTS YOUR SOLUTION SHOULD “STRICTLY” ADHERE. AN IMPLEMENTATION WILL BE DISQUALIFIED IF IT DOES NOT MEET THESE REQUIREMENTS. PLEASE PAY ENOUGH ATTENTION, AND DO NOT ATTEMPT THIS QUESTION IF YOUR SOLUTION CANNOT MEET THESE REQUIREMENTS
- The delivered solution should disable all 'trace' and 'debug' messages.
- The program should not hardcode the number of lines in the file in ANY manner. In other words, the program should keep dynamically allocating memory as it reads from the file. It could be by means of either realloc’ing or using a linked list. Under no circumstances, you could declare an array of some arbitrarily big size to hold the input numbers.
- The input file(s) will be passed via command-line arguments. The output of the program should go to ‘stdout’. The program should *not* hardcode the input file name.
- You MUST implement your functions for finding the power of a number or the exponent of a number using BITWISE operations; the solution should NOT make use of standard math library functions like pow() or use plain-multiplication / division to calculate the power.
Basic tests: Your program should pass at the least, the following test cases in order to qualify for further testing. So, please consider the following as the "basic" test-cases that the program should pass as a minimum requirement:
- input file has one or more numbers, output should be sorted
- multiple input files, output should be sorted
Boundary conditions: That apart, the program should work properly for the following boundary conditions:
- input file is not present (program shouldn’t crash/hang)
- input file is empty (program shouldn’t output anything, and shouldn’t crash/hang)
- input file has an arbitrarily long number (the program shouldn’t crash/hang)
- input file has negative numbers (ignore such numbers for processing)
Important: Provide a brief comment on top of your source code on what you think is the bottleneck (if any) when it comes to the performance aspect of your code.
Output format: Please have your output conform to the below requirement:
<input no> - <output no>
Each line should have the <input number>, followed by a <blank space>, followed by a <hyphen>, followed by a <blank space>, followed by the <output number>.
Portability considerations:
Your program should be portable. For example, do not use headers like conio.h and calls like itoa() that are not available on all platforms.
