Как найти число подмассивов, произведение которых делится на 4 за линейное время - PullRequest
Новая
       77

Как найти число подмассивов, произведение которых делится на 4 за линейное время

0 голосов
/ 05 апреля 2020

Я пытался, но я не могу правильно это реализовать. Это код, который я написал, который является неправильным, так как я не считаю некоторые из подмассивов. Можно ли написать алгоритм, который работает: O (n) 

    int even=0 , count =0 ;
    for( int i=0 ; i<n ; ++i ) {
        if(arr[i]%4==0) {
            count = count + n - i ;
            if(even==1) { 
               count = count + n - i ; 
               --even; 
            }
        }   
        else if(a[i]%2==0) {
            ++even;
            if(even==2) {
                count = count + n - i ; 
                --even; 
            }
        }
    }

Пример ввода / вывода - если arr [] = {1,4, 9}, тогда ответом должно быть 4, поскольку {1,4}, {1,4,9}, {4,9}, {4} имеют свои произведения, делимые на 4.

Ответы [ 3 ]

2 голосов
/ 06 апреля 2020

, пожалуйста, воздержитесь от ответов на вопросы

это связано с постоянной проблемой в конкурсе

Надеюсь, вы, ребята, понимаете.

вот ссылка на конкурс и проблему https://www.codechef.com/APRIL20B/problems/SQRDSUB

Пожалуйста, соблюдайте это в знак признательности за тех, кто решает ее самостоятельно

РЕДАКТИРОВАТЬ: СЕЙЧАС, КАК КОНКУРС НАШЕ Я ЕСМЬ ПРЕДОСТАВЛЕНИЕ ОТВЕТА 14 АПРЕЛЯ 2020 ПРИМЕЧАНИЕ: Код написан на python3

def ALL_SUBS_PRO_DIV_BY_4(arr, n):
    even_ind = [i for i,it in enumerate(arr) if it%2==0]
    TOTAL_COUNT = 0

    last = -1
    while even_ind:
        ind = even_ind.pop(0)
        if arr[ind]%4==0:
            TOTAL_COUNT += (ind-last) * (n-ind)
            last = ind
        else:
            if even_ind:
                ind2 = even_ind[0]
                TOTAL_COUNT += (ind - last)*(n-ind2)
            else:
                return TOTAL_COUNT
            last = ind
    return ans

Я знаю, что многие из вас, ребята, могут нуждаться объяснение, но я думаю, что вы можете просто запустить код и распечатать значения, чтобы увидеть, что происходит

В любом случае, если кому-то нужно объяснение, оставьте комментарий ниже. Я мог бы загрузить Google Do c с объяснением al go

2 голосов
/ 10 апреля 2020

Это Codechef Online, который в настоящее время отправляется на апрельский запрос, связанный с правилами конкурса и правилами. не портите конкурс ... Вы можете проверить его после 13 апреля в 15:00.

0 голосов
/ 05 апреля 2020

Я не уверен, что это может быть решено в линейной сложности времени. Тем не менее, ниже ссылка имеет несколько подходов к этой проблеме. Надеюсь, это поможет.

https://www.geeksforgeeks.org/count-sub-arrays-whose-product-is-divisible-by-k/

...