Блог

Вам дается массив A из N целых чисел. Если вы создадите массив целиком с помощью следующей операции, то какое минимальное количество операций требуется для выравнивания всего массива?

Примечание : Можно доказать, что это всегда возможно.

Операция

Выберите индекс

и выполнить операцию:

P=A[i] A[i 1]; Q=A[i]-A[i 1];

A[i]=P; A[i 1]=Q;

ссылка на весь вопрос

это мой код

 for i in range(int(input())):
    N=int(input())
    arr=list(map(int,input().split()))
    dic=[i for i in range(N) if arr[i]%2!=0 ]
    value=0
    for i in range(len(dic)-1):
        k=dic[i 1]-dic[i]
        value =k
    print(value)
 

тестовые наборы………….

 testcase1:
         N=6
         arr= 1 6 4 3 4 2
         my output = 3
         expected output = 4
 

я не понимаю, как получилось, что в этом тестовом случае требуется четыре операции, так как для этого нужно всего три операции .

   testcase 2:
           N=6
           arr = 1 6 4 3 5 2
           my output = 4
           expected output =3
 

в этом тестовом примере все целые числа не будут преобразованы в четное число, независимо от того, сколько операций мы применили .

если бы кто-нибудь мог показать мне, как получилось, что testcase2 выполняется за три операции .

тестовый кейс1 будет выполнен в четыре этапа .

и если бы я делал это неправильно

можно ли это решить с помощью битовых манипуляций.

Вот код, который вы можете попробовать для решения своей проблемы.

 def countOperations(arr, n) :
 
    count = 0;
 
    # Traverse the given array
    for i in range(n - 1) :
 
        # If an odd element occurs
        # then increment that element
        # and next adjacent element
        # by 1
        if (arr[i] amp; 1) :
            arr[i]  = 1;
            arr[i   1]  = 1;
            count  = 2;
 
    # Traverse the array if any odd
    # element occurs then return -1
    for i in range(n) :
        if (arr[i] amp; 1) :
            return -1;
 
    # Returns the count of operations
    return count;
 
if __name__ == "__main__" :
 
    arr = [ 2, 3, 4, 5, 6 ];
    n = len(arr);
    print(countOperations(arr, n));
 

в этом тестовом примере все целые числа не будут преобразованы в четное число, независимо от того, сколько операций мы применили .

• Да, они могут быть. Смотрите мое решение ниже.

Идея проста. Я не использовал никаких манипуляций с битами, но вот как бы я это сделал ,

• нечетное /- нечетное = четное
• нечетное /- четное = нечетное

Для ан i , если A[i] бы это было даже так, мне было бы все равно. Рассмотрим все i , такое, что A[i] странно.

• Если A[i 1] нечетно, у меня есть P= нечетно нечетно и Q=нечетно-нечетно, оба четных в одной операции. Я увеличу количество на 1.
• Если [i 1] четное, у меня есть P=нечетное четное и Q= нечетное-четное, оба нечетные. Я сделал одну операцию. Теперь у меня есть два шанса, еще одна операция, и я могу уравнять оба. Итак, я увеличу количество на 2.

если бы кто-нибудь мог показать мне, как получилось, что testcase2 выполняется за три операции .

• Операция 1 : [1 6 4 3 5 2] -> > [7 -5 4 3 5 2] , A[0] = A[0] A[1] , A[1] = A[0] - A[1]
• Операция 2 : [7 -5 4 3 5 2] -> > [2 12 4 3 5 2] , A[0] = A[0] A[1] , A[1] = A[0] - A[1]
• Операция 3 : [2 12 4 3 5 2] -> > [2 12 4 8 -2 2] , A[3] = A[3] A[4] , A[4] = A[3] - A[4]

можно ли это решить с помощью битовых манипуляций.

• Я думаю, что вы можете проверить нечетность даже с помощью побитовых операций, кроме этого, я так не думаю.

Вот возможная реализация :

 def count_ops(A,n):
    count = 0 
    i = 0 
    done_last = False
    while(i < n-1):
        if(A[i]%2 == 0):
            i =1
            continue
        if(i == n-2):
            done_last = True
        if(A[i 1]%2 == 0):
            count  = 2
        else:
            count  = 1
        i  = 2
    if(not done_last):
        if(A[n-1]%2 == 1):
            count  = 2
    print(count)
    return count
 

Обратите внимание на done_last флаг, я оставлю это на ваше усмотрение, чтобы выяснить.