Two Sum Challenge

0xEDD1E
0xEDD1E
මට leetcode.com එකේ හමුවුණු පොඩි programming challenge එකක් මේ.
කරන්න තියෙන්නේ දෙන ලද array එකක, element 2ක් එකතු කළාම යම් කිසි target number එකක් සැදෙන විදිහට ඇති elements දෙකේ index හොයන එකයි.

උදාහරණයක් විදිහට:

array එක [2, 5, 7 , 11] නම් target number එක 9 නම්.
output එක වෙන්නේ [0, 1].
*num[0] + num[1] = 9 නිසා.*


Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].



මොකක් හරි ප්‍රශ්නයක් නිසා මගේ විසඳුම leetcode එකෙන් භාරගන්නේ නෑ. ඒ හින්ද කාටහරි පුලුවන්නම් මේකට විසඳුමක් ලියන්න, ඒක ලොකු උදව්වක්.

මේ තියෙන්නේ මගේ විසඳුම.

/* hash element */
typedef struct hashkey {
int key; // key of the hash element
int idx; // index of the key in array
struct hashkey *next; // collision chain - next element
} Hashkey;

#define HASHNULL (Hashkey **) 0
#define MODNUM 263 // integer hashing modifier
#define PRIME 100000009 // relatively big prime to mod large hashes
#define NULLIDX -1 // null index

typedef unsigned long hashval_t;
typedef const unsigned hashsize_t;

Hashkey **initHash(hashsize_t);
int findHash(int, Hashkey **, hashsize_t);
int addHash(Hashkey **, int, int, hashsize_t);
hashval_t hashInt(int, hashval_t, hashval_t);
int *twoSum(int *, int, int);

/**
* creates a hashtable of size 'size'
*/
Hashkey **initHash(hashsize_t size)
{
if (size > 0) {
return (Hashkey **) malloc(size * sizeof (Hashkey *));
}

return HASHNULL;
}

/**
* integer hashing function
* calculates the hashkey for |val|
*/
hashval_t hashInt(int val, hashval_t mod, hashval_t p)
{
hashval_t key = 0UL;
val = (val < 0) ? -val : val;

do {
key = ((key + val % 10) * mod) % p;
val /= 10;
} while (val > 0);

return key;
}

/**
* add element to hashtable
* size of the hashtable is necessary to add the element
*/
int addHash(Hashkey **hashtab, int val, int idx, hashsize_t hashSize)
{
hashval_t hashSlot = hashInt(val, MODNUM, PRIME) % hashSize;
Hashkey *newKey = (Hashkey *) malloc(sizeof (Hashkey));

if (newKey != NULL) {
newKey->key = val;
newKey->idx = idx;
newKey->next = hashtab[hashSlot];
hashtab[hashSlot] = newKey;
return 1;
}

return 0;
}

/**
* finds the 'find' key in hashtable
* returns 'idx' if 'find' exists in hashtable
* else returns NULLIDX
* size of the hashtable is necessary
*/
int findHash(int find, Hashkey **hashtab, hashsize_t size)
{
hashval_t thisKeyHash = hashInt(find, MODNUM, PRIME) % size;

for (Hashkey *p = hashtab[thisKeyHash]; p != NULL; p = p->next)
if (p->key == find)
return p->idx;

return NULLIDX;
}

/**
* two sum function:
* for each element in array:
* if target - element in hashtable:
* return (indexof(target - element), element)
* else
* add element to hash
* return (0, 0) // no elements in the array to make target
*/
int *twoSum(int *array, int size, int target)
{
const int hashsize = 1000;
Hashkey **hashtab = initHash(hashsize);

int *ret = malloc(2 * sizeof(int));
ret[0] = 0, ret[1] = 0;

int pos = 0;

for (int i = 0; i < size; i++)
if ((pos = findHash(target - array[i], hashtab, hashsize)) != NULLIDX) {
ret[0] = pos, ret[1] = i;
return ret;
//printf("%d, %d\n", i, j);
} else
addHash(hashtab, array[i], i, hashsize);


return ret;
}
Area_MasterChathinduSL
Being able to break security doesn't make you a hacker anymore than being able to hotwire cars makes you an automotive engineer
- ESR ("How to become a Hacker")

Answers

Sign In or Register to comment.

තාමත් එකතු වුනේ නැද්ද....??

▪ අලුත් විදිහට ලෝකය දකින.......................!

▪ අලුත් දේවල් කරන්න සිහින දකින...............!

▪ ඔබ වෙනුවෙන්ම නිර්මානය කල, ඔබගේම ෆොරමය, එකතුව.org

▪ ඉතින් දැන්ම එකතු වෙන්න, එකතුවත් එක්ක.

Sign In with Facebook Sign In with GooglePlus Sign In with OpenID Sign In with Twitter

මෙම සාකච්චාවට සම්බන්ද වූ අය

Advertisement

© Copyright 2016 - ekathuwa.org | Powered By Max Web Solutions