给定一个数字，find与原始数字具有完全相同的一组数字的下一个更高的数字

我只是轰炸了面试，在面试问题上几乎没有什么进展。 任何人都可以让我知道如何做到这一点？ 我尝试在网上search，但找不到任何东西：

给定一个数字，find与原始数字具有完全相同的一组数字的下一个更高的数字。 例如：给出38276回报38627

我想从find第一个数字（从右边）的索引开始，这个索引小于那个数字。 然后，我将旋转子集中的最后一个数字，使得它是由相同数字组成的下一个最大数字，但是卡住了。

面试官还build议一次换一个数字，但是我不知道algorithm，只是盯着屏幕20-30分钟。 不用说，我想我将不得不继续寻找工作。

编辑：为了什么值得，我被邀请参加下一轮采访

Answer 1

您可以在O(n) （其中n是数字的位数）中这样做：

从右边开始，您会find第一个数字对，这样左边的数字就比右边的数字小。 我们用“digit-x”来指左边的数字。 在digit-x的右侧find大于digit-x的最小数字，并将其放在digit-x的左侧。 最后，按升序对剩下的数字进行sorting – 因为它们已经以降序排列，所有你需要做的就是反转它们（除了digit-x，可以放在O(n)的正确位置） 。

一个例子会使这个更清楚：

 123456784987654321
从一个数字开始

 123456784 987654321
          ^左边数字小于右边的第一位  
         数字“x”是4

 123456784 987654321
               ^find右边大于4的最小数字

 123456785 4 98764321
         ^把它放在4的左边

 123456785 4 12346789
 123456785123446789
          ^排列在5右边的数字。因为除了所有这些 
          '4'已经是降序了，我们所要做的就是 
         颠倒他们的顺序，find'4'的正确位置，

---

正确性certificate：

我们用大写字母来定义数字string和小写字母。 语法AB意思是“串A和串B ” 。 <是词典sorting，当数字串长度相等时，与整数sorting相同。

我们的原始数字N的forms是AxB ，其中x是一个数字， B是降序排列的。
我们的algorithmfind的数是AyC ，其中AyC是最小的数字> x （它必须存在，因为x被select的方式，参见上面） ， C按升序sorting。

假设有一些数字（使用相同的数字） N' ，使得AxB < N' < AyC 。 N'必须以A开始，否则不能在它们之间，所以我们可以用AzD的forms来写。 现在我们的不等式是AxB < AzD < AyC ，它等于xB < zD < yC ，其中所有三个数字string包含相同的数字。

为了做到这一点，我们必须有x <= z <= y 。 由于y是最小的数字> x ，所以z不能在它们之间，所以z = x或者z = y 。 说z = x 。 那么我们的不等式是xB < xD < yC ，这意味着B < D ，其中B和D都有相同的数字。 然而，B是降序sorting的，所以没有string的那些数字大于它。 因此我们不能有B < D 。 按照相同的步骤，我们看到如果z = y ，我们不能有D < C 。

因此N'不能存在，这意味着我们的algorithm正确地find下一个最大的数字。

Answer 2

一个几乎相同的问题出现在代码堵塞问题，并有一个解决scheme在这里：

http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1

以下是使用示例的方法摘要：

 34722641 

A.将数字序列分成两部分，以便在保持降序的同时尽可能长的部分是正确的部分：

 34722 641 

（如果整个号码是递减的，没有更大的号码可以不添加数字。）

B.1。 select第一个序列的最后一个数字：

 3472(2) 641 

B.2。 find第二个序列中比它大的最小数字：

 3472(2) 6(4)1 

B.3。 交换他们：

 3472(2) 6(4)1 -> 3472(4) 6(2)1 -> 34724 621 

C.将第二个序列按递增顺序sorting：

 34724 126 

D.完成！

 34724126 

Answer 3

这是Python中的一个紧凑的（但部分蛮力）解决scheme

 def findnext(ii): return min(v for v in (int("".join(x)) for x in itertools.permutations(str(ii))) if v>ii) 

在C ++中，你可以像这样做排列： https : //stackoverflow.com/a/9243091/1149664 （它是itertools中的algorithm）

以下是Weeble和BlueRaja描述的最佳答案的实现 （其他答案）。 我怀疑有什么更好的。

 def findnext(ii): iis=map(int,str(ii)) for i in reversed(range(len(iis))): if i == 0: return ii if iis[i] > iis[i-1] : break left,right=iis[:i],iis[i:] for k in reversed(range(len(right))): if right[k]>left[-1]: right[k],left[-1]=left[-1],right[k] break return int("".join(map(str,(left+sorted(right))))) 

Answer 4

至less，下面是几个基于string的powershell解决scheme示例，你应该已经能够想到了：

在38276sorting的数字列表是23678

38627sorting的数字列表是23678

蛮力增量，sorting和比较

沿着蛮力的解决scheme将转换为一个string和蛮力使用这些数字所有可能的数字。

在它们中创buildints，将它们放在一个列表中并对其进行sorting，获得目标条目之后的下一个条目。

如果你花了30分钟的时间，并没有至less拿出一个暴力的方法，我也不会雇用你。

在商业世界中，一个不雅，缓慢，笨重的解决scheme，总是比没有解决scheme更有价值，事实上，这些解决scheme几乎可以描述所有的商业软件，不雅，慢，笨重。

Answer 5

 function foo(num){ sortOld = num.toString().split("").sort().join(''); do{ num++; sortNew = num.toString().split("").sort().join(''); }while(sortNew!==sortOld); return num; } 

Answer 6

你的想法

我想从find第一个数字（从右边）的索引开始，这个索引小于个位数。 然后，我将旋转子集中的最后一个数字，使得它是由相同数字组成的下一个最大数字，但是卡住了。

实际上是相当不错的。 您不仅要考虑最后一位数字，而且还要考虑比当前考虑的重要性要小的所有数字。 因为在此之前，我们有一个单调的数字序列，这是最右边的数字小于其右边的邻居。 看待

 1234675 ^ 

下一个更大的数字是相同的数字是

 1234756 

find的数字被交换为最后一位数字 – 所考虑数字中最小的一位数字，其余数字按递增顺序排列。

Answer 7

我相当肯定你的面试官正试图轻轻推动你这样的事情：

 local number = 564321; function split(str) local t = {}; for i = 1, string.len(str) do table.insert(t, str.sub(str,i,i)); end return t; end local res = number; local i = 1; while number >= res do local t = split(tostring(res)); if i == 1 then i = #t; end t[i], t[i-1] = t[i-1], t[i]; i = i - 1; res = tonumber(table.concat(t)); end print(res); 

不一定是最高效或优雅的解决scheme，但它解决了在两个周期中提供的示例，并像他build议的那样每次交换一位数字。

Answer 8

这是非常有趣的问题。

这是我的Java版本。 在我查看其他贡献者的意见之前，花了大约3个小时弄清楚了这个模式以完成代码。 很高兴看到我的想法与其他人完全一样。

O（n）解决scheme。 老实说，如果时间只有15分钟，我会在面试失败，需要在白板上完成代码。

以下是我的解决scheme的一些有趣的点：

• 避免任何分类。
• 避免string操作完全
• 实现O（logN）空间复杂度

我在我的代码中放置了详细注释，在每一步中都放了大O。

  public int findNextBiggestNumber(int input ) { //take 1358642 as input for example. //Step 1: split the whole number to a list for individual digital 1358642->[2,4,6,8,5,3,1] // this step is O(n) int digitalLevel=input; List<Integer> orgNumbersList=new ArrayList<Integer>() ; do { Integer nInt = new Integer(digitalLevel % 10); orgNumbersList.add(nInt); digitalLevel=(int) (digitalLevel/10 ) ; } while( digitalLevel >0) ; int len= orgNumbersList.size(); int [] orgNumbers=new int[len] ; for(int i=0;i<len;i++){ orgNumbers[i ] = orgNumbersList.get(i).intValue(); } //step 2 find the first digital less than the digital right to it // this step is O(n) int firstLessPointer=1; while(firstLessPointer<len&&(orgNumbers[firstLessPointer]>orgNumbers[ firstLessPointer-1 ])){ firstLessPointer++; } if(firstLessPointer==len-1&&orgNumbers[len-1]>=orgNumbers[len-2]){ //all number is in sorted order like 4321, no answer for it, return original return input; } //when step 2 step finished, firstLessPointer pointing to number 5 //step 3 fristLessPointer found, need to find to first number less than it from low digital in the number //This step is O(n) int justBiggerPointer= 0 ; while(justBiggerPointer<firstLessPointer&& orgNumbers[justBiggerPointer]<orgNumbers[firstLessPointer]){ justBiggerPointer++; } //when step 3 finished, justBiggerPointer pointing to 6 //step 4 swap the elements of justBiggerPointer and firstLessPointer . // This is O(1) operation for swap int tmp= orgNumbers[firstLessPointer] ; orgNumbers[firstLessPointer]= orgNumbers[justBiggerPointer] ; orgNumbers[justBiggerPointer]=tmp ; // when step 4 finished, the list looks like [2,4,5,8,6,3,1] the digital in the list before // firstLessPointer is already sorted in our previous operation // we can return result from this list but in a differrent way int result=0; int i=0; int lowPointer=firstLessPointer; //the following pick number from list from the position just before firstLessPointer, here is 8 -> 5 -> 4 -> 2 //This Operation is O(n) while(lowPointer>0) { result+= orgNumbers[--lowPointer]* Math.pow(10,i); i++; } //the following pick number from list from position firstLessPointer //This Operation is O(n) while(firstLessPointer<len) { result+= orgNumbers[firstLessPointer++ ]* Math.pow(10,i); i++; } return result; } 

这里是运行在Intellj的结果：

 959879532-->959892357 1358642-->1362458 1234567-->1234576 77654321-->77654321 38276-->38627 47-->74 

Answer 9

取一个数字并将其分成数字。 所以如果我们有一个5位数字，我们有5个数字：abcde

现在交换d和e，并与原来的数字比较，如果它更大，你有你的答案。

如果不大，则交换e和c。 现在比较一下，如果再小一些的话就交换d和e（注意recursion），取最小值。

继续下去，直到你find一个更大的数字。 recursion它应该算作约9行的计划，或20的C＃。

Answer 10

@ BlueRajaalgorithm的一个JavaScript实现。

 var Bar = function(num){ num = num.toString(); var max = 0; for(var i=num.length-2; i>0; i--){ var numArray = num.substr(i).split(""); max = Math.max.apply(Math,numArray); if(numArray[0]<max){ numArray.sort(function(a,b){return ab;}); numArray.splice(-1); numArray = numArray.join(""); return Number(num.substr(0,i)+max+numArray); } } return -1; }; 

Answer 11

我只用两个数字来testing。 他们工作。 作为IT经理，直到去年12月退休8年，我关心三件事情：1）准确性：总是有效的。 2）速度：必须被用户接受。 3）清晰：我可能不像你一样聪明，但我付钱给你。 确保你用英语解释你在做什么。

奥马，祝你好运。

 Sub Main() Dim Base(0 To 9) As Long Dim Test(0 To 9) As Long Dim i As Long Dim j As Long Dim k As Long Dim ctr As Long Const x As Long = 776914648 Dim y As Long Dim z As Long Dim flag As Boolean ' Store the digit count for the original number in the Base vector. For i = 0 To 9 ctr = 0 For j = 1 To Len(CStr(x)) If Mid$(CStr(x), j, 1) = i Then ctr = ctr + 1 Next j Base(i) = ctr Next i ' Start comparing from the next highest number. y = x + 1 Do ' Store the digit count for the each new number in the Test vector. flag = False For i = 0 To 9 ctr = 0 For j = 1 To Len(CStr(y)) If Mid$(CStr(y), j, 1) = i Then ctr = ctr + 1 Next j Test(i) = ctr Next i ' Compare the digit counts. For k = 0 To 9 If Test(k) <> Base(k) Then flag = True Next k ' If no match, INC and repeat. If flag = True Then y = y + 1 Erase Test() Else z = y ' Match. End If Loop Until z > 0 MsgBox (z), , "Solution" End Sub 

Answer 12

如果你用C ++编程，你可以使用next_permutation ：

 #include <algorithm> #include <string> #include <iostream> int main(int argc, char **argv) { using namespace std; string x; while (cin >> x) { cout << x << " -> "; next_permutation(x.begin(),x.end()); cout << x << "\n"; } return 0; } 

Answer 13

在回答这个问题时，我对蛮力algorithm一无所知，所以我从另一个angular度来看待它。 我决定从number_given + 1到可用的最大数字（999为3位数字，9999为4位数字等等）search可能的解决scheme的整个范围，这个数字可能被重新排列。 我这样做就像find一个带有单词的回文，把每个解决scheme的数字进行sorting，并将其与作为参数给出的sorting数字进行比较。 然后，我简单地返回解决scheme数组中的第一个解决scheme，因为这将是下一个可能的值。

这是我在Ruby中的代码：

def PermutationStep（num）

 a = [] (num.to_s.length).times { a.push("9") } max_num = a.join('').to_i verify = num.to_s.split('').sort matches = ((num+1)..max_num).select {|n| n.to_s.split('').sort == verify } if matches.length < 1 return -1 else matches[0] end 

结束

Answer 14

一个解决scheme（Java）可以是以下（我相信这里的朋友可以find更好的）：
开始交换数字从string的末尾，直到你得到一个更高的数字。
也就是说，首先开始向下移动数字，然后是下一个较高的数字，直到达到更高。
然后再分类。 在你的例子中，你会得到：

 38276 --> 38267 (smaller) --> 38627 Found it ^ ^ ^ public static int nextDigit(int number){ String num = String.valueOf(number); int stop = 0; char [] chars = null; outer: for(int i = num.length() - 1; i > 0; i--){ chars = num.toCharArray(); for(int j = i; j > 0; j--){ char temp = chars[j]; chars[j] = chars[j - 1]; chars[j - 1] = temp; if(Integer.valueOf(new String(chars)) > number){ stop = j; break outer; } } } Arrays.sort(chars, stop, chars.length); return Integer.valueOf(new String(chars)); } 

Answer 15

有关如何做到这一点的一个很好的写法，请参阅Knuth的“ 计算机编程的艺术：生成所有排列 ”（.ps.gz）中的“ algorithmL ”。

Answer 16

这是我的代码，它是这个例子的修改版本

图书馆：

 class NumPermExample { // print N! permutation of the characters of the string s (in order) public static void perm1(String s, ArrayList<String> perm) { perm1("", s); } private static void perm1(String prefix, String s, ArrayList<String> perm) { int N = s.length(); if (N == 0) { System.out.println(prefix); perm.add(prefix); } else { for (int i = 0; i < N; i++) perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N)); } } // print N! permutation of the elements of array a (not in order) public static void perm2(String s, ArrayList<String> perm) { int N = s.length(); char[] a = new char[N]; for (int i = 0; i < N; i++) a[i] = s.charAt(i); perm2(a, N); } private static void perm2(char[] a, int n, ArrayList<String> perm) { if (n == 1) { System.out.println(a); perm.add(new String(a)); return; } for (int i = 0; i < n; i++) { swap(a, i, n-1); perm2(a, n-1); swap(a, i, n-1); } } // swap the characters at indices i and j private static void swap(char[] a, int i, int j) { char c; c = a[i]; a[i] = a[j]; a[j] = c; } // next higher permutation public static int nextPermutation (int number) { ArrayList<String> perm = new ArrayList<String>(); String cur = ""+number; int nextPerm = 0; perm1(cur, perm); for (String s : perm) { if (Integer.parseInt(s) > number && (nextPerm == 0 || Integer.parseInt(s) < nextPerm)) { nextPerm = Integer.parseInt(s); } } return nextPerm; } } 

testing：

 public static void main(String[] args) { int a = 38276; int b = NumPermExample.nextPermutation(a); System.out.println("a: "+a+", b: "+b); } 

Answer 17

将9添加到给定的n位数字。 然后检查它是否在限制内（第一（n + 1）位数）。 如果是，则检查新号码中的数字是否与原始号码中的数字相同。 重复加9，直到两个条件都成立。 当数字超出限制时停止algorithm。

我不能拿出这个方法的矛盾的testing案例。

Answer 18

 #include<stdio.h> #include<cstring> #include<iostream> #include<string.h> #include<sstream> #include<iostream> using namespace std; int compare (const void * a, const void * b) { return *(char*)a-*(char*)b; } 

/ ———————————————– /

 int main() { char number[200],temp; cout<<"please enter your number?"<<endl; gets(number); int n=strlen(number),length; length=n; while(--n>0) { if(number[n-1]<number[n]) { for(int i=length-1;i>=n;i--) { if(number[i]>number[n-1]) { temp=number[i]; number[i]=number[n-1]; number[n-1]=temp; break; } } qsort(number+n,length-n,sizeof(char),compare); puts(number); return 0; } } cout<<"sorry itz the greatest one :)"<<endl; } 

Answer 19

只是另一个解决scheme使用Python：

 def PermutationStep(num): if sorted(list(str(num)), reverse=True) == list(str(num)): return -1 ls = list(str(num)) n = 0 inx = 0 for ind, i in enumerate(ls[::-1]): if i < n: n = i inx = -(ind + 1) break n = i ls[inx], ls[inx + 1] = ls[inx + 1], ls[inx] nl = ls[inx::-1][::-1] ln = sorted(ls[inx+1:]) return ''.join(nl) + ''.join(ln) print PermutationStep(23514) 

输出：

 23541 

Answer 20

 public static void findNext(long number){ /* convert long to string builder */ StringBuilder s = new StringBuilder(); s.append(number); int N = s.length(); int index=-1,pivot=-1; /* from tens position find the number (called pivot) less than the number in right */ for(int i=N-2;i>=0;i--){ int a = s.charAt(i)-'0'; int b = s.charAt(i+1)-'0'; if(a<b){ pivot = a; index =i; break; } } /* if no such pivot then no solution */ if(pivot==-1) System.out.println(" No such number ") else{ /* find the minimum highest number to the right higher than the pivot */ int nextHighest=Integer.MAX_VALUE, swapIndex=-1; for(int i=index+1;i<N;i++){ int a = s.charAt(i)-'0'; if(a>pivot && a<nextHighest){ nextHighest = a; swapIndex=i; } } /* swap the pivot and next highest number */ s.replace(index,index+1,""+nextHighest); s.replace(swapIndex,swapIndex+1,""+pivot); /* sort everything to right of pivot and replace the sorted answer to right of pivot */ char [] sort = s.substring(index+1).toCharArray(); Arrays.sort(sort); s.replace(index+1,N,String.copyValueOf(sort)); System.out.println("next highest number is "+s); } } 

Answer 21

下面是生成一个数字的所有排列的代码..但是必须首先使用String.valueOf（整数）将该整数转换为string。

 /** * * Inserts a integer at any index around string. * * @param number * @param position * @param item * @return */ public String insertToNumberStringAtPosition(String number, int position, int item) { String temp = null; if (position >= number.length()) { temp = number + item; } else { temp = number.substring(0, position) + item + number.substring(position, number.length()); } return temp; } /** * To generate permutations of a number. * * @param number * @return */ public List<String> permuteNumber(String number) { List<String> permutations = new ArrayList<String>(); if (number.length() == 1) { permutations.add(number); return permutations; } // else int inserterDig = (int) (number.charAt(0) - '0'); Iterator<String> iterator = permuteNumber(number.substring(1)) .iterator(); while (iterator.hasNext()) { String subPerm = iterator.next(); for (int dig = 0; dig <= subPerm.length(); dig++) { permutations.add(insertToNumberStringAtPosition(subPerm, dig, inserterDig)); } } return permutations; } 

Answer 22

 #include<bits/stdc++.h> using namespace std; int main() { int i,j,k,min,len,diff,z,u=0,f=0,flag=0; char temp[100],a[100]`enter code here`,n; min=9999; //cout<<"Enter the number\n"; cin>>a; len=strlen(a); for(i=0;i<len;i++) { if(a[i]<a[i+1]){flag=1;break;} } if(flag==0){cout<<a<<endl;} else { for(i=len-1;i>=0;i--)if(((int)a[i-1])<((int)a[i]))break; for(k=0;k<i-1;k++)cout<<a[k]; for(j=i;j<len;j++) { if(((int)a[j]-48)-((int)a[i-1]-48)>0) { diff=((int)a[j]-48)-((int)a[i-1]-48); if(diff<min){n=a[j];min=diff;} } } cout<<n; for(z=i-1;z<len;z++) { temp[u]=a[z]; u++; } temp[u]='\0'; sort(temp,temp+strlen(temp)); for(z=0;z<strlen(temp);z++){if(temp[z]==n&&f==0){f=1;continue;}cout<<temp[z];} } return 0; } 

Answer 23

这里是我在ruby中的实现：

 def foo num num = num.to_s.chars.map(&:to_i) return num.join.to_i if num.size < 2 for left in (num.size-2).downto(0) do for right in (num.size-1).downto(left+1) do if num[right]>num[left] num[left],num[right] = num[right],num[left] return (num[0..left] + num[left+1..num.size-1].sort).join.to_i end end end return num.join.to_i end p foo 38276 #will print: 38627 

你可以在这里阅读更多

Answer 24

还有另一个Java实现，可以运行在盒子外面并且完成testing。 这个解决scheme是O（n）空间和时间使用良好的旧dynamic编程。

如果想要暴力，有两种暴力行为：

1. 排列所有的东西，然后select更高：O（n！）

2. 类似于这个实现，但是替代DP，强制执行填充indexToIndexOfNextSmallerLeft映射的步骤将在O（n ^ 2）中运行。

---

 import java.util.Arrays; import java.util.HashMap; import java.util.Map; import org.junit.Test; import static org.junit.Assert.assertEquals; public class NextHigherSameDigits { public long next(final long num) { final char[] chars = String.valueOf(num).toCharArray(); final int[] digits = new int[chars.length]; for (int i = 0; i < chars.length; i++) { digits[i] = Character.getNumericValue(chars[i]); } final Map<Integer, Integer> indexToIndexOfNextSmallerLeft = new HashMap<>(); indexToIndexOfNextSmallerLeft.put(1, digits[1] > digits[0] ? 0 : null); for (int i = 2; i < digits.length; i++) { final int left = digits[i - 1]; final int current = digits[i]; Integer indexOfNextSmallerLeft = null; if (current > left) { indexOfNextSmallerLeft = i - 1; } else { final Integer indexOfnextSmallerLeftOfLeft = indexToIndexOfNextSmallerLeft.get(i - 1); final Integer nextSmallerLeftOfLeft = indexOfnextSmallerLeftOfLeft == null ? null : digits[indexOfnextSmallerLeftOfLeft]; if (nextSmallerLeftOfLeft != null && current > nextSmallerLeftOfLeft) { indexOfNextSmallerLeft = indexOfnextSmallerLeftOfLeft; } else { indexOfNextSmallerLeft = null; } } indexToIndexOfNextSmallerLeft.put(i, indexOfNextSmallerLeft); } Integer maxOfindexOfNextSmallerLeft = null; Integer indexOfMinToSwapWithNextSmallerLeft = null; for (int i = digits.length - 1; i >= 1; i--) { final Integer indexOfNextSmallerLeft = indexToIndexOfNextSmallerLeft.get(i); if (maxOfindexOfNextSmallerLeft == null || (indexOfNextSmallerLeft != null && indexOfNextSmallerLeft > maxOfindexOfNextSmallerLeft)) { maxOfindexOfNextSmallerLeft = indexOfNextSmallerLeft; if (maxOfindexOfNextSmallerLeft != null && (indexOfMinToSwapWithNextSmallerLeft == null || digits[i] < digits[indexOfMinToSwapWithNextSmallerLeft])) { indexOfMinToSwapWithNextSmallerLeft = i; } } } if (maxOfindexOfNextSmallerLeft == null) { return -1; } else { swap(digits, indexOfMinToSwapWithNextSmallerLeft, maxOfindexOfNextSmallerLeft); reverseRemainingOfArray(digits, maxOfindexOfNextSmallerLeft + 1); return backToLong(digits); } } private void reverseRemainingOfArray(final int[] digits, final int startIndex) { final int[] tail = Arrays.copyOfRange(digits, startIndex, digits.length); for (int i = tail.length - 1; i >= 0; i--) { digits[(digits.length - 1) - i] = tail[i]; } } private void swap(final int[] digits, final int currentIndex, final int indexOfNextSmallerLeft) { int temp = digits[currentIndex]; digits[currentIndex] = digits[indexOfNextSmallerLeft]; digits[indexOfNextSmallerLeft] = temp; } private long backToLong(int[] digits) { StringBuilder sb = new StringBuilder(); for (long i : digits) { sb.append(String.valueOf(i)); } return Long.parseLong(sb.toString()); } @Test public void test() { final long input1 = 34722641; final long expected1 = 34724126; final long output1 = new NextHigherSameDigits().next(input1); assertEquals(expected1, output1); final long input2 = 38276; final long expected2 = 38627; final long output2 = new NextHigherSameDigits().next(input2); assertEquals(expected2, output2); final long input3 = 54321; final long expected3 = -1; final long output3 = new NextHigherSameDigits().next(input3); assertEquals(expected3, output3); final long input4 = 123456784987654321L; final long expected4 = 123456785123446789L; final long output4 = new NextHigherSameDigits().next(input4); assertEquals(expected4, output4); final long input5 = 9999; final long expected5 = -1; final long output5 = new NextHigherSameDigits().next(input5); assertEquals(expected5, output5); } } 

Answer 25

我们需要find最右边的位0，然后是1，然后将这个最右边的位翻转到1。

例如让我们说我们的input是487，这是二进制的111100111。

我们翻转最右边的0，有1个跟随它

所以我们得到111101111

但是现在我们有一个1和一个更less的0，所以我们将翻转位右边的1的数量减less1，并将0的数量增加1，产生

111101011 – binary 491

 int getNextNumber(int input) { int flipPosition=0; int trailingZeros=0; int trailingOnes=0; int copy = input; //count trailing zeros while(copy != 0 && (copy&1) == 0 ) { ++trailingZeros; //test next bit copy = copy >> 1; } //count trailing ones while(copy != 0 && (copy&1) == 1 ) { ++trailingOnes; //test next bit copy = copy >> 1; } //if we have no 1's (ie input is 0) we cannot form another pattern with //the same number of 1's which will increment the input, or if we have leading consecutive //ones followed by consecutive 0's up to the maximum bit size of a int //we cannot increase the input whilst preserving the original no of 0's and //1's in the bit pattern if(trailingZeros + trailingOnes == 0 || trailingZeros + trailingOnes == 31) return -1; //flip first 0 followed by a 1 found from the right of the bit pattern flipPosition = trailingZeros + trailingOnes+1; input |= 1<<(trailingZeros+trailingOnes); //clear fields to the right of the flip position int mask = ~0 << (trailingZeros+trailingOnes); input &= mask; //insert a bit pattern to the right of the flip position that will contain //one less 1 to compensate for the bit we switched from 0 to 1 int insert = flipPosition-1; input |= insert; return input; } 

Answer 26

 int t,k,num3,num5; scanf("%d",&t); int num[t]; for(int i=0;i<t;i++){ scanf("%d",&num[i]); } for(int i=0;i<t;i++){ k=(((num[i]-1)/3)+1); if(k<0) printf("-1"); else if(num[i]<3 || num[i]==4 || num[i]==7) printf("-1"); else{ num3=3*(2*num[i] - 5*k); num5=5*(3*k -num[i]); for(int j=0;j<num3;j++) printf("5"); for(int j=0;j<num5;j++) printf("3"); } printf("\n"); } 

Answer 27

Here is the Java Implementation

 public static int nextHigherNumber(int number) { Integer[] array = convertToArray(number); int pivotIndex = pivotMaxIndex(array); int digitInFirstSequence = pivotIndex -1; int lowerDigitIndexInSecondSequence = lowerDigitIndex(array[digitInFirstSequence], array, pivotIndex); swap(array, digitInFirstSequence, lowerDigitIndexInSecondSequence); doRercursiveQuickSort(array, pivotIndex, array.length - 1); return arrayToInteger(array); } public static Integer[] convertToArray(int number) { int i = 0; int length = (int) Math.log10(number); int divisor = (int) Math.pow(10, length); Integer temp[] = new Integer[length + 1]; while (number != 0) { temp[i] = number / divisor; if (i < length) { ++i; } number = number % divisor; if (i != 0) { divisor = divisor / 10; } } return temp; } private static int pivotMaxIndex(Integer[] array) { int index = array.length - 1; while(index > 0) { if (array[index-1] < array[index]) { break; } index--; } return index; } private static int lowerDigitIndex(int number, Integer[] array, int fromIndex) { int lowerMaxIndex = fromIndex; int lowerMax = array[lowerMaxIndex]; while (fromIndex < array.length - 1) { if (array[fromIndex]> number && lowerMax > array[fromIndex]) { lowerMaxIndex = fromIndex; } fromIndex ++; } return lowerMaxIndex; } public static int arrayToInteger(Integer[] array) { int number = 0; for (int i = 0; i < array.length; i++) { number+=array[i] * Math.pow(10, array.length-1-i); } return number; } 

Here is the Unit Tests

 @Test public void nextHigherNumberTest() { assertThat(ArrayUtils.nextHigherNumber(34722641), is(34724126)); assertThat(ArrayUtils.nextHigherNumber(123), is(132)); } 

Answer 28

I know this is very old question but still I didn't find easy code in c#. This might help guys who are attending interviews.

 class Program { static void Main(string[] args) { int inputNumber = 629; int i, currentIndexOfNewArray = 0; int[] arrayOfInput = GetIntArray(inputNumber); var numList = arrayOfInput.ToList(); int[] newArray = new int[arrayOfInput.Length]; do { int temp = 0; int digitFoundAt = 0; for (i = numList.Count; i > 0; i--) { if (numList[i - 1] > temp) { temp = numList[i - 1]; digitFoundAt = i - 1; } } newArray[currentIndexOfNewArray] = temp; currentIndexOfNewArray++; numList.RemoveAt(digitFoundAt); } while (arrayOfInput.Length > currentIndexOfNewArray); Console.WriteLine(GetWholeNumber(newArray)); Console.ReadKey(); } public static int[] GetIntArray(int num) { IList<int> listOfInts = new List<int>(); while (num > 0) { listOfInts.Add(num % 10); num = num / 10; } listOfInts.Reverse(); return listOfInts.ToArray(); } public static double GetWholeNumber(int[] arrayNumber) { double result = 0; double multiplier = 0; var length = arrayNumber.Count() - 1; for(int i = 0; i < arrayNumber.Count(); i++) { multiplier = Math.Pow(10.0, Convert.ToDouble(length)); result += (arrayNumber[i] * multiplier); length = length - 1; } return result; } } 

Answer 29

private static int GetNextHigherNumber(int num) { //given 38276 return 38627

  string numberstring = num.ToString(); char[] sNum = numberstring.ToCharArray(); for (int i = sNum.Length - 1; i > 0; i--) { for (int j = i - 1; j > 0; j--) { if (sNum[i] > sNum[j]) { for (int x = i; x > j; x--) { char chr = sNum[x]; sNum[x] = sNum[x - 1]; sNum[x - 1] = chr; } i = 0; break; } } } numberstring = string.Empty; for(int x= 0 ; x<sNum.Length;x++) { numberstring += sNum[x].ToString(); } return Convert.ToInt32(numberstring); } 

Answer 30

The simple approach to sove this question are:

1. Case 1:- If All digits of given number are in descending order then print “NO”

2. Case 2:- Else find the first number from right-most digit which is lesser than it's right digit (because this is the first digit responsible for violation of CASE 1).

keeping in mind with these two cases we can easily reach out to the solution.You can see the C implementation at best explained What is next