Find next greater number with same set of digits

Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”.
Examples:

For simplicity of implementation, we have considered input number as a string.

Input:  n = "218765"
Output: "251678"

Input:  n = "1234"
Output: "1243"

Input: n = "4321"
Output: "Not Possible"

Input: n = "534976"
Output: "536479"

Following are few observations about the next greater number.
1) If all digits sorted in descending order, then output is always “Not Possible”. For example, 4321.
2) If all digits are sorted in ascending order, then we need to swap last two digits. For example, 1234.
3) For other cases, we need to process the number from rightmost side (why? because we need to find the smallest of all greater numbers)
You can now try developing an algorithm yourself.
Following is the algorithm for finding the next greater number.
I) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.
II) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.
III) Swap the above found two digits, we get 536974 in above example.
IV) Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479” which is the next greater number for input 534976.


Following is implementation of above approach.

#include <iostream> #include <cstring> #include <algorithm> using namespace std; void swap(char *a, char *b) {     char temp = *a;     *a = *b;     *b = temp; } void findNext(char number[], int n) {     int i, j;          for (i = n-1; i > 0; i--)         if (number[i] > number[i-1])            break;          if (i==0)     {         cout << "Next number is not possible";         return;     }          int x = number[i-1], smallest = i;     for (j = i+1; j < n; j++)         if (number[j] > x && number[j] < number[smallest])             smallest = j;          swap(&number[smallest], &number[i-1]);          sort(number + i, number + n);     cout << "Next number with same set of digits is " << number;     return; } // Driver program to test above function int main() {     char digits[] = "534976";     int n = strlen(digits);     findNext(digits, n);     return 0; }

Output:

Next number with same set of digits is 536479

The above implementation can be optimized in following ways.
1) We can use binary search in step II instead of linear search.
2) In step IV, instead of doing simple sort, we can apply some clever technique to do it in linear time. Hint: We know that all digits are linearly sorted in reverse order except one digit which was swapped.
With above optimizations, we can say that the time complexity of this method is O(n).

Evaluation of Expression Tree

Given a simple expression tree, consisting of basic binary operators i.e., + , – ,* and / and some integers, evaluate the expression tree.
Examples:

Input :
Root node of the below tree


Output :
100

Input :
Root node of the below tree


Output :
110

We strongly recommend you to minimize your browser and try this yourself first.

As all the operators in the tree are binary hence each node will have either 0 or 2 children. As it can be inferred from the examples above , the integer values would appear at the leaf nodes , while the interior nodes represent the operators.
To evaluate the syntax tree , a recursive approach can be followed .

Algorithm :
Let t be the syntax tree
If  t is not null then
      If t.info is operand then  
         Return  t.info
      Else
         A = solve(t.left)
         B = solve(t.right)
         return A operator B
         where operator is the info contained in t

The time complexity would be O(n), as each node is visited once. Below is a C++ program for the same:

// C++ program to evaluate an expression tree #include <bits/stdc++.h> using namespace std;   // Class to represent the nodes of syntax tree class node { public:     string info;     node *left = NULL, *right = NULL;     node(string x)     {         info = x;     } };   // Utility function to return the integer value // of a given string int toInt(string s) {     int num = 0;     for (int i=0; i<s.length();  i++)         num = num*10 + (int(s[i])-48);     return num; }   // This function receives a node of the syntax tree // and recursively evaluates it int eval(node* root) {     // empty tree     if (!root)         return 0;       // leaf node i.e, an integer     if (!root->left && !root->right)         return toInt(root->info);       // Evaluate left subtree     int l_val = eval(root->left);       // Evaluate right subtree     int r_val = eval(root->right);       // Check which operator to apply     if (root->info=="+")         return l_val+r_val;       if (root->info=="-")         return l_val-r_val;       if (root->info=="*")         return l_val*r_val;       return l_val/r_val; }   //driver function to check the above program int main() {     // create a syntax tree     node *root = new node("+");     root->left = new node("*");     root->left->left = new node("5");     root->left->right = new node("4");     root->right = new node("-");     root->right->left = new node("100");     root->right->right = new node("20");     cout << eval(root) << endl;       delete(root);       root = new node("+");     root->left = new node("*");     root->left->left = new node("5");     root->left->right = new node("4");     root->right = new node("-");     root->right->left = new node("100");     root->right->right = new node("/");     root->right->right->left = new node("20");     root->right->right->right = new node("2");       cout << eval(root);     return 0; }

Output:

100
110

Default Methods In Java

Before Java 8, interfaces could have only abstract methods. The implementation of these methods has to be provided in a separate class. So, if a new method is to be added in an interface then its implementation code has to be provided in the class implementing the same interface. To overcome this issue, Java 8 has introduced the concept of default methods which allow the interfaces to have methods with implementation without affecting the classes that implement the interface.

// A simple program to Test Interface default // methods in java interface TestInterface {     // abstract method     public void square(int a);       // default method     default void show()     {       System.out.println("Default Method Executed");     } }   class TestClass implements TestInterface {     // implementation of square abstract method     public void square(int a)     {         System.out.println(a*a);     }       public static void main(String args[])     {         TestClass d = new TestClass();         d.square(4);           // default method executed         d.show();     } }

Output:

 16
 Default Method Executed

The default methods were introduced to provide backward comparability so that existing intefaces can use the lambda expressions without implementing the methods in the implementation class. Default methods are also known as defender methods or virtual extension methods.
Static Methods:
The interfaces can have static methods as well which is similar to static method of classes.

// A simple Java program to TestClassnstrate static // methods in java interface TestInterface {     // abstract method     public void square (int a);       // static method     static void show()     {         System.out.println("Static Method Executed");     } }   class TestClass implements TestInterface {     // Implementation of square abstract method     public void square (int a)     {         System.out.println(a*a);     }       public static void main(String args[])     {         TestClass d = new TestClass();         d.square(4);           // Static method executed         TestInterface.show();     } }

Output:

 16
 Static Method Executed

Default Methods and Multiple Inheritance
In case both the implemented interfaces contain deafult methods with same method signature, the implementing class should explicitly specify which default method is to be used or it should override the default method.

// A simple Java program to demonstrate multiple // inheritance through default methods. interface TestInterface1 {     // default method     default void show()     {         System.out.println("Default TestInterface1");     } }   interface TestInterface2 {     // Default method     default void show()     {         System.out.println("Default TestInterface2");     } }   // Implementation class code class TestClass implements TestInterface1, TestInterface2 {     // Overriding default show method     public void show()     {         // use super keyword to call the show         // method of TestInterface1 interface         TestInterface1.super.show();           // use super keyword to call the show         // method of TestInterface2 interface         TestInterface2.super.show();     }       public static void main(String args[])     {         TestClass d = new TestClass();         d.show();     } }

Output:

Default TestInterface1
Default TestInterface2

Important Points:

1. Interfaces can have default methods with implementation from java 8 onwards.
2. Interfaces can have static methods as well similar to static method of classes.
3. Default methods were introduced to provide backward comparability for old interfaces so that they can have new methods without effecting existing code.

Find minimum adjustment cost of an array

Given an array of positive integers, replace each element in the array such that the difference between adjacent elements in the array is less than or equal to a given target. We need to minimize the adjustment cost, that is the sum of differences between new and old values. We basically need to minimize ∑|A[i] – A_new[i]| where 0 <= i <= n-1, n is size of A[] and A_new[] is the array with adjacent difference less that or equal to target.
Assume all elements of the array is less than constant M = 100.
Examples:

Input: arr = [1, 3, 0, 3], target = 1
Output: Minimum adjustment cost is 3
Explanation: One of the possible solutions 
is [2, 3, 2, 3]

Input: arr = [2, 3, 2, 3], target = 1
Output: Minimum adjustment cost is 0
Explanation:  All adjacent elements in the input 
array are already less than equal to given target

Input: arr = [55, 77, 52, 61, 39, 6, 
             25, 60, 49, 47], target = 10
Output: Minimum adjustment cost is 75
Explanation: One of the possible solutions is 
[55, 62, 52, 49, 39, 29, 30, 40, 49, 47]

We strongly recommend you to minimize your browser and try this yourself first.

In order to minimize the adjustment cost ∑|A[i] – A_new[i]| for all index i in the array, |A[i] – A_new[i]| should be as close to zero as possible. Also, |A[i] – A_new[i+1] ]| <= Target.
This problem can be solved by dynamic programming.
Let dp[i][j] defines minimal adjustment cost on changing A[i] to j, then the DP relation is defined by –

dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|
           for all k's such that |k - j| <= target

Here, 0 <= i < n and 0 <= j <= M where n is number of elements in the array and M = 100. We have to consider all k such that max(j – target, 0) <= k <= min(M, j + target)
Finally, the minimum adjustment cost of the array will be min{dp[n – 1][j]} for all 0 <= j <= M.
Below is C++ implementation of above idea –

// C++ program to find minimum adjustment cost of an array #include <bits/stdc++.h> using namespace std;   #define M 100   // Function to find minimum adjustment cost of an array int minAdjustmentCost(int A[], int n, int target) {     // dp[i][j] stores minimal adjustment cost on changing     // A[i] to j     int dp[n][M + 1];       // handle first element of array seperately     for (int j = 0; j <= M; j++)         dp[0][j] = abs(j - A[0]);       // do for rest elements of the array     for (int i = 1; i < n; i++)     {         // replace A[i] to j and calculate minimal adjustment         // cost dp[i][j]         for (int j = 0; j <= M; j++)         {           // initialize minimal adjustment cost to INT_MAX           dp[i][j] = INT_MAX;             // consider all k such that k >= max(j - target, 0) and           // k <= min(M, j + target) and take minimum           for (int k = max(j-target,0); k <= min(M,j+target); k++)              dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(A[i] - j));         }     }          // return minimum value from last row of dp table     int res = INT_MAX;     for (int j = 0; j <= M; j++)         res = min(res, dp[n - 1][j]);       return res; }   // Driver Program to test above functions int main() {     int arr[] = {55, 77, 52, 61, 39, 6, 25, 60, 49, 47};     int n = sizeof(arr) / sizeof(arr[0]);     int target = 10;       cout << "Minimum adjustment cost is "          << minAdjustmentCost(arr, n, target) << endl;       return 0; }

Output:

Minimum adjustment cost is 75

Replace every element with the least greater element on its right

Given an array of integers, replace every element with the least greater element on its right side in the array. If there are no greater element on right side, replace it with -1.
Examples:

Input: [8, 58, 71, 18, 31, 32, 63, 92, 
         43, 3, 91, 93, 25, 80, 28]
Output: [18, 63, 80, 25, 32, 43, 80, 93, 
         80, 25, 93, -1, 28, -1, -1]

We strongly recommend you to minimize your browser and try this yourself first.

A naive method is to run two loops. The outer loop will one by one pick array elements from left to right. The inner loop will find the smallest element greater than the picked element on its right side. Finally the outer loop will replace the picked element with the element found by inner loop. The time complexity of this method will be O(n²).
A tricky solution would be to use Binary Search Trees. We start scanning the array from right to left and insert each element into the BST. For each inserted element, we replace it in the array by its inorder successor in BST. If the element inserted is the maximum so far (i.e. its inorder successor doesn’t exists), we replace it by -1.
Below is C++ implementation of above idea –

// C++ program to replace every element with the // least greater element on its right #include <iostream> using namespace std;   // A binary Tree node struct Node {     int data;     Node *left, *right; };   // A utility function to create a new BST node Node* newNode(int item) {     Node* temp = new Node;     temp->data = item;     temp->left = temp->right = NULL;       return temp; }   /* A utility function to insert a new node with    given data in BST and find its successor */ void insert(Node*& node, int data, Node*& succ) {     /* If the tree is empty, return a new node */     if (node == NULL)         node = newNode(data);       // If key is smaller than root's key, go to left     // subtree and set successor as current node     if (data < node->data)     {         succ = node;         insert(node->left, data, succ);     }       // go to right subtree     else if (data > node->data)         insert(node->right, data, succ); }   // Function to replace every element with the // least greater element on its right void replace(int arr[], int n) {     Node* root = NULL;       // start from right to left     for (int i = n - 1; i >= 0; i--)     {         Node* succ = NULL;           // insert current element into BST and         // find its inorder successor         insert(root, arr[i], succ);           // replace element by its inorder         // successor in BST         if (succ)             arr[i] = succ->data;         else    // No inorder successor             arr[i] = -1;     } }   // Driver Program to test above functions int main() {     int arr[] = { 8, 58, 71, 18, 31, 32, 63, 92,                   43, 3, 91, 93, 25, 80, 28 };     int n = sizeof(arr)/ sizeof(arr[0]);       replace(arr, n);       for (int i = 0; i < n; i++)         cout << arr[i] << " ";       return 0; }

Output:

18 63 80 25 32 43 80 93 80 25 93 -1 28 -1 -1

Worst case time complexity of above solution is also O(n²) as it uses BST. The worst case will happen when array is sorted in ascending or descending order. The complexity can easily be reduced to O(nlogn) by using balanced trees like red-black trees.

Palindromic Primes

A palindromic prime (sometimes called a palprime) is a prime number that is also a palindromic number.

Given a number n, print all palindromic primes smaller than or equal to n. For example, If n is 10, the output should be “2, 3, 5, 7′. And if n is 20, the output should be “2, 3, 5, 7, 11′.
Idea is to generate all prime numbers smaller than or equal to given number n and checking every prime number whether it is palindromic or not.
Methods used

• To find if a given number is prime or not.
• To check whether the given number is palindromic number or not.

Below is the C++ implementation of above algorithm:

// C++ Program to print all palindromic primes // smaller than or equal to n. #include<bits/stdc++.h> using namespace std;   // A function that reurns true only if num // contains one digit int oneDigit(int num) {     // comparison operation is faster than     // division operation. So using following     // instead of "return num / 10 == 0;"     return (num >= 0 && num < 10); }   // A recursive function to find out whether // num is palindrome or not. Initially, dupNum // contains address of a copy of num. bool isPalUtil(int num, int* dupNum) {     // Base case (needed for recursion termination):     // This statement/ mainly compares the first     // digit with the last digit     if (oneDigit(num))         return (num == (*dupNum) % 10);       // This is the key line in this method. Note     // that all recursive/ calls have a separate     // copy of num, but they all share same copy     // of *dupNum. We divide num while moving up     // the recursion tree     if (!isPalUtil(num/10, dupNum))         return false;       // The following statements are executed when     // we move up the recursion call tree     *dupNum /= 10;       // At this point, if num%10 contains i'th     // digit from beiginning, then (*dupNum)%10     // contains i'th digit from end     return (num % 10 == (*dupNum) % 10); }   // The main function that uses recursive function // isPalUtil() to find out whether num is palindrome // or not int isPal(int num) {     // If num is negative, make it positive     if (num < 0)        num = -num;       // Create a separate copy of num, so that     // modifications made to address dupNum don't     // change the input number.     int *dupNum = new int(num); // *dupNum = num       return isPalUtil(num, dupNum); }   // Function to generate all primes and checking // whether number is palindromic or not void printPalPrimesLessThanN(int n) {     // Create a boolean array "prime[0..n]" and     // initialize all entries it as true. A value     // in prime[i] will finally be false if i is     // Not a prime, else true.     bool prime[n+1];     memset(prime, true, sizeof(prime));       for (int p=2; p*p<=n; p++)     {         // If prime[p] is not changed, then it is         // a prime         if (prime[p] == true)         {             // Update all multiples of p             for (int i=p*2; i<=n; i += p)                 prime[i] = false;         }     }       // Print all palindromic prime numbers     for (int p=2; p<=n; p++)          // checking whether the given number is        // prime palindromic or not        if (prime[p] && isPal(p))           cout << p << " "; }   // Driver Program int main() {     int n = 200;     printf("Palindromic primes smaller than or "            "equal to %d are :\n", n);     printPalPrimesLessThanN(n); }

Output:

Palindromic primes smaller than or equal to 100 are :
2 3 5 7 11 

To Generate a One Time Password or Unique Identification URL

A one-time password (OTP) is a password that is valid for only one login session or transaction, on a computer system or other digital device.

Applications

• OTPs are widely used in websites like- Facebook, Google Sign-in, Wifi – accessing, Railways Portal Login etc.

How it gets generated ?
Well it is a great possibility that they uses the same algorithm as an OTP is generated. If by chance (very rare) the unique string generated is already been generated before and has been associated with a different code then another random string is used.
As per now it seems that only six character strings are generated randomly for a unique identification of all codes. A time will come when all the possible six character strings may get exhausted. So yes, even the web-related stuffs also heavily relies on randomness.
Probability of collision of two OTPs

• The length of OTP is 6 and the set size of all possible characters in the OTP is 62. So the total number of possible sets of the pair of OTPs are 62¹².
• Some of them are – [{aaaaaa, aaaaaa}, {aaaaaa, aaaaab},…..{456789, 456788}, {456789, 456789}]
• But the possible sets of equal pair of OTPs are:62⁶. Some of them are – [{aaaaaa, aaaaaa}, {aaaaab, aaaaab},…..{456788, 456788}, {456789, 456789}]
• Hence the probability of collision of two OTPs is:
  62⁶ / 62¹² = 1 / 62⁶ = 1 / 56800235584 = 1.7605561^-11

So the probability of two OTPs colliding are as less probable as the existence of your life on earth (Ratio of the number of years you will live to the number of years from the start of the universe and everything in existence).So yes,OTPs are way more secure than static passwords !


Implementation

// A C/C++ Program to generate OTP (One Time Password) #include<bits/stdc++.h> using namespace std;   // A Function to generate a unique OTP everytime string generateOTP(int len) {     // All possible characters of my OTP     string str = "abcdefghijklmnopqrstuvwxyzABCD"                "EFGHIJKLMNOPQRSTUVWXYZ0123456789";     int n = str.length();       // String to hold my OTP     string OTP;       for (int i=1; i<=len; i++)         OTP.push_back(str[rand() % n]);       return(OTP); }   // Driver Program to test above functions int main() {     // For different values each time we run the code     srand(time(NULL));       // Delare the length of OTP     int len = 6;     printf("Your OTP is - %s", generateOTP(len).c_str());       return(0); }

Output (May be different for every run):

Your OTP is - 8qOtzy

Time Complexity: O(N), where N = number of characters in our OTP
Auxiliary Space: Apart from the string having all possible characters we require O(N) space to hold the OTP, where N = number of characters in our OTP.


Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.