Maximize difference between sum of prime and non-prime array elements by left shifting of digits minimum number of times

  

def isPrime(n):

  

    

    if (n <= 1):

        return False

    if (n <= 3):

        return True

  

    

    

    if (n % 2 == 0 or n % 3 == 0):

        return False

  

    i = 5

  

    

    while(i * i <= n):

  

        

        if (n % i == 0 or n % (i + 2) == 0):

            return False

        i = i + 6

  

    return True

  

def rotateElement(n):

  

        

    strN = str(n)

  

    

    

    maxPrime = -1

  

    

    

    cost = 0

  

    temp = str(strN)

  

    

    

    for i in range(len(strN)):

  

        

        

        if isPrime(int(temp)) and int(temp) > maxPrime:

            maxPrime = int(temp)

            cost = i

  

        

        temp = temp[1:]+temp[:1]

  

    optEle = maxPrime

  

    

    if optEle == -1:

        optEle = float('inf')

        temp = str(strN)

  

        

        

        for i in range(len(strN)):

  

            

            if int(temp) < optEle:

                optEle = int(temp)

                cost = i

  

            

            temp = temp[1:]+temp[:1]

        optEle *= (-1)

  

    return (optEle, cost)

  

def getMaxSum(arr):

  

    

    

    maxSum, cost = 0, 0

  

    

    for x in arr:

  

        

        

        optEle, optCost = rotateElement(x)

  

        

        

        maxSum += optEle

        cost += optCost

  

    

    print('Difference =', maxSum, ',',

          'Count of operations =', cost)

  

  

  

arr = [541, 763, 321, 716, 143]

getMaxSum(arr)

Let's block ads! (Why?)