Move all zeroes to end of number

How to Add leading Zeros to a Number in Python

Difference Between Linear Search and Jump Search

Given a number N, the task is to move all zeroes in the number to the end.

Examples:

Input: N = 230404
Output: 234400
Explanation: After moving all the zeros to the end, 230404 becomes 234400

Input: N = 1004
Output: 1400
Explanation: After moving all the zeros to the end, 1004 becomes 1400.

Approach: To solve the problem, follow the below idea:

Find the number of digits in the input number. Maintain a variable, say ans to store the number after moving all zeros to the end. Then, one by one extract the digits from left to right and check if the digit is non-zero or not. If the digit is non-zero then multiply ans by 10 and add the current digit to ans. After traversing all the digits, multiply ans by 10 till the number of digits in ans becomes equal to the number of digits in the input number.

Step-by-step algorithm:

Find the number of digits, say digitCnt in input number.
Maintain a variable, say ans = 0 to store the number after moving all the zeros to the end.
Extract digits from the input number from the most significant digit to the least significant digit.
If the current digit is non-zero, then multiply ans by 10 and add the current digit to ans.
Else, move to the next digit.
After iterating over all the digits, fill the remaining positions of ans with zeros.

Below is the implementation of the approach:

C++

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

// function to return the number after shifting all the
// zeros to the end
int solve(int n)
{
    if (n == 0)
        return 0;

    // Count the number of digits in input number
    int temp = n, digitCnt = 0;
    while (temp) {
        temp /= 10;
        digitCnt += 1;
    }

    // Extract all the digits from most significant digit to
    // least significant digit
    int divisor = pow(10, digitCnt - 1);
    int ans = 0, digitCnt2 = 0;
    temp = n;
    while (divisor > 0) {
        int digit = temp / divisor;
        if (digit != 0) {
            ans = ans * 10 + digit;
            digitCnt2 += 1;
        }
        temp = temp % divisor;
        divisor /= 10;
    }

    // Fill the remaining last digits with zeros
    while (digitCnt2 < digitCnt) {
        ans = ans * 10;
        digitCnt2 += 1;
    }
    return ans;
}

int main()
{
    // Sample Input
    int n = 230404;

    cout << solve(n);

    return 0;
}

Output

Time complexity: O(log₁₀(N)), where N is the input number.
Auxiliary Space: O(1)

Tags:

#DSA #Mathematical #Mathematical

How to Add leading Zeros to a Number in Python

Difference Between Linear Search and Jump Search

Move all zeroes to end of number

Contact Us