Проверить, делится ли число на 3

Дано число x. Преобразуйте x в строку. Анализируйте строковый символ за символом. Преобразуйте каждый проанализированный символ в число (используя atoi ()) и сложите все эти числа в новое число y. Повторяйте процесс до тех пор, пока окончательное число не станет длиной в одну цифру. Если эта одна цифра равна 3,6 или 9, исходное число x делится на 3.

Число, делящееся на 3, iirc имеет такую ​​характеристику, что сумма его цифр делится на 3. Например,

12 -> 1 + 2 = 3
144 -> 1 + 4 + 4 = 9

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

Если это 3, 6 или 9, то число делится на 3.

Разделите номер на цифры. Сложите цифры вместе. Повторяйте, пока у вас не останется только одна цифра. Если эта цифра 3, 6 или 9, число делится на 3. (И не забывайте обрабатывать 0 как особый случай).

Вопрос интервью по сути просит вас придумать (или уже знать) сокращенное правило делимости с 3 в качестве делителя.

Одно из правил делимости для 3 звучит так:

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

Пример:

16,499,205,854,376
=> 1+6+4+9+9+2+0+5+8+5+4+3+7+6 sums to 69
=> 6 + 9 = 15 => 1 + 5 = 6, which is clearly divisible by 3.

См. также

• Wikipedia/Divisibility rule - имеет много правил для многих делителей

Хотя техника преобразования в строку и последующего сложения десятичных цифр элегантна, она либо требует деления, либо неэффективна на этапе преобразования в строку. Есть ли способ применить эту идею непосредственно к двоичному числу, без предварительного преобразования в строку десятичных цифр?

Оказывается, есть:

Учитывая двоичное число, сумма его нечетных разрядов минус сумма четных разрядов делится на 3, если исходное число делится на 3.

В качестве примера возьмем число 3726, которое делится на 3. В двоичном виде это 111010001110. Возьмем нечетные разряды, начиная справа и двигаясь влево, это [1, 1, 0, 1, 1, 1, 1]; их сумма равна 5. Четные биты - [0, 1, 0, 0, 0, 1]; их сумма равна 2. 5 - 2 = 3, из чего можно сделать вывод, что исходное число делится на 3.

Все текущие ответы сосредоточены на десятичных цифрах, когда применяется прием "сложить все цифры и посмотреть, делится ли это на 3". На самом деле этот трюк работает и в шестнадцатеричной системе; например, 0x12 можно разделить на 3, потому что 0x1 + 0x2 = 0x3. И "конвертировать" в шестнадцатеричную систему гораздо проще, чем в десятичную.

Pseudo-code:

int reduce(int i) {
  if (i > 0x10)
    return reduce((i >> 4) + (i & 0x0F)); // Reduces 0x102 to 0x12 to 0x3.
  else
   return i; // Done.
}
bool isDiv3(int i) {
  i = reduce(i);
  return i==0 || i==3 || i==6 || i==9 || i==0xC || i == 0xF;
}

[edit] Вдохновленный R, более быстрая версия (O log log N):

int reduce(unsigned i) {
  if (i >= 6)
    return reduce((i >> 2) + (i & 0x03));
  else
   return i; // Done.
}
bool isDiv3(unsigned  i) {
  // Do a few big shifts first before recursing.
  i = (i >> 16) + (i & 0xFFFF);
  i = (i >> 8) + (i & 0xFF);
  i = (i >> 4) + (i & 0xF);
  // Because of additive overflow, it's possible that i > 0x10 here. No big deal.
  i = reduce(i);
  return i==0 || i==3;
}

Число делится на 3, если все цифры в числе при сложении дают результат 3, 6 или 9. Например, 3693 делится на 3 как 3 + 6 + 9 + 3 = 21 и 2 + 1 = 3 и 3 делится на 3.

Вы не пометьте этот C, но поскольку вы упомянули atoi , я собираюсь дать решение C:

int isdiv3(int x)
{
    div_t d = div(x, 3);
    return !d.rem;
}