Number system coding pattern

Print digits right to left

https://maang.in/problems/Digits-1207?resourceUrl=cs99-cp503-pl3382-rs1207&returnUrl=/dashboard

Description

Given a number N. Print the digits of that number from right to left separated by space.

Input Format

First line contains a number T number of test cases. Next T lines will contain a number N.

Output Format

For each test case print a single line contains the digits of the number separated by space.

Constraints

1≤T≤10

0≤N≤10^9

Approach#1: Convert to string and then reverse

Time complexity: O(k) here k is length of number

#include <bits/stdc++.h>
using namespace std;

void solve(long n) {
    string number = to_string(n);
    reverse(number.begin(), number.end());
    string ans;
    accumulate(number.begin()+1, number.end(), ans, [](string acc, char &digit){
        acc.append(" ");
        acc.append(digit);
        return acc;
    });
    cout << ans << endl;
}
int main() {
    int t;
    cin >> t;
    for (int i=0; i < t;i++) {
        long n;
        cin >>n;
        solve(n);
    }
    return 0;
}

Approach#2: Divide by 10 to get the digits

Time complexity: O(klogk) here k= length of number and log is with base 10.

#include <bits/stdc++.h>
using namespace std;
void solve(long n) {
    if (n == 0) {
        cout << 0 << endl;
        return;
    }
    while(n > 0) {
        cout << n % 10;
        n = n/10;
        if(n > 0) {
            cout <<" ";
        }
    }
    cout << endl;
}
int main() {
    int t;
    long n;
    cin >> t;
    for (int i=0; i < t;i++) {
        cin >>n;
        solve(n);
    }
    return 0;
}

Lucky Numbers

https://maang.in/problems/Lucky-Numbers-1209?resourceUrl=cs99-cp503-pl3382-rs1209&returnUrl=/dashboard

Description

Given two numbers A and B. Print all lucky numbers between A and B inclusive.

Note:

The Lucky number is any positive number that its decimal representation contains only 4 and 7.

For example: numbers 4,7,474,7,47 and 744744 are lucky and numbers 5,175,17 and 174174 are not.

Input Format

Only one line containing two numbers A and B.

Output Format

Print all lucky numbers between A and B inclusive separated by a space and in sorted order. If there is no lucky number print −1.

Constraints

1≤A≤B≤10^5

Approach#1: Use bfs to generate the number

BFS generates sorted order.

#include <bits/stdc++.h>
using namespace std;
bool found = false;
void luckyNumber (int num, int a, int b) {
    queue<int> q;
    q.push(0);
    while(!q.empty()) {
        int node = q.front();
        if(node > b) {
            return;
        }
        if(node >=a) {
            found = true;
            cout << node << " ";
        }
        q.pop();

        q.push(node*10  + 4);
        q.push(node*10 + 7);
    }
}

void solve(int a, int b) {
    luckyNumber(0, a, b);
}
int main() {
    int a,b;
    cin >>a>>b;
    solve(a,b);
    if(!found) {
        cout <<-1;
    }
    return 0;
}

Approach #6: Use dfs to generate lucky number

Since dfs doesn’t guarantee sorted order therefore sort it once get result.

#include <bits/stdc++.h>
using namespace std;
bool found = false;
void luckyNumber (long num, int a, int b, vector<int>& ans) {
   if(num > b) {
    return;
   }
   if(num >=a) {
    ans.push_back(num);
   }
   luckyNumber(num*10 + 4, a, b, ans);
   luckyNumber(num*10 + 7, a, b, ans);
}

void solve(int a, int b) {
    vector<int> ans;
    luckyNumber(0, a, b, ans);
    sort(ans.begin(), ans.end());
    if(ans.size() == 0) {
        cout << -1;
    } else {
        for (auto num : ans) {
            cout << num << " ";
        }
    }
}
int main() {
    int a,b;
    cin >>a>>b;
    solve(a,b);
    return 0;
}

Approach #3: Using block size iteration

#include <bits/stdc++.h>
using namespace std;
bool found = false;
int countDigits (int n) {
    return n == 0? 1: floor(log10(abs(n))) + 1;
}
void luckyNumber (int i, int number, int a, int b) {
    if(i == -1) {
        // If not in range
        if(number <a || number > b) {
            return;
        }      
        found = true;  
        // print number
        cout <<number << " ";
        return;
    }
    // We have two choices at ith position
    luckyNumber(i-1, number * 10 + 4, a,b);
    luckyNumber(i-1, number * 10 + 7, a, b);
}
void solve(int a, int b) {
    int min = countDigits(a);
    int max = countDigits(b);
    for(int len=min; len <= max; len++) {
        luckyNumber(len-1, 0,a,b);
    }
}
int main() {
    int a,b;
    cin >>a>>b;
    solve(a,b);
    if(!found) {
        cout <<-1;
    }
    return 0;
}

2802. Find The K-th Lucky Number

https://leetcode.com/problems/find-the-k-th-lucky-number/description/

We know that 4 and 7 are lucky digits. Also, a number is called lucky if it contains only lucky digits.

You are given an integer k, return the kth lucky number represented as a string.

Example 1:

Input: k = 4
Output: "47"
Explanation: The first lucky number is 4, the second one is 7, the third one is 44 and the fourth one is 47.

Approach # 1 (TLE): Use BFS to generate kth number

class Solution {
public:
    string kthLuckyNumber(int k) {
        queue<long> q;
        q.push(4);
        q.push(7);
        int count = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                count++;
                long node = q.front();
                q.pop();
                if (count == k) {
                    return to_string(node);
                }
                q.push(node * 10 + 4);
                q.push(node * 10 + 7);
            }
        }
        return "";
    }
};

Approach#2: Convert into binary number and increment in per block

class Solution {
private:
    vector<int> convertToBinary(int num, int block) {
        vector<int> binary(block);
        int i = block - 1;
        while (num != 0) {
            binary[i] = num % 2;
            num = num / 2;
            i--;
        }
        return binary;
    }
    int getBlock(int n) { return floor(log2(n + 2)) - 1; }
    int totalTillBlock(int x) {
        if (x < 0) {
            return 0;
        }
        return pow(2, x + 1) - 2;
    }

public:
    string kthLuckyNumber(int k) {
        // Find block for k
        int block = getBlock(k - 1);
        int prev = totalTillBlock(block);
        int pos = k - 1 - prev;
        vector<int> binary = convertToBinary(pos, block + 1);
        string ans;
        for (auto digit : binary) {
            ans.push_back(digit == 0 ? '4' : '7');
        }
        return ans;
    }
};

7. Reverse Integer

https://leetcode.com/problems/reverse-integer/description

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Approach #1: Apply reverse string concept with overflow check

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function (x) {
    const reverse = parseInt(Math.abs(x).toString().split('').reverse().join(''));
    if (reverse > 2 ** 31) return 0;
    return reverse * Math.sign(x);
};

179. Largest Number

https://leetcode.com/problems/largest-number/description/

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]
Output: "210"

Approach

1. First, we convert each integer to a string.
2. Sorting the numbers in descending order might seem like a good idea, but it leads to issues when numbers share the same leading digit.
3. For example, sorting [9, 5, 34, 3, 30] in descending order gives "9534303", but the correct answer is "9534330".
4. The problem arises because "3" and "30" share the same leading digit.
5. To fix this, we compare the concatenated results of pairs of numbers. For example, given two numbers a and b, we compare a + b and b + a (where + denotes string concatenation). If a + b is larger, we place a before b. This ensures that the numbers are ordered correctly for the largest possible result.

Following is code for reference.

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function (nums) {
    const tokens = nums.map(a => String(a));
    const comparator = (a, b) => {
        const num1 = parseInt(a + b);
        const num2 = parseInt(b + a);
        // Sort in descreasing order
        return -num1 + num2;
    }
    tokens.sort(comparator);
    const result = tokens.join('');
    // handle largest number as zero
    if (result[0] === '0') {
        return '0';
    }
    return result;
};

Primes from 1 to n

Description

Given a number N. Print all prime numbers between 1 and N inclusive.

A prime number is a number that is greater than 1 and has only two factors which are 1 and itself. In other words : prime number divisible only by 1 and itself. Be careful that 1 is not prime.

The first few prime numbers are 2,3,5,7,11…

Input Format

Only one line containing a number N.

Output Format

Print all prime numbers between 1 and N (inclusive) separated by a space.

Approach#1: Iterate and test each number for primary (TLE)

#include <bits/stdc++.h>
using namespace std;
bool isPrime (int num) {
    for (int i=2; i <= sqrt(num); i++) {
        if(num % i == 0) {
            return false;
        }
    }
    return true;
}
void solve(int n) {
    for (int i=2; i <=n; i++) {
        if(isPrime(i) ) {
            cout <<i<<" ";
        }
    }
}

int main() {
    int n;
    cin >> n;
    solve(n);
    return 0;
}

Approach #2: Using Sieve of Eratosthenes Algorithm

Intuition

1. Every multiple of primary numbers are not a primary number
2. Once we find the primary number then we can set rest of p*p as prime=false

Following are details to apply this approach.

1. Create a boolean array is_prime of size (N+1), initialized with true values for all elements.
2. Loop through the array is_prime from 2 to the square root of N (inclusive), and for each prime number p found in the loop:
3. If is_prime[p] is true, loop through the multiples of p from p*p up to N, and mark them as false in the is_prime array.
4. Loop through the array is_prime from 2 to N (inclusive), and for each index i where is_prime[i] is true, print i as a prime number.

#include <bits/stdc++.h>
using namespace std;
void solve(int n) {
    vector<bool> primes(n+1, true);
    primes[0] = false;
    primes[1] = false;
    for (int p=2; p <= sqrt(n); p++) {
        if(primes[p] ) {
           // Every multiple of primary numbers are not a primary number
           for (int i = p*p; i <=n; i+=p) {
                primes[i] = false;
           }
        }
    }
    for (int i=0; i < n+1; i++) {
        if(primes[i]) {
            cout << i << " ";
        }
    }
}

int main() {
    int n;
    cin >> n;
    solve(n);
    return 0;
}

Time complexity: O(sqrt(n)​loglogn + n)

991. Broken Calculator

https://leetcode.com/problems/broken-calculator/description

There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:

• multiply the number on display by 2, or
• subtract 1 from the number on display.

Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator.

Example 1:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Approach 1# Using BFS (TLE+Overflow)

We can use startValue as starting node and derive two neighbors as given operation and search for target. Every level of BFS on this graph will be treated as one operation.

The first match target will give the minimum number of operations. But this will lead to Overflow+TLE for many test cases. Following is code for reference.

class Solution {
public:
    int brokenCalc(int startValue, int target) {
        queue<int> q;
        unordered_set<int> visited;
        int height = 0;
        q.push(startValue);
        visited.insert(startValue);
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int node = q.front();
                q.pop();
                // if found the target
                if (node == target) {
                    return height;
                }
                // Two neighbors
                vector<int> neighbors = {node * 2, node - 1};
                for (int neighbor : neighbors) {
                    if (visited.count(neighbor) == 0) {
                        // launch bfs again by adding into queue
                        q.push(neighbor);
                        visited.insert(neighbor);
                    }
                }
            }
            height++; // At least one operation is applied
        }
        return -1;
    }
};

Approach #2: Work backwards

Instead of multiplying by 2 or subtracting 1 from startValue, we could divide by 2 (when target is even) or add 1 to target.

The motivation for this is that it turns out we always greedily divide by 2:

• If say target is even, then if we perform 2 additions and one division, we could instead perform one division and one addition for less operations [(target + 2) / 2 vs target / 2 + 1].
• If say target is odd, then if we perform 3 additions and one division, we could instead perform 1 addition, 1 division, and 1 addition for less operations [(target + 3) / 2 vs (target + 1) / 2 + 1].

Following is code for reference.

class Solution {
public:
    int brokenCalc(int startValue, int target) {
        int ans = 0;
        while(target > startValue) {
            ans++;
            if(target % 2 == 1) { // in case of odd
                target++;
            } else {
                target /= 2; // in case of even
            }
        }
        return ans + startValue - target;
    }
};

Happy learning :-)