Counting Sort Algorithm
Counting sort runs on relatively smaller set of input. Counting sort calculates…
August 27, 2019
Given a signed integer, reverse digits of an integer.
Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
Return 0 for Integer overflow
The algorithm should be simple. You fetch the last digit. For next round, you need to move this to next digit place, and add next last digit.
You need to get last digit from number, and multiply last result by 10 to move it to next place.
s = s*10 + remainder;
We will do two calculations
Overflow cases
:
Note, max limit for 64-bit integer: 2^(64-1) - 1 = 2147483647
case 1
: Multiplication is itself overflowed:
Operation we will do: s10, we can check if s10 > Integer.MAXVALUE
OR, s > Integer.MAXVALUE/10case 2
: if s10 is equal to Integer.MAX_VALUE, Which means the number will be *214748364
multiply it with 10 will give: 21474836470
So, we need to check the remainder (which is to be added), if it is greater than 7, it is an overflow.public class Q7_ReverseInteger {
public int reverse(int x) {
boolean neg = false;
if (x < 0) {
//negative number
neg = true;
x = -x;
}
int s = 0;
while (x > 0) {
int rem = x%10;
if (s > Integer.MAX_VALUE/10 || (s == Integer.MAX_VALUE/10 && rem > 7)) {
return 0;
}
s = s*10 + rem;
x = x/10;
}
if (neg) {
return -s;
}
return s;
}
}
It is equal to the number of digits of the number. O(l)
Counting sort runs on relatively smaller set of input. Counting sort calculates…
Problem Statement Given a string s, return the maximum number of unique…
This is kind of preliminary technique of sorting. And, this is the first…
A Binary tree is a data structure which has two children nodes attached to it…
This algorithm is very useful for large input. And, is quite efficient one. It…
This topic is one of the most common studied. When somebody started preparation…
Problem Statement You are given a string text of words that are placed among…
Problem Statement You are given a rows x cols matrix grid. Initially, you are…
Problem Statement Given a string s, return the maximum number of unique…
Problem The Leetcode file system keeps a log each time some user performs a…
Problem Statement Replace all spaces in a string with ‘%20’ (three characters…
Problem Implement an algorithm to determine if a string has all the characters…