I thought of this. Please let me know what you think.

1- Sort points based on their distance.
2- Set the minimal distance to the distance between the 1st and the 100th point. Then iterate through points, calculate the distance between the 2nd and 101th, 3rd and 102nd, ... and update the minimal distance accordingly.
I assumed the set of 100 closest points is defined as the set of points which the distance between its two farthest points is less than all other possible sets of 100 points.

BTW, just to show that the issue isn't unique to primes, consider what happens when n is the square of a prime, p^2. Then the only even division of the set (which we need for uniform random generation) has p buckets with p elements each. But then lookup takes O(p) = O(sqrt(n)) time! You're going to have issues like that whenever n doesn't have small prime factors (small relative to n).

This approach can't work in general. If the number of elements in the set is prime, for example, it is impossible to divide the elements evenly between buckets, so that each bucket has the same size. That manifests in a non-uniform probability distribution, where elements in larger buckets are less likely to be picked.

The enumeration for the 5 example is wrong.

A sequence of positive integers summing to an integer n is called a composition of n. If you think of n as 1 + 1 + ... + 1, a composition corresponds to replacing some of the plus signs with commas. There are n terms and hence n-1 plus signs, so there are C(n-1, k) compositions of n with k parts. Summing over all k gives C(n-1, 0) + C(n-1, 1) + C(n-1, 2) + ... + C(n-1, n-1) = 2^(n-1). Discounting the 1-term composition that consists of just n itself, that leaves 2^(n-1) - 1 compositions. Your 4 example has 7 = 2^(4-1) - 1 objects, so it checks out. But your 5 example has only 12 objects, whereas the formula says it should have 2^(5-1) -1 = 15.

This counting argument shows that brute-force enumeration without dynamic programming is the best you can do if you want to represent all the compositions explicitly. Here's a program that enumerates all compositions of an integer:

#include <stdio.h>


void printa(int *a, int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
}

void compositions(int *a, int n, int k)
{
    if (n == 0) {
        printa(a, k);
        return;
    }
    for (int p = 1; p <= n; p++) {
        a[k] = p;
        compositions(a, n-p, k+1);
    }
}

int main()
{
    int a[10];
    compositions(a, 5, 0);
    return 0;
}

Running this shows that the compositions of 5 missing from your example are 1 2 2, 2 1 2 and 2 2 1.

Maybe, we can also sort the src string, and for each character in finding string, we perform a binary search in src string to see if src string also has such character. It will be slower, however, save spaces

Awesomly awesome..!

Counting Sort O(n)

Traverse once to find dups O(n)

should be d, since args is an array of strings

We can use hashing with chaining(linked-list).
For this we have to choose an array of size M = 1113 (larger than the number of keys).
We choose a large array so that average number of keys per linked-list remains almost ~1. Let’s say no. is 997, so 997 % 1113 = 997.
997 will be my array index, Key = 997, Value = 997.

Going by this way out search hit, search miss, insert, delete, and finding any random number will be executed in constant-time.

We have to choose the load-factor very wisely such that list sizes are small and number of comparisons if needed be (no. of keys in the arrays / size of the array)

This is a standard implementation of backtracking algorithm.

Take your position as 0,0,0
then calculate the d1,d2,d3 of all the stars from your position..
Now make the min heap of all the distances..
Now delete the root node 100 times ..and there u find the nearest 100 stars from ur point..

reviews please

0sabio00@gmail.com

Good thinking but retainAll is not O(1)
retainAll is an inbuilt JAVA algorithm which takes higher time complexity.
(nobrainer .co .cc)

Hi Tanvi Reddy,

Can you be a bit more elaborate on this? What are you trying to achieve by using a boolean array ?

In C, with no error handling, and using built-in functions for string searching and decimal conversion:

typedef unsigned int ipaddr;


ipaddr parse_ipaddr(const char *str)
{
    ipaddr addr;
    while (str) {
        addr *= 256;
        addr += atoi(str);
        str = strchr(str, '.');
        if (str) str++;
    }
    return addr;
}

public double IPAddressToNumber(string IPaddress)
{
int i;
string [] arrDec;
double num = 0;
if (IPaddress == "")
{
return 0;
}
else
{
arrDec = IPaddress.Split('.');
for(i = arrDec.Length - 1; i >= 0 ; i --)
{
num += ((int.Parse(arrDec[i])%256) * Math.Pow(256 ,(3 - i )));
}
return num;
}
}

Use a variation on the Briggs-Torczon sparse set data structure. Google it if you're unfamiliar with it. Then everything takes constant time, including (rather interestingly) initialization.

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

unsigned int forward[1000];
int backward[1000];
int n;

int contains(int x)
{
    assert(0 <= x && x < 1000);
    unsigned int i = forward[x];
    return i < n && backward[i] == x;
}

void insert(int x)
{
    assert(0 <= x && x < 1000);
    if (!contains(x)) {
        unsigned int i = n++;
        forward[x] = i;
        backward[i] = x;
    }
}

void delete(int x)
{
    assert(0 <= x && x < 1000);
    unsigned int i = forward[x];
    if (i < n && backward[i] == x) {
        int y = backward[n-1];
        forward[y] = i;
        backward[i] = y;
        n--;
    }
}

int choose()
{
    assert(n > 0);
    return backward[rand() % n];
}

int main()
{
    insert(0);
    insert(500);
    insert(3);
    assert(contains(0));
    assert(contains(500));
    assert(contains(3));
    assert(!contains(4));
    assert(!contains(123));
    for (int i = 0; i < 10; i++)
        printf("%d ", choose());
    printf("\n");
    delete(3);
    insert(999);
    for (int i = 0; i < 10; i++)
        printf("%d ", choose());
    printf("\n");
    delete(500);
    delete(0);
    for (int i = 0; i < 10; i++)
        printf("%d ", choose());
    printf("\n");

return 0;
}

Good answer, but I want to add, that FFT really faster for big numbers. If you have participated at Facebook HC 2011, there was interesting problem in it, where Karatsuba worked tool long.

Actually for numbers like in example simple O(n^2) or Java.BigInteger will work even faster then Karatsuba.

- Interfaces are used for writing extensible code, when you modify an implementation of an interface, you ensure that this change will not effect the system because only the implementation has changed but not the contract, so when you really need to modify the implementations without really affecting how the application uses it, you use interfaces.
- And usually it is a good practice to write interfaces because they also help you in Mocking and unit testing of your code.
- It is also a good practice to ensure that you set the implementations of interfaces in your application using setter methods because that ensures more ways to mock your objects and helps in loose coupling.

Actually the mask should be
m = z ^ ~(z-1)
this will solve any number of bit changes in the two distinct numbers we want to find.

In .NET

const sampleIp = "255.255.255.255";
string toConvert = sampleIp.Replace(".", "");
uint ip = (uint)Int.TryParse(toConvert);

sorry ...i gave ans. on the basis of random input of no.'s

for random no--->len=strlen(a)
int ran=rand()%len;

#include<stdio.h>
#include<conio.h>
void swap(int ,int );
int a[]={1,-2,-3,-4,-5,1,2,3,4};
void main()
{
int needed,current;
int i=0,j=1;
clrscr();
if(a[0]>0)
{
needed=-1;
current=0;
}
else
{
needed=0;
current=-1;
}
while(j<9)
{
if(a[j]>0)
current=0;
else
current=-1;
if(needed==current)
{
swap(i+1,j);
needed=~needed;
i++;
j=i+1;
}
else
j++;
}
for(i=0;i<9;i++)
printf(" %3d",a[i]);
getch();
}

void swap(int i,int j)
{
int c,k;
c=a[j];
for(k=j;k>i;k--)
a[k]=a[k-1];
a[i]=c;
}

The main idea is to wrap around the max sum..
1.find the max sum n nos using kadane's algo
2.Use DP to remember Max sum's
3.wrap around the sum..i.e start from each no
4.if the 1st no is -ve remove the no from max sum

eg..
-3 5 6 -2 -2 2 2

1.find max sum for the sq->11
2.start including circula wise start from 5 and include -3 in the sum element include .store the sum in a DP.
3.when startng from a -ve no dont include it in sum.For the array starting in -2 dont include it

finally max of DP array will give u the sum

content of DP array 11 8 8 10 12 10 8

hope u got my approach its O(n) with extra space of n

void rotate(char str[], int k)
{
int n;

n = strlen(str);

reverse(str, 0, k-1);
reverse(str, k, n-1);
reverse(str, 0, n-1);
}
where,
k = pivot
n = string length

void rotate(char str[], int k)
{
int n;

n = strlen(str);

reverse(str, 0, k-1);
reverse(str, k, n-1);
reverse(str, 0, n-1);
}
where,
k = pivot
n = string length

but I guess that with extra data structure (stack?) or if thre are pointers up from children to their father.

Hash Table?

verify whether it is compatibility to handle coffee cup with soucer

verify whether it is compatibility to handle coffee cup with soucer

STACK

the asymptotically fastest algorithm is based on Fermat transform
where you compute the product using FFT modulo 2^{2^n}+1 (fermat numbers)
yet for numbers of this magnitude, FFT does not pay off in practice: it's better to use some splitting scheme, ie Karatsuba or Toom-Cook multiplication:

suppose A = h1 * 2^w + l1
B = h2 * 2^w + l2
where w is chosen to split the numbers in possibly even parts

then A * B = z2 * 2^{2w} + z1*2^w + z0
where z2 = h1*h2, z0 = l1*l2, z1 = (h1+l1)*(h2+l2) - z2 - z0
hence we need only 3 muls instead of 4. And the whole algorithm can be applied recursively yielding complexity O(n^{log3})

Thank you very much for your help.

This should be fine:

int randY()
{
   int  a=rand(5)-1;    //0-4
   int  b=rand(5)-1;    //0-4
   int c=2^a+b;              //    1-20
   int d=c%7;


return d;

}

This should be fine:

int randY()
{

}

along with linked lists, i will prefere Booth's algorithm which deals with 1,0 and carry can be followed here or is there any other approach for this

along with linked lists, i will prefere Booth's algorithm which deals with 1,0 and carry can be followed here or is there any other approach for this

substring takes O(1), but == takes O(1) to O(m), so in the worst case scenario where all strings are the same, this will be doing O(m*n).

We can also add Compatibility Test Cases...
1. Testing using various browsers like FireFox, Chrome, IE, Safari
2. Testing in different environments like mobile browser, desktop, tablet

Hi Joe,
Just trace the whole program, its smart and easy. You will understand it better.

Are not we using extra space 'temp'?? [do not use any extra space] It is clearly specified in given question.

One thing missing from delete. Update A[B[C-1]] to A[x] (use the old values before the swap).

-1. They tough part is getting the random generation to work.

I don't want to register etc just for the sake of downvoting.

This was assuming numbers are 0..1000.

Use two arrays A and B. Also maintain a count C of how many distinct elements have been inserted.

Initially A and B are initialized with -1, and C is set to 0.

Each element of array A contains index into element of Array B.

On an insert of element x, if A[x] is -1, then we set B[C] to x, set A[x] to C and increment C.

On a search we check if A[x] is -1 or not.

On a delete we swap B[A[x]] and B[C-1], decrement C, and set A[x] to -1.

On a random number required, we generate a random number r from 0 to C-1, and return B[r].

All operations are O(1) (assuming random number generator is O(1)).

I tried by executing above code, but they are not producing the desired output of "542" for the input of "2452". Here is my code:

#include <stdio.h>
main()
{
     int num = 0, dup, rev = 0;
     int i = 0, arr[10]= {0};
     printf ("\n Please enter a number: ");
     scanf ("%d", &num);
     dup = num;
     while (dup > 0) {
          i = dup%10;
          arr[i]++;
          dup = dup/10;
     }
     dup = num;
     while (dup > 0) {
          i = dup%10;
          if (arr[i] == 1) 
               rev = rev * 10 + i;
          else
               arr[i]--;
          dup = dup/10;
     }
     printf ("\n Reverse number is: %d \n", rev);
}

It works for first 3 but not for "Get any random number".
"Get any random number" means that the index can be can be a random number between 1 and 1000 so you could potentially get a deleted/empty (a[i]==0) node.

xor solution is nice.. as an alternative we can compute
the sum and sum of squares which for 32-bit numbers won't produce an overflow (or we can work with 64-bit ints instead which wont change the complexity)

thus we get: x + y = SUM_A - SUM_B
x^2 + y^2 = SUMSQ_A - SUMSQ_B

from there x and y can be easily computed.