Google Interview Question Software Engineer / Developers
Team: Knowledge Graph
Country: United States
Interview Type: In-Person
Array.sort is O(nLogN). To keep the total time complexity linear, just reverse the remaining digits as they are already sorted in descending manner from left to right.
And we don't have to search for minimum value on the right side of our found first_not_in_ascending_order digit. It would allways be rightmost digit. Because they are actually arranged in ascending order from right to left:)
I think the time complexity is O(log N)
Proof:
For Integer N , there are max of logN+1 digits , let K= log N
so,
1. For traversing over digits : O(K)
2. We know the digits range only from 0-9 , so we'll use bucket sort, radix sort algos instead of heap -r quick sort , hence for sorting O(K)
over all : O(K) => O(log N)
public class Solution {
public static int nextHigherPermutation(int number) {
int[] num = numberToArray(number);
nextPermutation(num);
int nextPermNumber = arrayToNumber(num);
return Math.max(number, nextPermNumber);
}
private static int arrayToNumber(int[] num) {
int number = 0;
int p = 10;
for (int i = 0; i < num.length; i++) {
number = number * p + num[i];
}
return number;
}
private static int[] numberToArray(int number) {
String numberString = String.valueOf(number);
int digits = numberString.length();
int[] num = new int[digits];
int i = 0;
for (char digit: numberString.toCharArray()){
num[i] = digit - '0';
i++;
}
return num;
}
public static void nextPermutation(int[] num) {
int i = num.length - 2;
boolean permFound = false;
while (i >= 0) {
int j = i + 1;
while (j < num.length) {
if (num[i] < num[j]) {
swap(num, i, j);
permFound = true;
break;
}
j++;
}
if (permFound)
break;
rotateLeft(num, i);
i--;
}
}
private static void rotateLeft(int[] num, int from) {
int temp = num[from];
for (int i = from; i < num.length - 1; i++) {
num[i] = num[i + 1];
}
num[num.length - 1] = temp;
}
private static void swap(int[] num, int indxi, int indxj) {
int temp = num[indxi];
num[indxi] = num[indxj];
num[indxj] = temp;
}
/**
* Example 1 : if num = 25468, o/p = 25486
* Example 2 : if num = 21765, o/p = 25167
* Example 3 : If num = 54321, o/p = 54321
*
* @param args
*/
public static void main(String[] args) {
System.out.println(nextHigherPermutation(25468));
System.out.println(nextHigherPermutation(21765));
System.out.println(nextHigherPermutation(54321));
}
}
//O(n) time complexity
public int nextHighNumber(int number){
int[] num = numberToArray(number);
int i = 0;
for(i = 0 ; i < num.length-1; i++){
if(num[i] > num[i+1]) break;
}
if(i == num.length-1) {
System.out.println("No number can be formed");
return 0;
}
int numi = num[i+1];
num[i+1] = num[0];
int temp = 0;
for(int j = 0; j <= i/2; j++){
temp = num[j];
num[j]=num[i-j];
num[i-j] = temp;
}
num[i]=numi;
return arrayToNumber(num);
}
public int[] numberToArray(int number){
System.out.println("Original number: " + number);
int[] num = new int[getNumberLength(number)];
int i = 0;
while(number > 0){
num[i] = number % 10;
number = number / 10;
System.out.print(num[i]);
i++;
}
System.out.println("\n" + "Converted number to array");
return num;
}
public int arrayToNumber(int[] num){
int number = 0;
for(int i = 0; i < num.length; i++){
number = number + num[i] * (int) Math.pow(10, i);
}
System.out.println("\n" + "Converted Array to number");
return number;
}
public int getNumberLength(int number){
int length = 0;
while(number > 0){
length++;
number = number / 10;
}
System.out.println("The length of number is: " + length);
return length;
}
class Solution:
# @param num, a list of integer
# @return a list of integer
def nextPermutation(self, num):
length = len(num)
if not num:
return []
i = length - 1
# find the last item which has at least one
# item that is greate than it and behind it.
# the item is num[j], the item that greater than
# it and behind it is mun[i]
max_j = -1
max_j_i = None
while i >= 0:
j = i - 1
while j >= 0:
if num[j] < num[i]:
if j > max_j:
max_j = j
max_j_i = i
break
j -= 1
i -= 1
j = max_j
i = max_j_i
if max_j != -1:
# it is not a descending array
num[i], num[j] = num[j], num[i]
for k in range(j + 1, length):
for l in range(k, length):
if num[k] > num[l]:
num[k], num[l] = num[l], num[k]
else:
# it is a descending array
return num
return num
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
public class getNextHigherNumber {
public static void main(String args[])throws IOException
{
try{
Scanner sc = new Scanner(System.in);
int number = sc.nextInt();
getHigher(number);
}
catch(java.util.InputMismatchException e)
{
System.out.println("Value is too big: "+ e.getMessage());
}
}
public static void getHigher(int number)
{
int num=number;
int len=0;
while(num>0)
{
len++;
num= num/10;
}
num=number;
int[] a = new int[len];
for(int i=a.length-1; i>=0; i--)
{
a[i]=num%10;
num=num/10;
}
int[] secondHalf = new int[a.length];
secondHalf[a.length-1]=a[a.length-1];
int i;
for(i=a.length-2; i>=0; i--)
{
if(a[i]>secondHalf[i+1]) //insert in the array
{
secondHalf[i]=a[i];
Arrays.sort(secondHalf);
}
else
{
secondHalf[i]=a[i];
int t = secondHalf[i];
secondHalf[i] = secondHalf[i+1];
secondHalf[i+1] = t;
break;
}
}
if(i-1>=0){
for(int j=i-1; j>=0; j--)
{
secondHalf[j]=a[j];
}
}
for(int j=0; j<secondHalf.length; j++)
{
System.out.print(secondHalf[j]); //print the next higher number
}
System.out.println();
}
}
integer to array, then scan from the last digit, if a[i] < a[i + 1] continue, until you find a pos to stop, if not found, then return the original number (cannot swap), else do:
let the number to be swapped is x = a[i + 1] (which is smaller than a[i])
find the position that a[p] > x (p is from 0 to i - 1, use binary search)
swap the a[p + 1] and x;
reverse the order of elements from 0 to i;
convert the array to integer and return it.
int* toarray(int x, int& size)
{
int n = x;
int l = 0;
while (n > 0)
{
n /= 10;
++l;
}
int* a = new int[l];
int p = 0;
n = x;
while (n > 0)
{
a[p] = n % 10;
n /= 10;
++p;
}
size = l;
return a;
}
int find(int x, int* a, int s, int e)
{
if (s == e)
{
if (a[s] < x)
return s;
else
return s - 1;
}
int mid = (s + e) / 2;
if (a[mid] > x)
return find(x, a, 0, mid - 1);
else
return find(x, a, mid + 1, e);
}
int toint(int* a, int p, int size)
{
int result = 0;
for (int i = size - 1; i > p; --i)
{
result = result * 10 + a[i];
}
for (int i = 0; i <= p; ++i)
{
result = result * 10 + a[i];
}
return result;
}
int nextbig(int n)
{
int size;
int *a = toarray(n, size);
for (int i = 0; i < size - 1; ++i)
{
if (a[i] > a[i + 1])
{
// swap a[i + 1] to the proper position
int pos = find(a[i + 1], a, 0, i) + 1;
a[i + 1] ^= a[pos];
a[pos] ^= a[i + 1];
a[i + 1] ^= a[pos];
return toint(a, i, size);
}
}
return n;
}
int _tmain(int argc, _TCHAR* argv[])
{
int x = 54321;
std::cout << nextbig(x) << "\n";
getchar();
}
#include<stdio.h>
#include<conio.h>
int main()
{
int n,i,j,k,ar[5],num,key,p;
printf("Enter no.: ");
scanf("%d",&n);
i=0;
p=n;
while(n>0) //seperating each digit
{ //and storing it in array.
ar[i]=n%10;
n=n/10;
i++;
}
num=ar[i-1]; //using last digit in num bcz num must be started with same digit i.e.
for(j=1;j<i-1;j++) //if number is 21567 then higher will be started from 2 and will be 25167
{
key=ar[j]; //appplying insertion sort on digits stored in array except last digit
k=j-1;
while((k>=0)&&ar[k]>key)
{
ar[k+1]=ar[k];
k=k-1;
ar[k+1]=key;
}
}
for(k=0;k<i-1;k++) //finding the smallest larger number from last digit
{ //i.e larger no than 2 in our example is 5 which is smallest
if(ar[k]>num) //of all larger no's.
{
j=k;
key=ar[k];
break;
}
}
num=num*10+key; //converting digits in number
k=0;
while(k<i-1)
{
if(k==j) //we need not to take that digit which is already has been used
{ //so if that location comes, just increment in k location
k++;
}
num=num*10+ar[k];
k++;
}
printf("\nThe next higher number of %d is %d",p,num);
getch();
return 0;
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class NextHighestNumber {
public static void main(String args[]) {
System.out.println(nextHighestNumber(25468));
System.out.println(nextHighestNumber(21765));
System.out.println(nextHighestNumber(54321));
}
public static int nextHighestNumber(int number) {
List<Integer> result = new ArrayList<Integer>();
createPermutations("", String.valueOf(number), result);
Collections.sort(result);
int index = result.indexOf(number);
return result.get(index == result.size() - 1 ? index : index + 1);
}
public static void createPermutations(String prefix, String str,
List<Integer> result) {
if (str.length() == 0) {
result.add(Integer.valueOf(prefix));
}
for (int i = 0; i < str.length(); i++) {
createPermutations(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1), result);
}
}
}
public class FindNumber {
public static void main(String argv[]) {
System.out.println(findGreater(25468));
System.out.println(findGreater(21765));
System.out.println(findGreater(54321));
}
private static int findGreater(int i) {
ArrayList<Integer> digits = new ArrayList<Integer>(); //Contains digits in the ascending order
//Break number into digits.
while (i > 0) {
digits.add(i % 10);
i /= 10;
}
for (int candidateDigit = 1; candidateDigit < digits.size(); candidateDigit++) {
if (digits.get(candidateDigit) < digits.get(candidateDigit - 1)) {
//We found digits[candidateDigit] breaks the ascending order.
//Swap it with smallest possible digit in the tail array [0, candidateDigit],
//in such way so after that, the tail array will be still in ascending order
for (int toSwap = 0; i < candidateDigit; i++) {
if (digits.get(toSwap) > digits.get(candidateDigit)) {
//digits[toSwap+1]>=digits[candidateDigit]>= digits[toSwap-1],
// so array is still in order
swap(digits, candidateDigit, toSwap);
break;
}
}
//Reverse the tail array
for (int index1 = 0; ; index1++) {
int index2 = candidateDigit - 1 - index1;
if (index1 < index2) swap(digits, index1, index2);
else break; //We are done reversing, indexes crossed
}
//We are done modifying the number, break out of the cycle
break;
}
}
//Assemble the number back
int result = 0;
for (int c = digits.size() - 1; c >= 0; c--) {
result *= 10;
result += digits.get(c);
}
return result;
}
private static void swap(ArrayList<Integer> digits, int index1, int index2) {
Integer swap = digits.get(index1);
digits.set(index1, digits.get(index2));
digits.set(index2, swap);
}
}
Pretty sure some simple thing like this in Ruby would work.
ARGV.each do |a|
nums = a.to_s.chars.map(&:to_i)
i = nums.length - 1
last = nums.last
nums.reverse_each {|n| (last > n) ? break : i-=1 }
nums[-1] = nums[i]
nums[i] = last
nums = nums[0..i] + nums[i+1..-1].sort unless i == -1
puts nums.map(&:to_s).join.to_i
end
And a slightly longer version in Python
import sys
for arg in sys.argv[1:]:
nums = map(int,list(str(arg)))
i = len(nums) - 1
last = nums[-1]
for n in reversed(nums):
if last > n:
break
i-=1
nums[-1] = nums[i]
nums[i] = last
if not i == -1:
nums = nums[:i+1] + sorted(nums[i+1:])
print ''.join(map(str,nums))
And finally a kind of ridiculous one line ruby script with no semi-colons
ARGV.each {|a| lambda {|b| puts b.reverse.each_with_index.inject([]){|ary, (elem, idx)| b.last > elem && ary.length < b.length ? (ary[0] = elem) && ary.sort!.reverse! && ary << b.last && ary+=b[0..b.length-idx-2].reverse : ary.length < b.length ? ary << elem : ary }.reverse.map(&:to_s).join("")}.call(a.to_s.chars.map(&:to_i))}
import java.io.*;
public class Qs4869907900530688 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
String number = br.readLine();
int length = number.length();
if (length > 0) {
char ch = number.charAt(length-1);
int exchangePosition = -1;
for (int i = length-2; i >= 0; --i) {
if (ch > number.charAt(i)) {
exchangePosition = i;
break;
}
}
if (exchangePosition == -1)
out.println(number);
else {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < exchangePosition; ++i)
sb.append(number.charAt(i));
sb.append(ch);
sb.append(number.charAt(exchangePosition));
for (int i = length-2; i > exchangePosition; --i)
sb.append(number.charAt(i));
out.println(sb.toString());
}
}
out.flush();
out.close();
System.exit(0);
}
}
int nextPermutation(int n){
int result, size, prev, next;
string number;
stringstream ss;
string::iterator itr;
// Converts n to char array (string)
ss << n;
ss >> number;
// Clears stream for next use
ss.str("");
ss.clear();
next = number.length()-1;
prev = next; // Starting point, usually equals next-1
itr = number.end();
while(next > -1){
// Sorts the right half
sort(itr, number.end());
itr--;
if(number[next] < number[prev]){
// Swaps numbers
number[prev] = number[prev] ^ number[next];
number[next] = number[prev] ^ number[next];
number[prev] = number[prev] ^ number[next];
// Converts back to int
ss << number;
ss >> result;
return result;
}
else{
prev = next;
next--;
}
}
return n;
}
int nNextHigher( int N )
{
assert( N >= 0 );
// Count # of digits
int nDigitCount = 0;
for( int nTemp = N; nTemp > 0; ++nDigitCount )
{
nTemp /= 10;
}
// Return current if 0/1 digit
if( nDigitCount <= 1 )
{
return N;
}
// Decompose into digits
vector<int> digits( nDigitCount, 0 );
for( int i = 0, nTemp = N; nTemp > 0; ++i, nTemp /= 10 )
{
digits[nDigitCount -1 - i] = nTemp % 10;
}
// Find first inverted digit
int nToggleIndex = -1;
for( int i = nDigitCount -2; i >= 0; --i )
{
if( digits[i] < digits[i+1] )
{
nToggleIndex = i;
break;
}
}
// If none found, return original N
int nNextHighestValue = N;
if( nToggleIndex != -1 )
{
// Build up set of all digits to the right of inverted index
multiset<int> nToggleDigits;
for( int i = nToggleIndex; i < nDigitCount; ++i )
{
nToggleDigits.emplace(digits[i]);
}
// Find the first value above the current value
int nCurrentDigit = digits[nToggleIndex];
auto minGreaterThanIter = nToggleDigits.upper_bound(nCurrentDigit);
assert( minGreaterThanIter != end(nToggleDigits) );
assert( *minGreaterThanIter > nCurrentDigit );
// Replace the current digit and remove from the toggle digit set
digits[nToggleIndex] = *minGreaterThanIter;
nToggleDigits.erase(minGreaterThanIter);
// For the remaining digits, just choose the min
for( int i = nToggleIndex + 1; i < nDigitCount; ++i )
{
assert( !nToggleDigits.empty() );
auto minDigitIter = begin(nToggleDigits);
digits[i] = *minDigitIter;
nToggleDigits.erase(minDigitIter);
}
// Build the integer back up
nNextHighestValue = 0;
for( int i = nDigitCount -1, nPow10 = 1; i >= 0; --i, nPow10 *= 10 )
{
nNextHighestValue += digits[i] * nPow10;
}
}
return nNextHighestValue;
}
That ought to do it:
unsigned next_largest(unsigned x)
{
std::vector<unsigned short> l;
unsigned p;
do l.push_back(x % 10); while (x/=10);
for (p=0; p+1!=l.size() && l[p]<l[p+1]; ++p);
std::sort(&l[0], &l[p+1]);
std::reverse(&l[0], &l[p+1]);
std::swap(l[p+1], l[p]);
for (unsigned i=l.size(); i-->0; x*=10, x+=l[i]);
return x;
}
Oops.. I made a mistake!
You can fix it with (at most) one line extra... I'll leave that as an exercise ;)
My solution in python:
def next_higher(number):
stringified_number = list(str(number))
n = len(stringified_number)
j = n - 2
for i in reversed(xrange(n)):
for j in reversed(xrange(i)):
if int(stringified_number[j]) < int(stringified_number[i]):
stringified_number[j], stringified_number[i] = stringified_number[i], stringified_number[j]
return int("".join(stringified_number[:j+1])+ "".join(sorted(stringified_number[j+1:])))
return number
assert(next_higher(25468) == 25486)
assert(next_higher(21765) == 25167)
assert(next_higher(54321) == 54321)
import java.util.Scanner;
public class NextHighestNumberWithSameDigits {
public static void main(final String[] args) {
// TODO Auto-generated method stub
final Scanner sc = new Scanner(System.in);
System.out.println("Enter a number:");
final String digit = sc.next();
final char[] ch = digit.toCharArray();
final int j = digit.length() - 1;
int k = -1;
for (int i = j - 1; i >= 0; i--) {
if (ch[i] < ch[j]) {
final char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
k = i;
break;
}
}
if (k == -1) {
System.out.println(digit);
} else {
for (int i = k + 1; i < j; i++) {
if (ch[i] > ch[j]) {
final char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
}
System.out.println("next biggest digit:" + String.valueOf(ch));
}
}
}
1. We scan the no from the Least significant digit and store it
2. The scan continues unitl we find a digit lesser than the previous digit
3. If the order is in ascending from least significant digit to the most then return the same number
4. Else the found digit is swapped with the least significant digit and the rest digits are sorted in ascending order and the final number is made
#include<iostream>
#include<math.h>
//#include<algorithm>
using namespace std;
int get_length(int n)
{
int temp=0;
while(n)
{
n=n/10;
temp++;
}
cout<<"in get_length ="<<temp<<endl;
return temp;
}
void sortRest(int arr[],int i)
{
int j,k,temp;
for(j=0;j<=i-1;j++)
{
for(k=j+1;k<=i;k++)
{
if(arr[j]>arr[k])
{
temp=arr[k];
arr[k]=arr[j];
arr[j]=temp;
}
}
}
cout<<"after sorting\n";
for(j=0;j<=i;j++)
cout<<arr[j];
cout<<endl;
}
double swap(int arr[], int i, double n)
{
int j=i;
//int temp = arr[0];
//arr[0] = arr[i];
//arr[i]= temp;
cout<<"0,i= "<<arr[0]<<arr[i]<<endl;
sortRest(arr+1, i-1);
cout<<"0,i= "<<arr[0]<<arr[i]<<endl;
while(j>=0)
{ cout<<"in swap n="<<n<<" i="<<i<<endl;
n=n*10+arr[i-j];
j--;
}
return n;
}
int main()
{
int n,num,len,i=0,ans=-1;
cout<<"enter n\n";
cin>>n;num=n;
len=get_length(n);
int arr[len];
while(n)
{
arr[i]=n%10;cout<<"arr["<<i<<"]="<<arr[i]<<endl;
n=n/10;cout<<"n="<<n<<endl;
if(i!=0)
{
if(arr[i]<arr[i-1])
{
ans=swap(arr, i, n);
break;
}
}
i++;
}
if(ans!=-1)
cout<<ans<<endl;
else
cout<<num<<endl;
return ans;
}
Hey everyone. My solution is the same as the majority of you. Here is my implementation in C++, using priority_queue class in STL. Note that, we should push (-1 * value) in the pqueue, because we want to have a min-heap but the priority_queue class implements a max-heap.
#include <iostream>
#include <queue>
#include <string>
using namespace std;
string findnexthighest(string ipt)
{
priority_queue <char> pq;
int swplace = -1;
for (int i = ipt.size() - 1; i > 0; i--)
{
pq.push(-1 * ipt[i]);
if (ipt[i] > ipt[i - 1])
{
swplace = i - 1;
break;
}
}
if (swplace < 0)
return ipt;
pq.push(-1 * ipt[swplace]);
int curplace = swplace + 1;
int cur;
while (true)
{
cur = -1 * pq.top();
pq.pop();
if (cur>ipt[swplace])
{
ipt[swplace] = cur;
break;
}
ipt[curplace++] = cur;
}
while (!pq.empty())
{
cur = -1 * pq.top();
pq.pop();
ipt[curplace++] = cur;
}
return ipt;
}
The running time of the algorithm is proportional to running time of the sorting algorithm used. Note that we have only digits here, so we can use counting sort to have a linear running time.
public static ArrayList<Integer> convertToList(int a) {
ArrayList<Integer> l = new ArrayList();
int num = a;
while (num > 0) {
l.add(0, num % 10);
num /= 10;
}
return l;
}
public static int convertToInt(ArrayList<Integer> num) {
int a = 0;
int unit = 1;
for (int i = num.size(); i > 0; i--) {
a += num.get(i - 1) * unit;
unit *= 10;
}
return a;
}
public static int findNextMax(int a) {
ArrayList<Integer> num = convertToList(a);
boolean found = false;
for (int j = num.size(); j > 0; j--) {
int last = num.get(j - 1);
for (int i = j; i > 0; i--) {
if (last > num.get(i - 1)) {
num.add(i - 1, last);
num.remove(j );
found = true;
break;
}
}
if(found){break;}
}
return convertToInt(num);
}
package com.test.util;
public class NextHigherNumber {
static int numArr[];
public static void main(String[] arg)
{
int n=123456789;
int num=n;
int numLen=0;
while(n!=0)
{
n=n/10;
numLen++;
}
numArr=new int[numLen];
n=num;
for(int i=numLen-1;i>=0;i--)
{
numArr[i]=n%10;
n=n/10;
}
for(int i : numArr)
System.out.println("i : "+i);
outer : for(int i=numLen-2;i>=0;i--)
{
inner : for(int j=i+1;j<numLen;j++)
{
if(numArr[i]>=numArr[j])
{
System.out.println("1st cond>>>>>i : "+i+" j : "+j+" numArr[i]="+numArr[i]+" numArr[j]="+numArr[j]);
continue inner;
}
else
{
System.out.println("2nd cond>>>>>i : "+i+" j : "+j+" numArr[i]="+numArr[i]+" numArr[j]="+numArr[j]);
int temp=numArr[numLen-1];
numArr[numLen-1]=numArr[i];
numArr[i]=temp;
System.out.println("Swapping>>>>>i : "+i+" numLen-1 : "+(numLen-1)+" numArr[i]="+numArr[i]+" numArr[numLen-1]="+numArr[numLen-1]);
sort(i+1,numLen-1);
break outer;
}
}
}
int newNum=0;
for(int i=numLen-1;i>=0;i--)
{
newNum=newNum+(int) (Math.pow(10, i)*numArr[numLen-1-i]);
}
System.out.println("New Number : "+newNum);
}
public static void sort(int frmIndex,int toIndex)
{
for(int i=frmIndex;i<=toIndex;i++)
System.out.println(i+" Before : "+numArr[i]);
for(int i=frmIndex;i<=toIndex;i++)
{
for(int j=i+1;j<=toIndex;j++)
{
if(numArr[i]>numArr[j])
{
int temp=numArr[i];
numArr[i]=numArr[j];
numArr[j]=temp;
}
}
}
for(int i=0;i<=toIndex;i++)
System.out.println(i+" After : "+numArr[i]);
}
}
def next_higher(a):
a = [int(i) for i in str(a)]
length = len(a)
index = -1
for i in range(length-1, -1, -1):
if a[i] < a[length-1]:
index = i
break
b = a[0:index]
b.append(a[length-1])
c=a[index:length-1]
c.sort()
b.extend(c)
return reduce(lambda a, b: a*10+b, b)
print next_higher(25468), next_higher(21765), next_higher(54321)
/*
* find the next higher number with the same digits
*/
public static int findNextHigerNum(int num){
int[] arr = num2arr(num);
if(arr.length<=1) return num;
if(num<0) return -1 * findNextLower(arr);
return findNextHiger(arr);
}
private static int[] num2arr(int num){
if(num<0) num *= -1;
int count = 0;
int temp = num;
while(temp>0){
temp /= 10;
count++;
}
//use an array to store the num digit by digit
int[] arr = new int[count];
for(int i=0; i<count; i++){
arr[i] = num%10;
num /= 10;
}
return arr;
}
private static int findNextHiger(int[] arr){
int i = 0, j = 0;
while(arr[i]<=arr[i+1]&&i<arr.length-1){
i++;
if(i==arr.length-1) return arr2num(arr);//meaning this number is the largest possible
}
int value = arr[i+1];
while(arr[j]<=value) j++;
swap(arr, i+1, j);
//now place the the remaining part in descending order, this just need a reverse operation
reverse(arr, 0, i);
return arr2num(arr);
}
private static int findNextLower(int[] arr){
int i = 0, j = 0;
while(arr[i]>=arr[i+1]&&i<arr.length-1){
i++;
if(i==arr.length-1) return arr2num(arr);
}
int value = arr[i+1];
while(arr[j]>=value) j++;
swap(arr, i+1, j);
reverse(arr, 0, i);
return arr2num(arr);
}
private static int arr2num(int[] arr){
int poly = 1;
int value = 0;
for(int i=0; i<arr.length; i++){
value += arr[i] * poly;
poly *= 10;
}
return value;
}
private static void reverse(int[] arr, int start, int end){
while(start<end){
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
c++ solution
#include<bits/stdc++.h>
using namespace std;
int main()
{ int i,j,l,hash[10];
char s[1000001],max;//using string to store number.. no precision issues atleast for a 1000000 digits!!!
scanf("%s",s);
for(i=0;i<10;i++)
hash[i]=0;//initially count of 0..9 digits is 0 in the number
l=strlen(s);
i=l-1;
max='0';
while(i>=0)//from right to left until we find a smaller digit than present max digit found.
{
hash[s[i]-48]++;//add digit to hash
if(s[i]>max)//update max if greater digit found
max=s[i];
else if(s[i]<max)//end loop if smaller digit found
break;
i--;
}
if(i<0)//if number has digits in non increasing order from left to right i.e.no greater no. possible
{
puts(s);
return 0;
}
//i currently holds the position of leftmost digit to be changed
j=s[i]-48+1;
while(hash[j]==0)
j++;
s[i]=48+j;//use digit which is just greater than digit at ith position
hash[j]--;
i++;
j=0;
for(;i<l;i++)//update all digits to the right of the previous digit
{
while(hash[j]==0)
j++;
s[i]=48+j;
hash[j]--;
}
puts(s);
return 0;
}
#include<stdio.h>
void sort(int *number, int size, int last);
void leastBiggerNumberWithSameDigits(int *number, int size);
void print(int *number, int size);
int main(void)
{
int number[] = {2, 1, 7, 6, 5};
print(number, 5);
leastBiggerNumberWithSameDigits(number, 5);
print(number, 5);
return 0;
}
void sort(int *number, int size, int last)
{
for(int i = last + 1; i < size - 1; i++)
{
for(int j = i + 1; j < size; j++)
{
if(number[i] > number[j])
{
int temp = number[i];
number[i] = number[j];
number[j] = temp;
}
}
}
}
void leastBiggerNumberWithSameDigits(int *number, int size)
{
// first make the smallest swap
int last;
for(last = size - 2; last >= 0; last--)
{
if(number[last] < number[last + 1])
{
//printf("-%d-", number[last]);
break;
}
}
if(last == 0)
{
return;
}
bool swapped = false;
for(int i = last + 1; i < size; i++)
{
if(number[i] < number[last])
{
int temp = number[i-1];
number[i-1] = number[last];
number[last] = temp;
sort(number, size, last);
swapped = true;
break;
}
}
if(!swapped)
{
int temp = number[size - 1];
number[size - 1] = number[last];
number[last] = temp;
sort(number, size, last);
}
}
void print(int *number, int size)
{
for(int i = 0; i < size; i++)
{
printf("%d, ", number[i]);
}
printf("\n");
}
similar to leetcode nextPermutation
class Solution {
public:
void nextPermutation(vector<int> &num) {
int i = num.size()-1;
int j = 0;
while (i>0 && num[i-1] >= num[i]) {
i--;
}
if (i==0)
sort(num.begin(), num.end()); // 321 to 123
else {
j = i+1;
while (num[j] > num[i-1] && j<num.size()) {
j++;
}
swap(num[j-1], num[i-1]);
sort(num.begin()+i,num.end());
}
}
};
public class NextHigh {
public static int makeNumber(int a[])
{
int ans=0;
for(int i=a.length-1;i>=0;i--)
{
ans=a[i]+ans*10;
}
return ans;
}
public static int func(int b[])
{
int a[]=new int[b.length];
a=Arrays.copyOf(b, b.length);
int n=a.length,ans=makeNumber(b);
int i,t;
boolean found=false;
int f,s;
for(i=0;i<n-1;i++)
{
f=makeNumber(a);
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
s=makeNumber(a);
if(s>f)
{
found=true;
break;
}
else
a=Arrays.copyOf(b, b.length);
}
if(found)
ans=makeNumber(a);
return ans;
}
public static void main(String args[])
{
int n=11;
int t=n;
int len=0;
while(t>0)
{
len++;
t=t/10;
}
int a[]=new int[len];
t=n;
for(int i=0;i<len;i++)
{
a[i]=t%10;
t=t/10;
}
System.out.println(makeNumber(a));
System.out.println(func(a));
}
}
// Working c code
/*
* File: main.c
* Author: Sandeep Srivastava
*
* Created on May 11, 2014, 11:30 AM
*/
#include <stdio.h>
#include <stdlib.h>
void sortArray(int arr[],int s,int e)
{
int i,j;
for (i = s; i < e; ++i)
{
for (j = i + 1; j < e; ++j)
{
if (arr[i] > arr[j])
{
int a = arr[i];
arr[i] = arr[j];
arr[j] = a;
}
}
}
}
void swap(int arr[],int i,int pos)
{
int temp=arr[i];
arr[i]=arr[pos];
arr[pos]=temp;
}
int findMin(int arr[],int s,int e)
{
int pos=s;
while(s<e)
{
if(arr[pos]>arr[s])
pos=s;
s++;
}
return pos;
}
int findDigit(int n)
{
int count=0;
while(n)
{
n=n/10;
count++;
}
return count;
}
int findNext(int n,int d)
{
int tn=n; // storing n in tn
int arr[d]; // array of length equal to number of digit
int i;
for(i=d-1;i>=0;i--)
{
arr[i]=n%10; // storing each digit of number in array
n=n/10;
}
int temp= arr[d-1];
i=d-1;
while(temp<=arr[i] && i>=0)
{
temp=arr[i];
i--;
}
if(i==-1)
return tn;
else
{
int pos= findMin(arr,i+1,d);
swap(arr,i,pos);
sortArray(arr,i+1,d);
for(i=0;i<d;i++)
{
n=n*10+arr[i];
}
}
return n ;
}
int main() {
int digit =findDigit(21765); // find the number of digit
printf("input is: %d and output is: %d \n",21765, findNext(21765,digit));
digit =findDigit(25468);
printf("input is: %d and output is: %d \n",25468, findNext(25468,digit));
digit =findDigit(54321);
printf("input is: %d and output is: %d \n",54321, findNext(54321,digit));
return 0;
}
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> digits;
if (n <= 0) return -1;
else{
while(n){
digits.push_back(n%10);
n/=10;
}
reverse(digits.begin(), digits.end());
if (digits.size() == 1) return -1;
int i;
for (i = digits.size()-2; i >= 0; i--){
if (digits[i] < digits[i+1]){
int j = i+1;
while(j < digits.size() && digits[j] > digits[i]) j++;
j--;
swap(digits[i], digits[j]);
sort(digits.begin()+i+1, digits.end());
break;
}
}
if (i == -1) return -1;
else{
for (int i = 0; i < digits.size(); i++)
cout << digits[i];
cout << endl;
}
}
}
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> digits;
if (n <= 0) return -1;
else{
while(n){
digits.push_back(n%10);
n/=10;
}
reverse(digits.begin(), digits.end());
if (digits.size() == 1) return -1;
int i;
for (i = digits.size()-2; i >= 0; i--){
if (digits[i] < digits[i+1]){
int j = i+1;
while(j < digits.size() && digits[j] > digits[i]) j++;
j--;
swap(digits[i], digits[j]);
sort(digits.begin()+i+1, digits.end());
break;
}
}
if (i == -1) return -1;
else{
for (int i = 0; i < digits.size(); i++)
cout << digits[i];
cout << endl;
}
}
}
import java.util.*;
public class Main {
public static void main(String args[]){
int num = 18715;
String nums = String.valueOf(num);
int min = Integer.parseInt(nums.substring(nums.length()-1));
int minIndex = nums.length()-1;
int i = nums.length()-2;
int a = Integer.parseInt(nums.substring(i+1,i+2));
int b= Integer.parseInt(nums.substring(i,i+1));
while(a<b){
System.out.println(i);
i--;
if(i==-1){
System.out.println("No min next Possible");
break;
}
a = Integer.parseInt(nums.substring(i+1,i+2));
b= Integer.parseInt(nums.substring(i,i+1));
}
int newnum=0;
if(i!=-1){
for(int j=0;j<nums.length()-1;j++){
if(j==i){
newnum=newnum*10 + Integer.parseInt(nums.substring(nums.length()-1, nums.length()));
}
else{
newnum=newnum*10 + Integer.parseInt(nums.substring(j,j+1));
}
}
newnum=newnum*10 + Integer.parseInt(nums.substring(i,i+1));
System.out.println(newnum);
}
}
}
Guys even if he is publicizing his blog, atleast the question he posts are good. When the question quality is down then we can criticize him.
No, don't encourage people to make this their own advertising space. Broken windows theory (see wikipedia) applies here. Plus, the questions are not necessarily first-hand interview questions, even though they might be interesting/good. I can give you plenty of interesting questions which will only lower your chances of getting a job.
He can post to the forum all he wants. Is it really hard for folks to understand that? GAWD. The IQ level on this site is sickening.
- Get digits of N in positional order
- Find first digit M that is not in ascending order (searching from right to left)
- If all digits are in ascending order from right to left, then return N
- Find the smallest digit P that is to the right of M and is also larger than M
- Swap positions of M and P
- Sort digits after original position of M in ascending order from left to right
- Build and return from digits
- danyluis April 05, 2014public int NextLargest(int n) { byte[] digits = new byte[10]; int length = 0; while (n > 0) { digits[length++] = (byte)(n % 10); n /= 10; } Array.Reverse(digits, 0, length); int swapPos = -1; for (int i = length - 2; (i >= 0) && (swapPos == -1); i--) if (digits[i] < digits[i + 1]) swapPos = i; if (swapPos == -1) return n; int swapPos2 = -1; int min = int.MaxValue; for (int i = swapPos + 1; i < length; i++) { if ((digits[i] > digits[swapPos]) && (digits[i] < min)) { min = digits[i]; swapPos2 = i; } } byte bTemp = digits[swapPos]; digits[swapPos] = digits[swapPos2]; digits[swapPos2] = bTemp; Array.Sort(digits, swapPos + 1, length - swapPos - 1); for (int i = 0; i < length; i++) n = n * 10 + digits[i]; return n; }