Check if a larger number divisible by 36 - GeeksforGeeks


Check if a larger number divisible by 36 - GeeksforGeeks
Given a number, check whether a given number is divisible by 36 or not. The number may be very large and may not fit in any numeric(int, long int, float, etc.) data type.

 number is divisible by 36 if the number is divisible by 4 and 9
  1. A number is divisible by 4 if the number formed by its last 2 digits is divisible by 4
  2. A number is divisible by 9 if the sum of the digits of the number is divisible by 9
string divisibleBy36(string num)
{
    int l = num.length();
    // null number cannot
    // be divisible by 36
    if (l == 0)
        return "No";
    // single digit number other than
    // 0 is not divisible by 36
    if (l == 1 && num[0] != '0')
        return "No";
    // number formed by the last 2 digits
    int two_digit_num = (num[l-2] - '0')*10 +
                        (num[l-1] - '0') ;
    // if number is not divisible by 4
    if (two_digit_num%4 != 0)
        return "No";
    // number is divisible by 4 calculate
    // sum of digits
    int sum = 0;
    for (int i=0; i<l; i++)
        sum += (num[i] - '0');
    // sum of digits is not divisible by 9
    if (sum%9 != 0)
        return "No";
    // number is divisible by 4 and 9
    // hence, number is divisible by 36
    return "Yes";
}

http://www.geeksforgeeks.org/check-large-number-divisible-9-not/
Given a number, the task is to find if the number is divisible by 9 or not. The input number may be large and it may not be possible to store even if we use long long int.
A number is divisible by 9 if sum of its digits is divisible by 9.
http://www.geeksforgeeks.org/check-large-number-divisible-4-not/
A number is divisible by 4 if number formed by last two digits of it is divisible by 4.
http://www.geeksforgeeks.org/check-large-number-divisible-6-not/
Given a number, the task is to check if a number is divisible by 6 or not. The input number may be large and it may not be possible to store even if we use long long int.
A number is divisible by 6 it's divisible by 2 and 3. 
a)  A number is divisible by 2 if its last digit is divisible by 2.
b)  A number is divisible by 3 if sum of digits is divisible by 3.
bool check(string str)
{
    int n = str.length();
    // Return false if number is not divisible by 2.
    if ((str[n-1]-'0')%2 != 0)
       return false;
    // If we reach here, number is divisible by 2.
    // Now check for 3.
    // Compute sum of digits
    int digitSum = 0;
    for (int i=0; i<n; i++)
        digitSum += (str[i]-'0');
    // Check if sum of digits is divisible by 3
    return (digitSum % 3 == 0);
}

http://www.geeksforgeeks.org/check-large-number-divisible-8-not/
Given a number, the task is to check if a number is divisible by 8 or not. The input number may be large and it may not be possible to store even if we use long long int.
A number is divisible by 8 if number formed by last three digits of it is divisible by 8.
bool check(string str)
{
    int n = str.length();
    // Empty string
    if (n == 0)
        return false;
    // If there is single digit
    if (n == 1)
        return ((str[0]-'0')%8 == 0);
    // If there is double digit
    if (n == 2)
        return (((str[n-2]-'0')*10 + (str[n-1]-'0'))%8 == 0);
    // If number formed by last three digits is
    // divisible by 8.
    int last = str[n-1] - '0';
    int second_last = str[n-2] - '0';
    int third_last = str[n-3] - '0';
    return ((third_last*100 + second_last*10 + last) % 8 == 0);
}

http://www.geeksforgeeks.org/check-large-number-divisible-11-not/
Given a number, the task is to check if the number is divisible by 11 or not. The input number may be large and it may not be possible to store it even if we use long long int.
A number is divisible by 11 if difference of following two is divisible by 11.
  1. Sum of digits at odd places.
  2. Sum of digits at even places.
Let us consider 7694, we can write it as
7694 = 7*1000 + 6*100 + 9*10 + 4

The proof is based on below observation:
Remainder of 10i divided by 11 is 1 if i is even
Remainder of 10i divided by 11 is -1 if i is odd

So the powers of 10 only result in values either 1 
or -1. 

Remainder of "7*1000 + 6*100 + 9*10 + 4"
divided by 11 can be written as : 
7*(-1) + 6*1 + 9*(-1) + 4*1

The above expression is basically difference 
between sum of even digits and odd digits.
int check(string str)
{
    int n = str.length();
    // Compute sum of even and odd digit
    // sums
    int oddDigSum = 0, evenDigSum = 0;
    for (int i=0; i<n; i++)
    {
        // When i is even, position of digit is odd
        if (i%2 == 0)
            oddDigSum += (str[i]-'0');
        else
            evenDigSum += (str[i]-'0');
    }
    // Check its difference is divisble by 11 or not
    return ((oddDigSum - evenDigSum) % 11 == 0);
}

http://www.geeksforgeeks.org/write-an-efficient-method-to-check-if-a-number-is-multiple-of-3/
Write an Efficient Method to Check if a Number is Multiple of 3
The very first solution that comes to our mind is the one that we learned in school. If sum of digits in a number is multiple of 3 then number is multiple of 3 e.g., for 612 sum of digits is 9 so it’s a multiple of 3. But this solution is not efficient. You have to get all decimal digits one by one, add them and then check if sum is multiple of 3.
There is a pattern in binary representation of the number that can be used to find if number is a multiple of 3. If difference between count of odd set bits (Bits set at odd positions) and even set bits is multiple of 3 then is the number.
Example: 23 (00..10111)
1) Get count of all set bits at odd positions (For 23 it’s 3).
2) Get count of all set bits at even positions (For 23 it’s 1).
3) If difference of above two counts is a multiple of 3 then number is also a multiple of 3.
(For 23 it’s 2 so 23 is not a multiple of 3)
Above can be proved by taking the example of 11 in decimal numbers. (In this context 11 in decimal numbers is same as 3 in binary numbers)
If difference between sum of odd digits and even digits is multiple of 11 then decimal number is multiple of 11. Let’s see how.
Let’s take the example of 2 digit numbers in decimal
AB = 11A -A + B = 11A + (B – A)
So if (B – A) is a multiple of 11 then is AB.
Let us take 3 digit numbers.
ABC = 99A + A + 11B – B + C = (99A + 11B) + (A + C – B)
So if (A + C – B) is a multiple of 11 then is (A+C-B)
Let us take 4 digit numbers now.
ABCD = 1001A + D + 11C – C + 999B + B – A
= (1001A – 999B + 11C) + (D + B – A -C )
So, if (B + D – A – C) is a multiple of 11 then is ABCD.
int isMultipleOf3(int n)
{
    int odd_count = 0;
    int even_count = 0;
 
    /* Make no positive if +n is multiple of 3
       then is -n. We are doing this to avoid
       stack overflow in recursion*/
    if(n < 0)   n = -n;
    if(n == 0) return 1;
    if(n == 1) return 0;
 
    while(n)
    {
        /* If odd bit is set then
           increment odd counter */
        if(n & 1)
           odd_count++;
        n = n>>1;
 
        /* If even bit is set then
           increment even counter */
        if(n & 1)
            even_count++;
        n = n>>1;
    }
 
     return isMultipleOf3(abs(odd_count - even_count));
}
Read full article from Check if a larger number divisible by 36 - GeeksforGeeks

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts