CareerCup

1) first sort the array --> O(nlog n)
2) Take two pointers first and last
while(first<=last)
{
if(arr[first]*arr[last]==given_input)
print " both nos";
if(arr[first]*arr[last]>given_input)
last--;
if(arr[first]*arr[last]<given_input)
first++;
}

not sure what you need an array of 100, you can just use two counters, one going up from 1, the other going down from N (where N is the number), the termining condition being (lower counter< upper counter)

it can be done with O(n) space and O(n) Runtime with Hash.

Step#1 Iterate over Array.
Step#2 Key=30/Array[i]. 
        a)Check if the key exists in Hashmap. If yes, print key and Array[i]
        b)if not [Insert key into Hashmap ]

A small correction.
 
it can be done with O(n) space and O(n) Runtime with Hash.

Step#1 Iterate over Array.
Step#2 Key=30/Array[i]. 
        a)Check if the array[i] exists in Hashmap. If yes, print key and Array[i]
        b)if not [Insert key into Hashmap ]

void main()
{
A[100];
k;
B[k/2];
PRINT(1,k);
for(i=2;i<100;i++)
{
If(k%A[i]==0)
{
m= k/A[i];
if(i<=m&&B[i]==0)
{
B[i]=1;
PRINT(i,m);
}
if(m]<i&&B[m]==0)
{
B[m]=1;
PRINT(m,i);

}
}
}
}

amit's solution is correct approach.

This can be done using a hashtable. For each number, check if (Given_value / array[i]) exists in the hash, if not then add array[i] in the hashtable. Keep going through the array, until you find the pair which multiplication is the value given. 
This can be done in O(n) with extra storage.

This can be done using a hashtable. For each number, check if (Given_value / array[i]) exists in the hash, if not then add array[i] in the hashtable. Keep going through the array, until you find the pair which multiplication is the value given.
This can be done in O(n) with extra storage.

suppose array has only six elements {1,2,3,4,5,6} number is 30,  key=30/arr[i]  .. ..30,15,10,7,6,5  can you explain how to get 6 and 5 is answer in this scenario.

i got it thanks

good solution given by amit

vector< pair <int, int> > getFactorInArrayOfInt( int numbers[100], int n )
{
map<int, bool> foundNums;
vector< pair <int, int> > ret;
for ( int i = 0; i < 100; i++ )
{
if ( n % numbers[i] == 0 )
{
int otherFactor = n / numbers[i];
if ( foundNums[ otherFactor ] )
{
pair <int, int> p( otherFactor, numbers[i] );
ret.push_back(p);
}
foundNums[ numbers[i] ] = true;
}
}
return ret;
}

When the array is pre-sorted it takes only o(n) time(single pass) and o(1) space, for idea's solution.

HashTable Solution doesnt depend on whether array is sorted or not. It always takes o(2n)(two passes) time and o(n) space.

int cmp(const void* a, const void* b) {
    return (*(int*) a) - (*(int*) b);
}

void factorsWithSort(int a[], int x) {
    int y = sqrt(x), z = 0;

    qsort(a, N, sizeof (int), cmp);

    for (int i = 0; a[i] <= y && i < N; ++i) {
        z = x / a[i];
        if (x % a[i] == 0 && binary_search(a, a + N, z)) cout << a[i] << '\t' << z << endl;
    }
}

// int hash[N] = {0}; Won't suffice if any value is >= 100
void factorsWithHash(int a[], int x) {
    map<int, int> map;
    int k = 0, v = 0;

    for (int i = 0; i < N; ++i) {
        if (x % a[i] == 0) {
            k = x / a[i];
            if (v = map[k]) cout << k << '\t' << v << endl;
            else map[a[i]] = k;
        }
    }
}

Enhancement:

void factorsWithHash(int a[], int x) {
map<int, int> map;
int k = 0, v = 0;

for (int i = 0; a[i] <= x && i < N; ++i) {
if (x % a[i] == 0) {
k = x / a[i];
if (v = map[k]) cout << k << '\t' << v << endl;
else map[a[i]] = k;
}
}
}

Enhancement:

void factorsWithHash(int a[], int x) {
    map<int, int> map;
    int k = 0, v = 0;

    for (int i = 0; a[i] <= x && i < N; ++i) {
        if (x % a[i] == 0) {
            k = x / a[i];
            if (v = map[k]) cout << k << '\t' << v << endl;
            else map[a[i]] = k;
        }
    }
}

can u explain more please...

what if we have to do without extra space,,i.e. inplace (and unsorted list) ?

void getProductPairs(std::vector<unsigned int> numberArray, unsigned int product, std::vector< std::pair<unsigned int, unsigned int> > &allPairs) {
std::map<unsigned int, unsigned int> occurenceMap;
for (std::vector<unsigned int>::iterator iter = numberArray.begin(); iter != numberArray.end(); iter++) {
if ((product % *iter) == 0) {
int numPairs;
if ( (numPairs = occurenceMap.count((product / *iter))) > 0) {
allPairs.insert(allPairs.begin(), occurenceMap[(product / *iter)] , std::make_pair(*iter, product/(*iter)));
}
}
occurenceMap[*iter]++;
}
}

Amit's solution though O(n) on the look of it is not all that elegant!

First, insertion or search in Hash would consume O(log(n)).
Second, even by using extra space the algorithm is not getting efficient on reruns!
His solution would eventually turn out to be O(nlog(n))!

In my opinion, time complexity is not an issue here because it's given that the Array is of size 100... even nlogn =~ O(700) which is not huge at all!

So without using any more space the possible solution is:
1. Sort the array (100log100)
2. Init low=A[0], high = A[99]; Input M;
3. Iterate array starting at low ; compute val = int(M/A[low]);
4. Put high = tentative_Binary_search(val, low, high); // tentative binary search means if val doesn't exist return the lower key
5. If(A[high] == val) Print A[low] and A[high];
6. low = low + 1;
7. Go to 3 ; Till the point where (low == high)


In this scenario also most expensive step is sorting [which can be improved to O(n) depending on Array sets]
The other part is worst case O(100)

i dont understand the need for a hash table.

assuming the array is from 1-100 ( in any order), iterate from start to end and check for key % a[i]==0 . if this stmt is true, then factor1 = key/a[i] and factor2 = a[i]. to prevent repetition check if factor2 is greater than factor1 and if so then dont print it else print it

arr = 100

arr = [i for i in range(1, arr+1)] # ask if array to start from 0 or 1

target = 30

ret = []

for x in range(0, len(arr)-1):
for y in range(x+1, len(arr)):
if x*y == target:
ret.append([x,y])
print(x,'', y)
else:
print('not possible to multiply')

#option2
arr2= [(x, y) for x in range(0, len(arr)-1) for y in range(x+1, len(arr)) if x*y ==target]
print(arr2)

sachin sinh gaur : do you hate indents/tabs? please surround your code with

and

.

@Anshul: You are a big SUCKER !
care to suck ? ring 1-320-322-468