http://www.geeksforgeeks.org/count-words-whose-th-letter-either-1-th-th-i1-th-letter-given-word/
http://www.geeksforgeeks.org/maximize-sum-n-x-n-upper-left-sub-matrix-given-2n-x-2n-matrix/
http://www.geeksforgeeks.org/queries-sum-prime-factor-counts-range/
http://www.geeksforgeeks.org/reversible-numbers/
Program To check if a number is reversible or not
Program To count total reversible numbers upto n
http://www.geeksforgeeks.org/program-for-goldbachs-conjecture-two-primes-with-given-sum/
http://www.geeksforgeeks.org/number-maximum-number-prime-factors/
http://www.geeksforgeeks.org/nearest-element-least-one-common-prime-factor/
http://www.geeksforgeeks.org/summation-gcd-pairs-n/
Given a string str. The task is to count the words having the same length as str and each letter at the i-th position is either (i-1)-th, i-th, or (i+1)-th position letter of str.
Note: For the first letter consider i-th and (i+1)-th position letter of W. And for last letter consider (i-1)-th and i-th position letter of str.
For any letter at index i, except first and last letter, there are three possible letter i.e (i-1)th, ith or (i+1)th letter of given words. So, if three of them are distinct, we have 3 possibilities. If two of them are same, we have 2 possibilities. And if all are same we have only 1 possibility.
So, traverse the given words and find the possibility of each letter and multiply them.
So, traverse the given words and find the possibility of each letter and multiply them.
Similarly, for first letter check the distinct letter at first and second position. And for last position check the distinct letter at last and second last position.
int countWords(char str[], int len){ int count = 1; // If word contain single letter, return 1. if (len == 1) return count; // Checking for first letter. if (str[0] == str[1]) count *= 1; else count *= 2; // Traversing the string and multiplying // for combinations. for (int j=1; j<len-1; j++) { // If all three letters are same. if (str[j] == str[j-1] && str[j] == str[j+1]) count *= 1; // If two letter are distinct. else if (str[j] == str[j-1] || str[j] == str[j+1] || str[j-1] == str[j+1]) count *= 2; // If all three letter are distinct. else count *= 3; } // Checking for last letter. if (str[len - 1] == str[len - 2]) count *= 1; else count *= 2; return count;}
Given a 2N x 2N matrix of integers. You are allowed to reverse any row or column any number of times and in any order. The task is to calculate the maximum sum of the upper-left N X N submatrix i.e the sum of elements of submatrix from (0, 0) to (N – 1, N – 1).
To maximize the sum of upper-left submatrix, observe, for each cell of the top-left submatrix, there are four candidates, meaning the corresponding cells in the top-left, top-right, bottom-left, and bottom-right submatrices that it can be swapped with.
Now, observe for each cell, wherever it is, we can swap it with the corresponding candidate value in the top-left submatrix without changing the order of the other cells in the top-left submatrix.The diagram show for an instance where the maximum value of the 4 candidates is in the top-right submatrix. If its is in the bottom-left or bottom-right submatrices, we can first reverse a row or column to put it in the top-right submatrix and then follow the same sequence of operations as shown in diagram.
In this matrix, let say a26 is the maximum of the 4 candidates and a23 must be swapped with a26without changing the order of the cells in the top-left submatrix.
Now, observe for each cell, wherever it is, we can swap it with the corresponding candidate value in the top-left submatrix without changing the order of the other cells in the top-left submatrix.The diagram show for an instance where the maximum value of the 4 candidates is in the top-right submatrix. If its is in the bottom-left or bottom-right submatrices, we can first reverse a row or column to put it in the top-right submatrix and then follow the same sequence of operations as shown in diagram.
In this matrix, let say a26 is the maximum of the 4 candidates and a23 must be swapped with a26without changing the order of the cells in the top-left submatrix.
int maxSum(int mat[R][C]){ int sum = 0; for (int i = 0; i < R/2; i++) for (int j = 0; j < C/2; j++) { int r1 = i; int r2 = R - i - 1; int c1 = j; int c2 = C - j - 1; // We can replace current cell [i, j] // with 4 cells without changing affecting // other elements. sum += max(max(mat[r1][c1], mat[r1][c2]), max(mat[r2][c1], mat[r2][c2])); } return sum;}
There are Q queries. Each query is of the form of L and R. The task is to output sum of number of prime factors of each number in the given range of each query.
The idea is to use the Sieve of Eratosthenes method for counting the number of prime factor of composite numbers. Just like, the inner loop of Sieve of Eratosthenes is used to mark composite number. We can use it for incrementing the prime factor of numbers. Instead of marking each array cell as 0 or 1, we can store the number of prime number of that index. And then for each query, find the sum of array from L to R.
void sieve(int count []){ for (int i = 2; i*i <= MAX; i++) { // if i is prime if (count[i] == 0) { for (int j = 2*i; j < MAX; j+=i) count[j]++; // setting number of prime // factor of a prime number. count[i] = 1; } }}// Returns sum of counts of prime factors in// range from l to r. This function mainly// uses count[] which is filled by Sieve()int query(int count[], int l, int r){ int sum = 0; // finding the sum of number of prime // factor of numbers in a range. for (int i = l; i <= r; i++) sum += count[i]; return sum;}Program To check if a number is reversible or not
void checkReversible (int n){ int rev = 0, rem; // Calculate reverse of n int flag = n; while (flag) { rem = flag % 10; rev *= 10; rev += rem; flag /= 10; } // Calculate sum of number // and its reverse int sum = rev + n; // Check for reverse number // reach digit must be odd while (sum && (rem % 2 != 0)) { rem = sum % 10; sum /= 10; } if (sum == 0) cout << "Reversible Number"; else cout << "Non-Reversible Number";}Program To count total reversible numbers upto n
- 1 digit number: Any one digit number will add to itself, which always be an even number, And thus there are no solutions.
- 2 digits number: Both digits must be odd.
- If a+b > 10 ,then we have a carryover and thus the first digit of the result will have a different parity than the second digit.
- So, Solutions can only be formed where a+b < 10 and a + b is odd. So, total 20 such numbers are possible.
- 3 digits number:
- The middle digit needs to be added to itself. That means that the third digit must have a carryover and be odd.
- Since the third digit is odd the first digit is odd as well if the second digit does not have a carryover, which happens when the second digit is less than 5, which gives us 20 choices for the first/third digit set and 5 options for the middle.So, totals 100 pairs.
- 4 digits number: There are two pairs, say the inner and outer pair.
- If the inner pair has carryover then the outer pair must also have carryover.
- Otherwise, the two inner pairs will have different parity.
- If the inner pair has carryover then the outer pair will have different parity since the first digit will end up with a carry over which the last digit would not get.
- Therefore we have solutions only when none of the pairs have carry over.
- In total: For the outer pair, this gives us the 20 choices we have seen in the two digit case. And it gives us 30 cases for the inner pair since they can also contain a zero.
Or in total we get 20*30 = 600 solutions.
- 5, 9, 13.. digits number: No solution as 1-digit number.
- 6, 8, 10.. digits number: Same as 2-digits number i.e. if n = 2*k then total solution = 20*30^(k-1).
- 7, 11, 15.. digits number: Same as 3-digits number i.e if n = 4k + 3 then total solution = 100*500^(k).
Generalizing the Solution:
- All even numbered digits(2, 4, 6, 8..) have the same formula so we can generalize
that for some integer k such that n = 2k we have 20*30^(k-1) solutions
which represents the outer pair along with all the inner pairs. - For n (3, 7, 11..) of form 4k + 3 (k is an integer), we have that the middle digit and
the outer pair gives us 5 and 20 options, as in the case of 3 digit number.
Then we have sets of internal pairs which gives us 20 and 25 solutions.
So that means we can generalize it to 20*5*(20*25)^(k) = 100*500^(k). - For n of form 4k+ 1 which means 1, 5, 9.. none of these have any solutions.
void countReversible (int n){ int count = 0; // Calculate counts of // reversible number of 1 to n-digits for ( int i = 1; i <= n; i++) { // All four possible cases and their formula switch (i % 4) { // for i of form 2k case 0: case 2: count += 20 * pow( 30, ( i / 2 - 1)); break; // for i of form 4k + 3 case 3: count += 100 * pow ( 500, i / 4 ); break; // for i of form 4k + 1 no solution case 1: break; } } cout << count;}
Goldbach’s conjecture is one of the oldest and best-known unsolved problems in number theory of mathematics. Every even integer greater than 2 can be expressed as the sum of two primes.
- Find the prime numbers using Sieve of Sundaram
- Check if entered number is an even number greater than 2 or not, if no return.
- If yes, then one by one subtract a prime from N and then check if the difference is also a prime, if yes then express it as a sum.
// Utility function for Sieve of Sundaramvoid sieveSundaram(){ // In general Sieve of Sundaram, produces primes smaller // than (2*x + 2) for a number given number x. Since // we want primes smaller than MAX, we reduce MAX to half // This array is used to separate numbers of the form // i + j + 2*i*j from others where 1 <= i <= j bool marked[MAX/2 + 100] = {0}; // Main logic of Sundaram. Mark all numbers which // do not generate prime number by doing 2*i+1 for (int i=1; i<=(sqrt(MAX)-1)/2; i++) for (int j=(i*(i+1))<<1; j<=MAX/2; j=j+2*i+1) marked[j] = true; // Since 2 is a prime number primes.push_back(2); // Print other primes. Remaining primes are of the // form 2*i + 1 such that marked[i] is false. for (int i=1; i<=MAX/2; i++) if (marked[i] == false) primes.push_back(2*i + 1);}// Function to perform Goldbach's conjecturevoid findPrimes(int n){ // Return if number is not even or less than 3 if (n<=2 || n%2 != 0) { cout << "Invalid Input \n"; return; } // Check only upto half of number for (int i=0 ; primes[i] <= n/2; i++) { // find difference by subtracting current prime from n int diff = n - primes[i]; // Search if the difference is also a prime number if (binary_search(primes.begin(), primes.end(), diff)) { // Express as a sum of primes cout << primes[i] << " + " << diff << " = " << n << endl; return; } }}
Given an integer N. The task is to find a number that is smaller than or equal to N and has maximum prime factors. In case there are two or more numbers with same maximum number of prime factors, find the smallest of all.
Use sieve method to count number of prime factor of each number less than N. And find the minimum number having maximum count.
int maxPrimefactorNum(int N){ int arr[N + 5]; memset(arr, 0, sizeof(arr)); // Sieve of eratosthenes method to count // number of prime factors. for (int i = 2; i*i <= N; i++) { if (!arr[i]) for (int j = 2*i; j <= N; j+=i) arr[j]++; arr[i] = 1; } int maxval = 0, maxint = 1; // Finding number having maximum number // of prime factor. for (int i = 1; i <= N; i++) { if (arr[i] > maxval) { maxval = arr[i]; maxint = i; } } return maxint;}
Generate all prime number before N using Sieve. Now, multiply consecutive prime numbers (starting from first prime number) one after another until the product is less than N.
int maxPrimefactorNum(int N){ bool arr[N + 5]; memset(arr, true, sizeof(arr)); // Sieve of eratosthenes for (int i = 3; i*i <= N; i += 2) { if (!arr[i]) for (int j = i*i; j <= N; j+=i) arr[j] = false; } // Storing prime numbers. vector<int> prime; prime.push_back(2); for(int i = 3; i <= N; i += 2) if(arr[i]) prime.push_back(i); // Generating number having maximum prime factors. int i = 0, ans = 1; while (ans*prime[i] <= N && i < prime.size()) { ans *= prime[i]; i++; } return ans;}http://www.geeksforgeeks.org/nearest-element-least-one-common-prime-factor/
Given an array arr[], find nearest element for every element such that there is at least one common prime factor. In output, we need to print position of closest element.
Input: arr[] = {2, 9, 4, 3, 13}
Output: 3 4 1 2 -1
Explanation :
Closest element for 1st element is 3rd.
=>Common prime factor of 1st and 3rd elements
is 2.
Closest element for 2nd element is 4th.
=>Common prime factor of 2nd and 4th elements
is 3.
We find prime factors of all array elements. To quickly find prime factors, we use Sieve of Eratosthenes. For every element, we consider all prime factors and keep track of closest element with common factor.
Time complexity: O(MAX * log(log (MAX) ) )
Auxiliary space: O(MAX)
Auxiliary space: O(MAX)
const int MAX = 100001;const int INF = INT_MAX;int primedivisor[MAX], dist[MAX], pos[MAX], divInd[MAX];vector<int> divisors[MAX];// Pre-computation of smallest prime divisor// of all numbersvoid sieveOfEratosthenes(){ for (int i=2; i*i < MAX; ++i) { if (!primedivisor[i]) for (int j = i*i; j < MAX; j += i) primedivisor[j] = i; } // Prime number will have same divisor for (int i = 1; i < MAX; ++i) if (!primedivisor[i]) primedivisor[i] = i;}// Function to calculate all divisors of// input arrayvoid findDivisors(int arr[], int n){ for (int i=0; i<MAX; ++i) pos[i] = divInd[i] = -1, dist[i] = INF; for (int i=0; i<n; ++i) { int num = arr[i]; while (num > 1) { int div = primedivisor[num]; divisors[i].push_back(div); while (num % div == 0) num /= div; } }}void nearestGCD(int arr[], int n){ // Pre-compute all the divisors of array // element by using prime factors findDivisors(arr, n); // Traverse all elements, for (int i=0; i<n; ++i) { // For every divisor of current element, // find closest element. for (auto &div: divisors[i]) { // Visit divisor if not visited if (divInd[div] == -1) divInd[div] = i; else { // Fetch the index of visited divisor int ind = divInd[div]; // Update the divisor index to current index divInd[div] = i; // Set the minimum distance if (dist[i] > abs(ind-i)) { // Set the min distance of current // index 'i' to nearest one dist[i] = abs(ind-i); // Add 1 as indexing starts from 0 pos[i] = ind + 1; } if (dist[ind] > abs(ind-i)) { // Set the min distance of found index 'ind' dist[ind] = abs(ind-i); // Add 1 as indexing starts from 0 pos[ind] = i + 1; } } } }}
Common prime factor will only exist if GCD of these two numbers will greater than 1. Simple brute force is to run the two loops one inside the another and iterate one by one from each index to both the sides simultaneously and find the gcd which is greater than 1. Whenever we found the answer then just break the loop and the print. If we reached the end of array after traversing both the sides then simply print -1.
void nearestGcd(int arr[], int n){ // Loop covers the every element of arr[] for (int i=0; i<n; ++i) { int closest = -1; // Loop that covers from 0 to i-1 and i+1 // to n-1 indexes simultaneously for (int j=i-1, k=i+1; j>0 || k<=n; --j, ++k) { if (j>=0 && __gcd(arr[i], arr[j]) > 1) { closest = j+1; break; } if (k<n && __gcd(arr[i], arr[k])>1) { closest = k+1; break; } } // print position of closest element cout << closest << " "; }}
Given a number N, find sum of all GCDs that can be formed by selecting all the pairs from 1 to N.
