CareerCup

One kind of easy solution is check all numbers which within between minimum and maximum.

for(int i=1; i<=max; i++) {

if inside any interval
if out side of all interval



}

Time complexity : O(Log(N))

Search from Root to Leaf. if((fabs)(cur_node_left_val-input)>=(fabs)(cur_node_right_val-input)) then go to Left node Else got to Right node.

Answer is 0. Because all number that is between 1 and 345 must divide 345!

How to check?
1. Fermat Little Theorem
2. IsPrimeNumber function that is in Java BigInteger Library.

Prime numbers are unlimited.

inline void update(int u)
{
while(u<=n)
{
val[u]++;
u+=(u&-u);
}
}
inline int sum(int u)
{
int ret = 0;
while(u>0) {
ret += val[u]; u-=(u&-u);
}
return ret;
}
first step is using map change (a[1],a[2],.....,a[n]) to any permutation of (1,2,....n).
second step. According to below source code.
for(int i=n; i>0; i--) {
/* Binary Indexed Tree */
update(a[i]);
int cnt = sum(a[i]); // cnt is number of less than a[i].
answer is print("%d ",n-i+1-cnt);
}

Time limit is n * (log(n) + log(n));

vector <int> v; v.push_back(2);
for(int i=3; i<3162; i+=2)
{
if(prime[i]==false)
for(int j=i*i; j<10000000; j+=2*i)
{
prime[j] = true;
}
}

for(int i=3; i<10000000; i+=2) if(prime[i] == false) v.push_back(i);

answer is v[k]. Because v.size() is greater than 500000.

Time limit 1ms.

vector <int> v; v.push_back(2);
for(int i=3; i<3162; i+=2)
{
if(prime[i]==false)
for(int j=i*i; j<10000000; j+=2*i)
{
prime[j] = true;
}
}

for(int i=3; i<10000000; i+=2) if(prime[i] == false) v.push_back(i);

answer is v[k]. Because v.size() is greater than 500000.

Time limit 1ms.

Wilson's prime number.

if n < 20 is bit mask.

sum = a1+a2+ ..... + an
if 00010101 is val = a4+a6+a8 another value is sum - val Now mn = min(mn, diff(sum-val,val))
and answer is mn
Solution o(2^n).

Dynamic programming

dpmn[i][j] is minimum value of [i,j] interval.
dpmx[i][j] is maximum value of [i,j] interval.

How to find dpmn[i][j], dpmx[i][j] these value.

given integers a[1],a[2],...,a[n]

for(int i=1; i<=n; i++)
{
dpm[i][i]=dpmx[i][i]=a[i];
for(int j=i-1; j>0; j--)
{
for(int k=j+1; k<i; k++)
{
dpmx[j][i] = max(dpmx[i][j], dpmn[j][k]*dpmn[k+1][i]);
dpmx[j][i] = max(dpmx[i][j], dpmx[j][k]*dpmn[k+1][i]);
dpmx[j][i] = max(dpmx[i][j], dpmn[j][k]*dpmx[k+1][i]);
dpmx[j][i] = max(dpmx[i][j], dpmx[j][k]*dpmx[k+1][i]);
...
etc
}
}
}
answer dp[1][n]
Solution is O(N^3)