Question

Assume someone has a secret 4-tuple (w, x, y, z) where each number can be from 1 to 1000 inclusive. Your code is supposed to find what these integers are by using a loop and comparing the number (part of Brute Force). One approach is to write four nested for-loops to check for the number. This is O(n 4 ). Your task is to determine a random 4-tuple. Is your solution better than O(n^4 )?

1 import random as rn

2

3 x = [rn.randint(1,1000), rn.randint(1,1000), rn.randint(1,1000), rn.←- randint(1,1000)]

4

5 def find_tuple(x):

6 pass

Answer 1

• Below is the detailed implementation of the above problem in PYTHON with code and output shown.
• For better understanding please read the comments mentioned in the code.
• CODE:

#import random module to generate random numbers
import random as rn
#generate a secret tuple
x = [rn.randint(1,1000), rn.randint(1,1000), rn.randint(1,1000), rn.randint(1,1000)]
#print the secret tuple so that we can check what we found afterwards
print("The secret tuple:",x)

#function which takes secret tuple as input and return the integers in tuple after finding them
def find_tuple(x):
#answer list to store integers
ans=[]
  
#for finding the first number in tuple x
#iterate from 1 to 1000 and check if number equals the first number in tuple x
for i in range(1,1001):
#if current number equals first number then add it to list and break the loop
if x[0]==i:
ans.append(i)
break
  
#for finding the second number in tuple x
#iterate from 1 to 1000 and check if number equals the second number in tuple x
for i in range(1,1001):
#if current number equals second number then add it to list and break the loop
if x[1]==i:
ans.append(i)
break
  
#for finding the third number in tuple x
#iterate from 1 to 1000 and check if number equals the third number in tuple x
for i in range(1,1001):
#if current number equals third number then add it to list and break the loop
if x[2]==i:
ans.append(i)
break
  
#for finding the fourth number in tuple x
#iterate from 1 to 1000 and check if number equals the fourth number in tuple x
for i in range(1,1001):
#if current number equals fourth number then add it to list and break the loop
if x[3]==i:
ans.append(i)
break
  
#return found tuple
return ans

#call find_tuple and print what we found
print("We found:",find_tuple(x))

• OUTPUT:

The secret tuple: [934, 9, 321, 28]
We found: [934, 9, 321, 28]

• The complexity of the above code is better than O(n^4 ) as we use 4 for-loops to find each of the numbers in the secret tuple and each loop as complexity O(n) so overall we have complexity O(4*n) which is O(n) only. So we found the secret tuple in linear time.

• Below are the screenshot attached for the code and output for better clarity and understanding.

CODE and OUTPUT

So if you still have any doubt regarding this solution please feel free to ask it in the comment section below and if it is helpful then please upvote this solution, THANK YOU.