# HackerRank: [Python Question] GET STORAGE | Python-3 Solution by APDaga

I came across a Python 3 practice question by HackerRank.

Here, I am providing my solution to the problem "Get Storage" with the intention to help you learn and understand Python 3 in a better way.

Please make use of my blog posts for learning purposes only and feel free to ask your questions in the comment box below in case of any doubt.

## Python Problem Description:

There are a number of computers which are connected to each other. Each computer has a storage capacity which can be used to store data. When a computer is connected to another, they form a set of computers

and the storage capacity of the set is the sum of the storage capacities of the computers in the set.

You are given the set of connections between the computers by the arrays connections_from and connections_to (The connections are bi-directional). The initial storage capacities are denoted by

storage[storage[0],...,storage[connections_nodes-1]]. Also, you are given a threshold of storage capacity. After every connection, you are required to find the number of sets of computers which have storage capacity

less than or equal to threshold.

Note: Initially there are no connections between the computers and each computer can be considered as a set with 1 computer.

For example

• connections_nodes = 3. storage = {2, 3, 6}, connections_from = {0, 0, 2}, connections_to = {1, 2, 1}, threshold = 6.

• After 1st connection {0, 1}: {5, 6} (2 values are less than or equal to 6)

• After 2nd connection {0, 2}: {11} (no value is less than or equal to 6)

• After 3rd connection {2, 1}: {11} (no value is less than or equal to 6)

Return an array containing the answer after each connection.

## Function Description:

Complete the function getStorage in the editor below. The function must return a vector. get_storage has the following parameter(s):
• connections_nodes: an integer denoting the number of computers

• connections_from: an array of integers denoting the ith connection

• connections_to: an array of integers denoting the ith connection

• storage: an array of integers denoting the initial storage capacities

• threshold: an integer

## Constraints:

• 1 ≤ connections_nodes ≤ 105
• 1 ≤ connections_edges ≤ min( (connections_nodes) * (connections_nodes-1)/2, 105)
• 0 ≤ connections_fromi, connections_toi < connections_nodes
• 1 ≤ storage i ≤ 104
• 1 ≤ threshold ≤ 109
• The graph does not contain a self-loop or multiple edges between two nodes.

## Input Format For Testing:

• The first line contains 2 space-separated integers, connections_nodes and connections_edges, denoting the number of computers and number of connections respectively.

• Each line i of the connections_edges subsequent lines (where 0 ≤ i < connections_edges) contains 2 space-separated integers describing connections_from i and connections_to i.

• The next line contains an integer, connections_nodes, denoting the number of elements in storage.

• Each line i of the connections_nodes subsequent lines (where 0 ≤ i < connections_nodes) contains an integer storage i.

• The last line contains the integer threshold.

```5 3
0 1
1 4
0 4
5
1
2
3
4
5
4```

```3
2
2```

## Explanation:

• Initial storage capacities: {1, 2, 3, 4, 5}

• After 1st connection {0, 1}: {3, 3, 4, 5} (3 values are less than or equal to 4)

• After 2nd connection {1, 4}: {3, 4, 8} (2 value is less than or equal to 4)

• After 3rd connection {0, 4}: {3, 4, 8} (2 value is less than or equal to 4)

```3 2
0 1
1 2
3
1
2
3
4```

```2
0```

## Explanation:

• Initial storage capacities: {1, 2, 3}

• After 1st connection {0, 1}: {3, 3} (2 values are less than or equal to 4)

• After 2nd connection {1, 2}: {6} (no value is less than or equal to 4)

```###############Write your solution below##################
def get_storage(connection_nodes, connection_edges, connections_from, connections_to, storage, threshold):
# ans[i] = answer to i-th query for connections_from[i] and connections_to[i]
ans = []

return ans

ans = get_storage(connection_nodes, connection_edges, connections_from, connections_to, storage, threshold)
for _ in range(0,len(ans)):
print(ans[_])```

```Sr No.  Task                                                                 Weightage
1.	Preparation of Input param for function 				 30%
2.	Algorithm design (Pseudo code, Time Complexity, Memory Complexity )	 40%
3.	Completion of function(Coding) 					 30%```

## Python 3 Solution:

```# nodes = 5
# num_edges = 3
# edges = [(0, 1), (1, 4), (0, 4)]
# storages = [1, 2, 3, 4, 5]
# threshold = 4

nodes = int(input("Enter no. of nodes: "))
num_edges = int(input("Enter no. of edges: "))

edges = []
for i in range(num_edges):
edges.append(tuple(map(int, input("edge "+str(i+1)+" = ").split(" "))))

storages = []
for i in range(nodes):
storages.append(int(input("Storage "+str(i)+" = ")))

threshold = int(input("Enter the threshold: "))

# connection_map = [[0] * nodes for n in range(nodes)]
# print(connection_map)

class Graph:

# init function to declare class variables
def __init__(self, V):
self.V = V
self.adj = [[] for i in range(V)]

def DFSUtil(self, temp, v, visited):

# Mark the current vertex as visited
visited[v] = True

# Store the vertex to list
temp.append(v)

# Repeat for all vertices adjacent
# to this vertex v
if visited[i] == False:
# Update the list
temp = self.DFSUtil(temp, i, visited)
return temp

# method to add an undirected edge

# Method to retrieve connected components
# in an undirected graph
def connectedComponents(self):
visited = []
cc = []
for i in range(self.V):
visited.append(False)
for v in range(self.V):
if visited[v] == False:
temp = []
cc.append(self.DFSUtil(temp, v, visited))
return cc

# Driver Code
if __name__ == "__main__":
# Create a graph given in the above diagram
# 5 vertices numbered from 0 to 4
g = Graph(nodes)
for edge in edges:
from_node, to_node = edge

cc = g.connectedComponents()

print("\nFollowing are connected components")
print(cc)

new_storages = []

for connected_component in cc:
if len(connected_component) == 1:
new_storages.append(storages[connected_component[0]])
else:
storage = 0
for i in connected_component:
storage = storage + storages[i]
new_storages.append(storage)

count = 0
for storage in new_storages:
if storage <= threshold:
count = count + 1
print("Set of Computer having storage less than of equal to threshold:")
print(count)```

## Output:

### [Case-0] Output:

```# Following are connected components
# [[0, 1], [2], [3], [4]]
# Set of Computer having storage less than of equal to threshold:
# 3

# Following are connected components
# [[0, 1, 4], [2], [3]]
# Set of Computer having storage less than of equal to threshold:
# 2

# Following are connected components
# [[0, 1, 4], [2], [3]]
# Set of Computer having storage less than of equal to threshold:
# 2
# >
```

### [Case-1] Output:

```# Enter no. of nodes: 3
# Enter no. of edges: 2
# edge 1 = 0 1
# edge 2 = 1 2
# Storage 0 = 1
# Storage 1 = 2
# Storage 2 = 3
# Enter the threshold: 4

# [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

# Following are connected components
# [[0, 1], [2]]
# Set of Computer having storage less than of equal to threshold:
# 2

# Following are connected components
# [[0, 1, 2]]
# Set of Computer having storage less than of equal to threshold:
# 0
# > ```

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