Problem Solving

This is my first post in which I am going to share about a simple problem solving in python.

Problem: If a read only array or list of numbers is given such that it contains all the numbers ranging from 0 to length of the array and the array has one number missing in it and therefore the missed number is replaced by another number which is repeated. Find the missing and repeated values in a given list.

I have chosen python programming to solve this problem. Here is the step by step process to approach the problem.

Step 1: Get a list of values from the user and sort the array in order.

length_of_array = int(input(“Enter the size of the array “))

user_list =[]
for i in range(length_of_array):
i = int(input(“Enter a number”))
user_list.append(i)

final_list = sorted(user_list)

Step 2: Find the difference between the sum of values of the given array and the sum of N natural numbers, N being the length of the array say X. i.e. (a-b)

sum_of_array = sum(final_list)
sum_of_nums = N*(N+1)/2
X = abs(sum_of_array — sum_of_nums)

Step 3: Similarly, Find the difference between the sum of squares of the values between given and N numbers of the array say Y. i.e. a²-b² which is equal to (a+b)(a-b)

sum_of_squares_array = sum(i*i for i in final_list)
sum_of_squared_nums = (N*(N+1)*(2*N+1))/6
Y = abs(sum_of_squares_array — sum_of_squared_nums)

Step 4: Now calculate the Y/X and store as say Z. i.e. (a+b)(a-b)/(a-b) = (a+b)

Z = int(Y/X)

Step 5: With X and Z we can calculate the repeated and missing values.

repeated_val = abs((X-Z)/2)
missed_val = abs((X+Z)/2)
print(“The missed value in the array is {} and the repeated value is {}”. format(missed_val,repeated_val))

Github link https://github.com/ganathetechie/problem_solving_using_python