ในที่นี้เราต้องเขียนโปรแกรมที่ใช้เช็คว่าตัวเลขที่ให้มานั้นคูณ 3 หรือไม่
คำตอบทั่วไปคือคำตอบที่ไม่สำคัญ โดยบวกตัวเลขทั้งหมดของตัวเลขนั้นและหากผลรวมเป็นทวีคูณของสาม ตัวเลขจะหารด้วย 3 ลงตัว ไม่เช่นนั้นจะไม่ใช่ แต่วิธีนี้ไม่มีประสิทธิภาพสูงสุด
วิธีแก้ปัญหาที่มีประสิทธิภาพจะใช้การนับบิตในการแทนค่าเลขฐานสองของตัวเลข หากผลต่างระหว่างการนับ set bit ที่ตำแหน่งคี่กับการนับ set bit ที่ตำแหน่งคู่เป็นทวีคูณของ 3 แสดงว่าจำนวนนั้นเป็นผลคูณของ 3
เราจะใช้การวนซ้ำและเลื่อนบิตของตัวเลขและนับจำนวนบิตที่เป็นตำแหน่งคู่และคี่ สุดท้ายเราจะคืนเช็คหากผลต่างเป็นทวีคูณของสาม
มาดูตัวอย่างเพื่อทำความเข้าใจการนำไปใช้
อินพุต
n = 24
ผลลัพธ์
even
คำอธิบาย
binary representation = 11000 Evensetbits = 1 , oddsetbits = 1. Difference = 0, it is divisible.
โปรแกรมแสดงการใช้งานโซลูชันของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int isDivisibleBy3(int n) {
int oddBitCount = 0;
int evenBitCount = 0;
if (n < 0)
n = -n;
if (n == 0)
return 1;
if (n == 1)
return 0;
while (n) {
if (n & 1)
oddBitCount++;
if (n & 2)
evenBitCount++;
n = n >> 2;
}
return isDivisibleBy3(oddBitCount - evenBitCount);
}
int main() {
int n = 1241;
cout<<"The number "<<n;
if (isDivisibleBy3(n))
cout<<" is a multiple of 3";
else
cout<<" is not a multiple of 3";
return 0;
} ผลลัพธ์
The number 1241 is not a multiple of 3
