tng
BAN USERHere's my code in C. Time complexity O(sqrt(n)), space complexity O(1). Uses the sqrt() function though.
bool
target_is_sum_of_two_squares(int target)
{
long square = 1;
for (int i = 1; square < target; i++, square = i*i) {
double complement_sqrt = sqrt(target - square);
if (complement_sqrt - (long)complement_sqrt == 0) {
printf("Found sum of two squares: %d = %d*%d + %ld*%ld.\n", target, i, i, (long)complement_sqrt, (long)complement_sqrt);
return true;
}
}
return false;
}
Help me understand here. You have a million entries stored in a tape, and the tape *HAS TO BE* read serially as the tape is scanned by the read-head. How would you optimize that? Regardless you do it or not, does that reduce the complexity of the task? I don't think so. It's still going to be O(n).
- tng February 02, 2013I hope I'm missing something here. If not, the answer seems pretty straightforward. We scan each element one-by-one (this has to be done regardless since the information on the tape is not stored in a particular order) and maintain a current minimum with lowest straight-line distance encountered so far. At the end of the scanning process, the nearest location remains in the current minimum. As for data structure, we can use something like the following.
struct data{
point myloc; //my current location (a,b)
point currentmin; //closest restaurant encountered so far
int distance; //distance from myloc to currentmin
};
RAND_MAX is a library-dependent variable, therefore, the result may change from machine to machine. While it's guaranteed to be at least 32767, on my laptop, it's 2147483647 (almost half of the max value for an unsigned int). Even in my case, there won't be any overflow as even a and b hit the max, c will be 2^32-2.
Hence, in most cases, overflow won't occur as the value of RAND_MAX is too low for c to overflow (again, this depends on your RAND_MAX value). Therefore, there's a high chance for c to always be greater than a and b.
I did the following. Assuming the time complexity of sorting is O(n log n), the algorithm runs in O(n log n). However, it requires additional space for the string array.
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;
void SortMax(int* arr, int len);
bool StringCompare(string s1, string s2);
string toString(int val);
int main()
{
int arr[5] = {4, 94, 9, 14, 91};
int len = 5; //sizeof(arr)/sizeof(int);
cout<<"Original array"<<endl;
for(int i = 0; i < len; i++)
cout<<arr[i]<<" ";
cout<<endl;
SortMax(arr, len);
cout<<"Sorted array"<<endl;
for(int i = 0; i < len; i++)
cout<<arr[i]<<" ";
cout<<endl;
}
void SortMax(int* arr, int len)
{
string strarr[len];
for(int i = 0; i < len; i++)
strarr[i] = toString(arr[i]);
std::sort(strarr, strarr+len, StringCompare);
for(int i = 0; i < len; i++){
arr[i] = atoi(strarr[i].c_str());
}
}
bool StringCompare(string s1, string s2)
{
if(atoi((s1 + s2).c_str()) > atoi((s2 + s1).c_str()))
return true;
else
return false;
}
string toString(int val)
{
stringstream ss;
ss<<val;
return ss.str();
}
@sachin, the moment you sort, the notion of subarray is gone (unless you record the original index somewhere). Your code will work if the question asked for the minimum "subset" instead of subarray...
- tng December 19, 2017