CODEWITHSUNDEEP
pythonarraysrecursionsearchinteger
lambduh
lambduh

Reputation: 43

Check if an Integer Array can be Equalized using Recursion in Python

Given an integer array of size 5 with arbitrary positive values and m, I am tasked to create a program that will check if it is possible to equalize this array (all integers are equal) with the following process:

With m being the current position, it will jump to another integer, and by jumping, the integer in that position gets reduced based of the distance from this integer's position from m.

Example: [2, 2, 4, 2, 2] with m = 0 (first position)
          
we jump to  the third position to equalize the integer array, that means 4 minus (distance from current position to 4)
   
   v (m = 0)
  [2, 2, 4, 2, 2]

          v jump to index 2 (3rd position)
  [2, 2, (4 - abs(2-0)), 2, 2]

= [2, 2, 2, 2, 2] (all integer is equal)

since there is a way to equalize the array, return True.

Integers in the array must only be positive. If there is no possible way to equalize the array, return False.

I managed to make a code but it's not working for the hidden cases (this is a problem from our school).

def canEqual(array, m):

    if min(array) == max(array): return True     # Array can be Equalized, Return True

    for integer in array:   
        if integer < 1: return False             # If there is an integer in the array
                                                 # less than 1, then return False since
                                                 # it cannot be.

    for index, integer in enumerate(array):           # Treats the min value in the array as the
        if integer > min(array) and index != m:       # basis for equalizing. If an element is greater
            temp = array[:]                           # than the minimum, the program will jump to this position
            temp[index] = integer-abs(m-index)        # and the cycle continues until either the array
                                                      # is equalized or there exists a non positive integer.

            if canEqual(temp, index): return canEqual(temp, index)

I'm not really sure if my approach to this problem is correct.

Upvotes: 0

Views: 117

Answers (1)

Yossi Levi
Yossi Levi

Reputation: 1268

Take a look at that (and try to understand it better by investigate it), uncomment the two prints to understand better the process, and ask for clarifications if something not make sense to you.

def canEqual(cur_arr, m):
    if min(cur_arr) < 0:
        return False
    if min(cur_arr) == max(cur_arr):
        return True
    else:
        for iter, item in enumerate(cur_arr):
            if iter!=m:
                cur_arr[iter] = cur_arr[iter]-abs(m-iter)
                # print(iter)
                # print(cur_arr)
                if canEqual(cur_arr, iter):
                    return True
                else:
                    cur_arr[iter] = cur_arr[iter]+abs(m-iter)
    return False
print(canEqual([2, 2, 4, 2, 2], 2))

output:

True

Upvotes: 1

Related Questions