Рубрики

Напишите эффективный метод, чтобы проверить, является ли число кратным 3

Самое первое решение, которое приходит нам на ум, — это то, которое мы узнали в школе. Если сумма цифр в числе кратна 3, то число кратно 3, например, для 612 сумма цифр равна 9, поэтому она кратна 3. Но это решение неэффективно. Вы должны получить все десятичные цифры одну за другой, добавить их и затем проверить, является ли сумма кратной 3.

В двоичном представлении есть шаблон, который можно использовать для определения, является ли число кратным 3. Если разность между количеством нечетных установленных битов (битов, установленных в нечетных позициях) и четными установленными битами кратна 3, тогда число.

Пример: 23 (00..10111)
1) Получить количество всех установленных битов в нечетных позициях (для 23 это 3).
2) Получить количество всех установленных битов в четных позициях (для 23 это 1).
3) Если разность двух вышеупомянутых чисел кратна 3, то число также кратно 3.

(Для 23 это 2, поэтому 23 не кратно 3)

Возьмите еще несколько примеров, таких как 21, 15 и т. Д.

Algorithm: isMutlipleOf3(n)
1) Make n positive if n is negative.
2) If number is 0 then return 1
3) If number is 1 then return 0
4) Initialize: odd_count = 0, even_count = 0
5) Loop while n != 0
    a) If rightmost bit is set then increment odd count.
    b) Right-shift n by 1 bit
    c) If rightmost bit is set then increment even count.
    d) Right-shift n by 1 bit
6) return isMutlipleOf3(odd_count - even_count)

Доказательство:
Выше может быть доказано на примере 11 в десятичных числах. (В этом контексте 11 в десятичных числах совпадает с 3 в двоичных числах)
Если разница между суммой нечетных и четных цифр кратна 11, то десятичное число кратно 11. Давайте посмотрим, как.

Давайте возьмем пример двухзначного числа в десятичной
AB = 11A -A + B = 11A + (B-A)
Таким образом, если (B — A) кратно 11, то AB.

Давайте возьмем трехзначные числа.

ABC = 99A + A + 11B — B + C = (99A + 11B) + (A + C — B)
Таким образом, если (A + C — B) кратно 11, то есть (ABC)

Давайте возьмем 4-значный номер сейчас.
ABCD = 1001A + D + 11C — C + 999B + B — A
= (1001A — 999B + 11C) + (D + B — A-C)
Итак, если (B + D — A — C) кратно 11, то ABCD.

Это можно продолжить для всех десятичных чисел.
Вышеупомянутое понятие может быть доказано для 3 в двоичных числах таким же образом.

Сложность времени:
O (logn)

Программа:

C ++

// Программа CPP для проверки, если n кратно 3
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция для проверки, если n кратно 3 * /

int isMultipleOf3(int n)

{

    int odd_count = 0;

    int even_count = 0;

  

    / * Не ставьте положительный результат, если + n кратно 3

    тогда это -n. Мы делаем это, чтобы избежать

    переполнение стека в рекурсии * /

    if (n < 0)

        n = -n;

    if (n == 0)

        return 1;

    if (n == 1)

        return 0;

  

    while (n) {

        / * Если установлен нечетный бит, то

        счетчик нечётного приращения * /

        if (n & 1)

            odd_count++;

  

        / * Если установлен четный бит

        приращение четного счетчика * /

        if (n & 2)

            even_count++;

        n = n >> 2;

    }

  

    return isMultipleOf3(abs(odd_count - even_count));

}

  
/ * Программа для проверки функции isMultipleOf3 * /

int main()

{

    int num = 24;

    if (isMultipleOf3(num))

        printf("%d is multiple of 3", num);

    else

        printf("%d is not a multiple of 3", num);

    return 0;

}

Джава

// Java программа для проверки
// n кратно 3

import java.lang.*;

import java.util.*;

  

class GFG {

    // Функция для проверки, если n

    // кратно 3

    static int isMultipleOf3(int n)

    {

        int odd_count = 0;

        int even_count = 0;

  

        / * Не ставьте положительный результат, если + n кратно

    из 3, то есть -n. Мы делаем это, чтобы

    избежать переполнения стека в рекурсии * /

        if (n < 0)

            n = -n;

        if (n == 0)

            return 1;

        if (n == 1)

            return 0;

  

        while (n != 0) {

            / * Если установлен нечетный бит, то

        счетчик нечётного приращения * /

            if ((n & 1) != 0)

                odd_count++;

  

            / * Если установлен четный бит

        приращение четного счетчика * /

            if ((n & 2) != 0)

                even_count++;

  

            n = n >> 2;

        }

  

        return isMultipleOf3(Math.abs(odd_count - even_count));

    }

  

    / * Программа для проверки функции isMultipleOf3 * /

    public static void main(String[] args)

    {

        int num = 24;

  

        if (isMultipleOf3(num) != 0)

            System.out.println(num + " is multiple of 3");

        else

            System.out.println(num + " is not a multiple of 3");

    }

}

  
// Этот код предоставлен Sahil_Bansall

python3

# Python profram, чтобы проверить, является ли n кратным 3

  
# Функция для проверки, если n кратно 3

def isMultipleOf3(n):

  

    odd_count = 0

    even_count = 0

  

    # Не делайте позитива, если + n кратно 3

    # тогда это -n. Мы делаем это, чтобы избежать

    # переполнение стека в рекурсии

    if(n < 0): 

        n = -n

    if(n == 0):

        return 1

    if(n == 1): 

        return 0

  

    while(n):

          

        # Если установлен нечетный бит, то

        # увеличение нечетного счетчика

        if(n & 1): 

            odd_count += 1

  

        # Если установлен четный бит

        # увеличить счетчик

        if(n & 2):

            even_count += 1

        n = n >> 2

  

    return isMultipleOf3(abs(odd_count - even_count))

  
# Программа для тестирования функции isMultipleOf3

num = 24

if (isMultipleOf3(num)): 

    print(num, 'is multiple of 3')

else:

    print(num, 'is not a multiple of 3')

  
# Этот код предоставлен Danish Raza

C #

// C # программа для проверки
// n кратно 3

using System;

  

class GFG {

  

    // Функция для проверки, если n

    // кратно 3

    static int isMultipleOf3(int n)

    {

        int odd_count = 0, even_count = 0;

  

        / * Не ставьте положительный результат, если + n кратно

        из 3, то есть -n. Мы делаем это, чтобы

        избежать переполнения стека в рекурсии * /

        if (n < 0)

            n = -n;

        if (n == 0)

            return 1;

        if (n == 1)

            return 0;

  

        while (n != 0) {

  

            / * Если установлен нечетный бит, то

            счетчик нечётного приращения * /

            if ((n & 1) != 0)

                odd_count++;

  

            / * Если установлен четный бит

            приращение четного счетчика * /

            if ((n & 2) != 0)

                even_count++;

  

            n = n >> 2;

        }

  

        return isMultipleOf3(Math.Abs(odd_count - even_count));

    }

  

    // Код драйвера

    public static void Main()

    {

        int num = 24;

  

        if (isMultipleOf3(num) != 0)

            Console.Write(num + " is multiple of 3");

        else

            Console.Write(num + " is not a multiple of 3");

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для проверки, если n
// кратно 3

  

  
// Функция для проверки, если n
// кратно 3

function isMultipleOf3( $n)

{

    $odd_count = 0;

    $even_count = 0;

  

    // Не делай позитива, если + n

    // кратен 3, то равен -n.

    // Мы делаем это, чтобы избежать

    // переполнение стека в рекурсии

    if($n < 0) $n = -$n;

    if($n == 0) return 1;

    if($n == 1) return 0;

  

    while($n)

    {

        // Если установлен нечетный бит

        // увеличиваем нечетный счетчик

        if($n & 1) 

        $odd_count++;

  

        // Если установлен четный бит

        // увеличиваем четный счетчик

        if($n & 2)

            $even_count++;

        $n = $n >> 2;

    }

  

    return isMultipleOf3(abs($odd_count

                             $even_count));

}

  
// Код драйвера

$num = 24;

if (isMultipleOf3($num)) 

    echo $num, "is multiple of 3";

else

    echo $num, "is not a multiple of 3";

      
// Этот код предоставлен vt_m.
?>


Выход :

24 is multiple of 3

Статьи по Теме:
Проверьте делимость в двоичном потоке
Отдел DFA

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Напишите эффективный метод, чтобы проверить, является ли число кратным 3

0.00 (0%) 0 votes