Some Math / Number Theory Tricks

-
2#  A number N can be represented by the difference of the square of two numbers that means it is possible to find two integers p and q such that 
N = p^2 - q^2

If

N is Odd or N is divisible by 4.
        If we named this type of number is a good number then
     2.1# If two number A and B both are good number then the product of them are also must be a good number

3# If a array / sequence have N element then total number of subarray / contigious_subsequence is n(n+1)/2
















<<<<<<<<<<<<<<<<<<<<<<<<<<<<**************>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>


Comments

Post a Comment

Popular posts from this blog

Longest Palindromic Substring

-
Today we will discuss a common problem. The problem is, you are given a string S, you have to find the longest palindromic substring in S. For example, S = abcbsd, here our desired answer is bcb with length 3. Solution: This problem can be solved in many ways. One of them is DP solution and another is Expand Around Center. DP: DP solution is a very straight cut solution. We go through all the substrings of the main string S and check each substring is palindrome or not and find the longest substring if it is palindrome. Here we do DP in the palindrome checking part. Here is the Code. Complexity O(n^2) . #include<bits/stdc++.h> using namespace std ;   string s ; int dp [ 1005 ] [ 1005 ] ; ///dp[l][r] means is substring s[l...r] is a palindrome or not   int isPalindrome ( int left, int right ) { if ( left >= right ) return 1 ; if ( dp [ left ] [ right ] ! = - 1 ) return dp [ left ] [ right ] ; int result = 0 ; if ( s ...
Read more

Number Of Divisors (NOD)

-
Number of Divisors(NOD) Given N you have to find the number of divisors of N. Solution: Step 1: Generating Prime using Sieve of Eratosthenes Step 2: Count Divisors using prime factorization CODE: long long NOD_using_factorization ( long long n ) /// O(lof2(N)) { long long sqrtn = sqrt ( n ) ; long long tmp = 1 ,divisors = 1 ; for ( int i = 0 ; i < prime. size ( ) && prime [ i ] <= sqrtn ; i ++ ) { ///if ( sieve[n] == 0 ) break; ///*Checks if n is prime or not*/ Please comment This line if n > 1e7 if ( n % prime [ i ] == 0 ) { tmp = 1 ; while ( n % prime [ i ] == 0 ) { n / = prime [ i ] ; tmp ++ ; } divisors * = tmp ; sqrtn = sqrt ( n ) ; ...
Read more

Chicken McNugget Theorem

-
Image
Problem Post #01 Given a positive integer N, determine whether you can make N by summing up some non-negative multiple of A and some non-negative multiple of B where A and are relatively prime numbers. ( একটা ধনাত্বক পূর্নসংখ্যা N দেয়া আছে । তোমাকে বলতে হবে N কে A এবং B এর গুনিতক এর যোগফল আকারে প্রকাশ করা যায় কিনা ।  অর্থাৎ N = xA + yB আকারে প্রকাশ করা যায় কিনা যেখানে x এবং y রিলেটিভ প্রাইম সংখ্যা ।  ) Solutions: The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) states that for any two relatively prime positive integers A, B, the greatest integer that cannot be written in the form xA + yB for nonnegative integers x, y is  AB - A - B. ( এই থিওরি মতে যেকোন দুইটা রিলেটিভ পজিটিভ প্রাইম সংখ্যা A এবং B এর জন্য সবচেয়ে বড় যে সংখ্যাটা xA + yB  ফর্ম এ লেখা যাবে না সেটা হলো A*B - A - B অর্থাৎ A*B - A - B  এর থেকে বড় সকল সংখ্যা  xA + yB আকারে প্রকাশ করা যাবে  ) A consequence of the theorem is that there are exactly  positive i...
Read more