Two Sum

Given an array of integers, return indices of the two numbers such that they add up to specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

Solution:

def twoSum(nums, target):

dic = {}

if len(nums) <= 1:

return False

for k in range(len(nums)):

if nums[k] in dic:

return [dic[nums[k]],k]

else:

dic[target - nums[k]] = k


#optimal_Solution #python #data_structure

Number of ways to add up to a sum S with N numbers

Given an array of unique number and sum. There are many combinations and subsets of an array that come up with given sum. 

Example : 

Input : A[] = {1,2,4,5,9}

           sum = 15

Output: 2

Combinations are {1,5,9} and {1,2,4,5}

Input: A[] = {2,3,5,6,8,10}

          Sum = 10 

Output: 3

Combinations are {2,3,5}, {2,8} and {10}

A = [2,3,5,8,10]

total = 10

#initialize all elements to zero first

arr = [[0 for x in range(len(A)+1)] for y in range(len(A)+1)]

arr[0][0] = 1 

index_dict = {0:0} #Stores element and its index in array

for ind, y in enumerate(A):

    index_dict[y] = ind+1

for i in range(1,len(A)+1):

    arr[i] = [x for x in arr[i-1]] #Duplicate upper row

    for j in range(i,len(A)+1):

        diff = A[j-1]-A[i-1]

        if diff in index_dict: #If difference found in present list

            indx = index_dict[diff]

            arr[i][j] = arr[i-1][j] + arr[i-1][indx] #Update with its possible combination

 print arr[-1][-1]      

NA	Array Elements					0
0	2	3	5	8	10	Subtract from
1	0	0	0	0	0	0
1	1	0	0	0	0	2
1	1	1	1	0	0	3
1	1	1	2	1	1	5
1	1	1	2	2	2	8
1	1	1	2	2	3	10

#perfectsumproblem #geeksforgeeks #ways #combinations #subset #subsequence #array #dynamicprogramming 

Hackerrank - Algorithm - Fibonacci Modified

 Hackerrank - Algorithm - Fibonacci Modified

Given terms  and  where , term  is computed using the following relation:

For example, if term  and , term , term , term , and so on.

Given three integers, , , and , compute and print term  of a modified Fibonacci sequence.

-----------------------------------------------------------------------------------------

Source Code:

t1,t2,n = map(int,raw_input().split())

for i in range(1,n-1):

    ans = t1 + t2**2

    t1 = t2

    t2= ans

print(ans)

------------------------------------------------------------------------------------------------------

#hackerrank #algorithm #fibonaccimodified #solution #sourcecode #python #submission