Check if a large number is divisible by 13 or not |
您所在的位置：网站首页 › 451728 › Check if a large number is divisible by 13 or not |
|
Given a large number, the task is to check if the number is divisible by 13 or not. Examples : Input : 637Output : 637 is divisible by 13.Input : 920Output : 920 is not divisible by 13.Input : 83959092724Output : 83959092724 is divisible by 13. Recommended: Please try your approach on {IDE} first, before moving on to the solution.If the given number num is small, we can easily find whether it is divisible by 13 or not by doing num % 13 and checking whether the result is 0 or not. But what about very large numbers? Let’s discuss large numbers. Below are some interesting facts about the divisibility of 13. A number is divisible by 13 if and if the alternating sum (alternatively adding and subtracting) of blocks of three from right to left is divisible by 13. For example, 2911285 is divisible by 13 because the alternating sum of blocks of size 3 is 2 – 911 + 285 = -650 which is divisible by 13. A number is divisible by 13 if and only if the number obtained by adding the last digit multiplied by 4 to the rest is also divisible by 13. For example, consider 2353. Applying above rule, we get 235 + 3*4 = 247. Again we apply the rule and get 24 + 7*4 = 52. Since 52 is divisible by 13, the given number is divisible by 13.Below is the implementation based on first fact above (Finding the alternating sum of blocks of size 3) C++
// CPP program to check // whether a number is // divisible by 13 or not. #include using namespace std; // Returns true if number // is divisible by 13 else // returns false bool checkDivisibility(string num) { int length = num.size(); if (length == 1 && num[0] == '0') return true; // Append required 0s . // at the beginning. if (length % 3 == 1) { // Same as strcat(num, "00"); // in c. num +="00"; length += 2; } else if (length % 3 == 2) { // Same as strcat(num, "0"); // in c. num += "0"; length += 1; } // Alternatively add/subtract // digits in group of three // to result. int sum = 0, p = 1; for (int i = length - 1; i >= 0; i--) { // Store group of three // numbers in group variable. int group = 0; group += num[i--] - '0'; group += (num[i--] - '0') * 10; group += (num[i] - '0') * 100; sum = sum + group * p; // Generate alternate series // of plus and minus p *= (-1); } sum = abs(sum); return (sum % 13 == 0); } // Driver code int main() { string number = "83959092724"; if (checkDivisibility(number)) cout Output 83959092724 is divisible by 13. Time Complexity: O(length(number))Auxiliary Space: O(1) Method: Checking given number is divisible by 13 or not by using the modulo division operator “%”. C++
#include using namespace std; int main() { //input long int n = 83959092724L; // finding given number is divisible by 13 or not if ((n) % 13 == 0) { cout Output Yes Time Complexity: O(1)Auxiliary Space: O(1) Method 3: 1. Initialize an integer variable alternating_sum to 0 and a variable multiplier to -1.2. While num is greater than 0, perform the following steps: a. Add multiplier * (num % 10) to alternating_sum. b. Multiply multiplier by -1. c. Divide num by 10.3. Check if alternating_sum is divisible by 13. If it is, return true. Otherwise, return false. C++
#include bool is_divisible_by_13(int num) { int alternating_sum = 0; int multiplier = -1; while (num > 0) { alternating_sum += multiplier * (num % 10); multiplier *= -1; num /= 10; } // checking if divisible by 13 or not return alternating_sum % 13 == 0; } int main() { if (is_divisible_by_13(12)) std::cout 0) { alternatingSum += multiplier * (num % 10); multiplier *= -1; num = Math.floor(num / 10); } // checking if divisible by 13 or not return alternatingSum % 13 === 0; } if (isDivisibleBy13(12)) { console.log("Yes"); // False } else { console.log("No"); } Output No Time Complexity: O(log10(n))Auxiliary Space: O(1) Method: Using lookup table method The remainders list contains the precomputed remainders of all numbers from 0 to 12 when divided by 13. The remainders for negative numbers are obtained by subtracting them from 13. The is_divisible_by_13() function takes a number as an input. It splits the number into blocks of three digits from right to left using the modulo operator and integer division. Each block represents a number in the range [0, 999]. It computes the remainders of each block using the precomputed values and updates the remainder variable accordingly. The formula used to compute the remainder of a block is (remainder * 1000 + block) % 13. This is based on the fact that 1000 % 13 is 8, which means that 10^n % 13 is 1 for all n >= 3. Therefore, we can compute the remainder of a block by multiplying the current remainder by 1000, adding the block to it, and taking the remainder when divided by 13. If the final remainder is 0, then the function returns True, indicating that the number is divisible by 13. Otherwise, it returns False. C++
#include #include using namespace std; bool isDivisibleBy13(long long number) { vector remainders = {0, 1, 2, 3, 4, 5, -1, -2, -3, -4, -5, 1, 0}; // Split the number into blocks of three digits from right to left vector blocks; while (number > 0) { blocks.push_back(number % 1000); number /= 1000; } // Compute the remainders of each block using the precomputed values int remainder = 0; for (int i = blocks.size() - 1; i >= 0; i--) { remainder = remainders[(remainder * 1000 + blocks[i]) % 13]; } // If the final remainder is 0, then the number is divisible by 13 return remainder == 0; } int main() { long long number = 83959092724; if (isDivisibleBy13(number)) { cout 0) { blocks.push(number % 1000); number = Math.floor(number / 1000); } // Compute the remainders of each block using the precomputed values let remainder = 0; for (let i = blocks.length - 1; i >= 0; i--) { remainder = remainders[(remainder * 1000 + blocks[i]) % 13]; } // If the final remainder is 0, then the number is divisible by 13 return remainder === 0; } const number = 83959092724; if (isDivisibleBy13(number)) { console.log(number + " is divisible by 13."); } else { console.log(number + " is not divisible by 13."); } Output 83959092724 is divisible by 13. Time complexity:The time complexity of the is_divisible_by_13() function depends on the number of blocks in the input number. The number of blocks is at most ceil(log10(number)/3), which is O(log(number)). The precomputation of the remainders takes constant time. The computation of each block’s remainder takes constant time. Therefore, the overall time complexity is O(log(number)). Auxiliary space:The space complexity of the is_divisible_by_13() function is O(1), as it uses only a constant amount of extra space to store the remainders of all numbers from 0 to 12. The number of blocks is at most ceil(log10(number)/3), which is also O(1) in terms of space complexity. Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule. Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks! DSA in C++ DSA in Java DSA in Python DSA in JavaScript |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |