Amazon Interview Question
Software Engineer / DevelopersCountry: India
can be done in o(num_of_digit) time.@Anonymous :no need to sort the number to get the answer.
actually you have to sort the number and the it's the perfect example for counting sort
1. Resolve Ambiguity: Should each digit be used as many times as it appears in the number? Ex: In 7111, should 7 be used only once and 1, only thrice? If yes, there's no bigger number for this scenario of 'XYYY' where X > Y. Can be handled as a special case.
Sounds like BIT Shifting problem. However, here's one solution runs in constant O(no.of.digits forming the number) == O(c) time:
a) Divide no. by 10 and store each digit in array
eg: 7585 ->
- use a counter to count no of digits as you divide by 10, here 4
- again, store in array each digit with [index 0 == digit at unit place, index 1 == digit at 10th place etc] -> int[] digits = {5, 8, 5, 7}
b) Find digits forming bigger no.
//code:
boolean foundBigger = false;
int length = digits.length;
int j = length - 1, i = length - 2;
while(!foundBigger){
if(i == -1){
//exception case of 7111. No bigger no. possible here.
break;
}
if((a[j] > a[i]) || (a[j] == a[i])){
j--;
i--
} else if(a[j] < a[i]){
//swap and found bigger no here
temp = a[j];
a[j] = a[i];
a[i] = temp;
foundBigger = true;
}
}
c) From new array( Eg: [5, 5, 8, 7] ), since we know the digit value: multiple accordingly:
int sum = 0, j = 1;
for (int i = 0; i<digits.length; i++){
sum = sum + a[i] * j;
j = j * 10;
}
Sorry .. Interviewer told me to use same digits with same number of time, coming in positive integer and if a small number is not possible then we have to return -1
how about
1. start from the right most digit ( ones position)
2. check if it is bigger than the immediate left..(tens position)
if yes then
swap them you got the answer
else
check the next left ( hundered postion)
if 10s is bigger than the 100s swap then you got the answer
This might give the right answer because if 1s position is bigger than the 10s then swaping them would give the immediate next bigger number and if it is not then this method will make sure it is smaller than all the subsequent digits traversing from left to right.
eg. 79 ( swap 1s position and 10s)
ans 97
eg 7585
1s(5) < 10s(8) hence do not swap
10s(8)> 100s(5) hence swap
ans 7855
eg. 7439
swap (9,3) ans 7493 ( next bigger no)
Please tell me any counter example in which case it will not work .
Cinderella ,
Take a example of 7684 ..!!
According to you it should be 7864 but the answer is 7846 !! :)
You are very close to the solution !!
May be reverse the string from the position of swap till the last and concatenate with the rest of the number.
7864(reverse 64 => 46) so 7846
76843
78643(reverse 643 => 346)
78346
7558
7855 ( reverse 55 => 55)
796851
798651( reverse 651 => 156)
798156
this reverse might work because while traversing from right to left we have made sure that it is sorted.
Is there a better way ?
@cindrella:
your solution is almost complete..
but it fails for 24965..
as per your logic answer is 29564..
but the answer is 29456...
you should also find correct location for swapped num before sorting...
I think the right solution would be like
1. start from right most digit as @cindrella said and find the digit bigger than immediate left
2. then swap both the digits and sort all the digits to the immediate right of the swapped digit in ascending order
3. in case of 7684, 8 is the swapped number and this will sort 64 to 46 which gives 7846
@nithin tell me if iam wrong
{{public static void main(String[] args) {
String str1 = "12342342355555575753453453421";
assert (str1 != null && str1.length() > 0);
int[] intArray = new int[str1.length()];
for (int i = 0; i < str1.length(); i++) {
intArray[i] = Character.digit(str1.charAt(i), 10);
}
determineNextHighest(intArray);
System.out.printf("Final Value =>" + Arrays.toString(intArray));
}
public static void determineNextHighest(int[] array) {
int len = array.length - 1;
int index = 0;
int j = len;
for (; j > 0; j--) { // iterate till n-1 < n and determine the index where swap happens
if ((array[j - 1] < array[j])) {
index = j - 1;
break;
}
}
if (index == 0) { // no solution here.. for digits in descending order 7654321 etc..
return;
}
findImmediateGreaterAndSort(array, j - 1, len);
}
// the next highest int to be swapped with
private static void findImmediateGreaterAndSort(int[] array, int i, int len) {
int noToSwap = array[i];
for (int j = len; j > i; j--) {
if (noToSwap < array[j]) {
swap(array, i, j); // swap
break;
}
}
// System.out.printf("1st Value =>" + Arrays.toString(array));
//reverse found subarray .. the subarray from i + 1 to len is already in desc order. just reverseing will sort it in asc order
i = i + 1;
for (int x = 0; x <= (len - i) / 2; x++) {
swap(array, i + x, len - x);
}
}
private static void swap(int x[], int a, int b) {
int t = x[a];
x[a] = x[b];
x[b] = t;
}
}}
Take the integer as string arg, decimals; scan right to left, compare sequentially (right to left) everything on the left with current, if current is larger - swap; ascending sort for the digits on the right side of the swap; otherwise make current the one to the left of the previous current, repeat.
We can solve it in another way, hopefully it would work for all the cases.
I am explaining using 2 examples:
1. 7684 - what is the next larger number - (ans : 7846)
Sort the numbers :
4 - a
6 - b
7 - c
8 - d
So, given number 7684 = cbda
Next larger number : check "d" and "a", since d > a the swapping wouldn't help
check : "b", "d" and "a"
For the 1st position - fill "d" as a<b (as we are looking for next greater no.)
For all the rest nos. we just select the least, to make it as small as possible.
For the 2nd position - "a"
For the 3rd position - "b"
So, the answer is : cdab - Using the table shown above = 7846
Example 2 : 24965 - What is the next larger number (ans : 25469)
2 - a
4 - b
5 - c
6 - d
9 - e
24965 = abedc
Since d > c (swapping c to d not helpful) and (e > c and e > d - so swapping of "c", "d" and "e" is not helpful either), so lets take a look at next possibility : "b""e""d""c"
Since b < c, it is definitely going to help find next larger number :
so, swapping "bedc" to "c???" (for ? find the smallest of the remaining) to "cb??" to "cbde" gives us the answer :
acbde = 25469.
For numbers like 9888, print -1..
I think Insertion Sort will work the best.
Letz take 126975
Start from the right and start inserting
Next number -> Sorted Array
5 -> 5
7 -> 57
9 -> 579
(Till now we were inserting only on one side i.e right side - No shifts were required)
6 -> Now we need shifts, instead what we will do is pop the number which is taking the 6's place i.e 7 and bring it to front. Place 6 at its position and we are done
Now we have 7569...Add digits in front which are not yet processed i.e 12
So, final ans will be 127569..
<pre lang="" line="1" title="CodeMonkey60315" class="run-this">int getLargerNum(int dnum)
{
int num[32];
int size = 31;
int cnum = dnum;
while (cnum && size)
{
num[size--] = cnum%10;
cnum /= 10;
}
for (int i = 31;i > size+1;i--)
{
if (num[i] > num[i-1])
{
for (int j = i;j < 31;j++)
{
if (num[j] < num[i] && num[j] > num[i-1])
swap(num+i,num+j);
}
swap(num+i,num+i-1);
for (int j = 31;j > i-1;j--)
{
for (int m = i;m < j;m++)
{
if (num[m] > num[m+1])
swap(num+m,num+m+1);
}
}
break;
}
}
int ret = 0;
for (int j = size+1;j < 32;j++)
{
ret = ret*10+num[j];
}
return ret;
}
</pre><pre title="CodeMonkey60315" input="yes">
</pre>
using System;
using System.Collections.Generic;
using System.Text;
namespace Digits
{
class Program
{
//Simply find the max of the digits starting from the second position.
//So, if your number is 7585.
//Split the number into digits {7,5,8,5} and find the maximum of the set
//{5,8,5}. of course, it can be generalized to any number.
static void Main()
{
int num = 7585;
int[] digits = new int[4];
int index = 4;
int maxIndex = 0;
int max = -1;
while (num != 0)
{
int rem = (num % 10);
num /= 10;
digits[--index] = rem;
if (index != 0 && rem > max)
{
maxIndex = index;
max = rem;
}
}
//Reconstruction
int newNum = digits[0]*10 + digits[maxIndex];
for (int i = 1; i < digits.Length; i++)
if(i != maxIndex)
newNum = (newNum * 10) + digits[i];
Console.WriteLine(newNum);
}
}
}
Taking the example 7465
start from the right
Traverse till you find a digit bigger than the immediate left.( 4 is less than 6)
Exchange it with the next largest digits from the right of the array(since 5 is less than 6, exchange 4 with 5)
Now arrange the remaining digits in ascending order(46)
The number generated will be 7546
@Nitin: ask ur brain to work on. You like spoon-feeding...
73741-> swap(3,4) -> 74731 -> reverse(731) -> 74137.
Got, you dumb stupid?
Here is slightly modified version of cinderella.
1. Go from right to left till the current number is less than immediate left. (Store all the left numbers in array call leftArr and note they are already sorted.)
2. Find the number in leftArr thats immediate bigger than current number and swap with current number. Note that our new leftArr is still sorted.
3. starting to right of new current number, moving towards right end, replace all the numbers with leftArr in increasing order.
Step 2 will be order O(log(n)) so overall order will be O(nlog(n)).
I have yet to code it down. :) But i think it will work for any size.
//Don't know if my code works for any case. It works so far.
//Performance might be boosted by using quick sort instead of bubble sort.
public class NextLarge {
public static void main(String[] args){
int[] data = {8,1,8,9,5,3,2};
int[] nextlarge = mynextlarge(data);
for(int i=0;i<nextlarge.length;i++){
System.out.print(String.valueOf(nextlarge[i])+' ');
}
}
public static int[] mynextlarge(int[] data){
int current = data.length-1;
while(true){
int pos = maxpos(data,current);
if(pos==current){
current--;
}else{
int tmp = data[current];
data[current] = data[pos];
data[pos] = tmp;
data = asendright(data,current);
break;
}
if(current<0)
break;
}
return data;
}
public static int[] asendright(int[] data,int current){
for(int i=current+1;i<=data.length-1;i++){
for(int j=i+1;j<=data.length-1;j++){
if(data[i]>data[j]){
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
}
return data;
}
public static int maxpos(int[] data,int current){
if(current == data.length-1){
return current;
}else{
int max = -9999;
int pos = current;
for(int i=current;i<data.length-1;i++){
if(data[i]>max){
max = data[i];
pos = i;
}
}
return pos;
}
}
}
Following steps should lead to solution:
1. sort the nos
2. In the original no, starting from the 2nd right most position find a position where the no at a position has next higher value than the nos which are right of the no at that position.
3. Now swap the highest no which is found at the right side of that no with that no.
4. starting from the next right position start filling the positions with the nos such that the nos are not in left of the position found in step 2.
ex- Given no is 24965
step 1. 24569
step 2. in the original no ie 24965, starting from 6 we check whether we have any value which is higher than it on its right.. no value found (since 5 is smaller than 6)
next get the 9 and start checking to its right again no value higher than itself.
next check 4, since we have next highest value on it right which is 5.
step 3: swap 4 and 5 so our valid no till now would be 25
step 4: Now chk the sort value found in step 1 fetch one value at a time...and append the values if they are not in the no found in the step 3....
so the no will become
25469
I hope this would be somewhat clear to you...here is a program for it ....let me know if it needs any corrections.
/******** Find the next higher value for a given no *******/
#include<stdio.h>
#include<string.h>
void
get_sorted(int a, int arr_no[], int sort[], int n){
int i, j, tmp;
for(i=0; i<n; i++) {
arr_no[n-i-1]=a%10;
a=a/10;
}
memcpy(sort, arr_no, n*sizeof(int) );
for(i=1; i<n; i++)
{
j=i-1;
while(j>=0)
{
if(sort[j] > sort[j+1])
{
tmp=sort[j];
sort[j]= sort[j+1];
sort[j+1] = tmp;
}
j--;
}
}
for(j=0; j<n; j++)
printf("%d -- %d\n",arr_no[j], sort[j]);
printf("\n");
}
int
nxt_higher_value(int x, int a[], int n) {
int i;
int large=x;
for(i=x+1; i<n; i++)
{
if(a[i] > a[large])
large=i;
}
printf("%d %d\n", large, a[large]);
if(large == x)
return -1;
else
return large;
}
int
main()
{
int a=7585;
int n=4;
int sort[n];
int arr_no[n];
int val, i, j, k;
get_sorted(a, arr_no, sort, n);
for(i=n-2; i>=0; i--)
{
val=nxt_higher_value(i, arr_no, n);
if(val >= 0)
{
arr_no[i]= arr_no[val];
break;
}
}
int flag_continue;
for(k=0; k<n; k++)
{
flag_continue=0;
for(j=0; j<=i; j++)
{
if(sort[k] == arr_no[j])
{
flag_continue=1;
break;
}
}
if(flag_continue)
continue;
arr_no[i+1]=sort[k];
i++;
}
for(i=0; i<n; i++)
printf(" %d", arr_no[i]);
printf("\n");
return 0;
}
I think the simplest solution for this would be to simply extract the digits, store them in an array and sort it in descending order. If the array is already sorted, return -1 else return the sorted array. The question asks to find "a" number which is larger, not the immediately larger number. Can anyone tell me if there is a problem with this solution?
However, if the immediately larger number is to be found.. I believe this solution should work:
1. Extract the numbers and save them in an array.
2. Starting from the right, start scanning the array such that you find a location where the array stops being sorted in an ascending order. ( asc from right )
3. At that position, find the difference between all the digits and the digit in question. Swap it with the digit which has the smallest difference.
4. For all the digits to the right of the digits in question, sort them in descending order.
e.g. lets say 126975
starting from left, 75 is sorted, 975 is sorted, 6975 is not.
x = 6
6-5 = 1
6-7 = -1
6-9 = -3
Since smallest negative difference is with 7, swap the digits 6 and 7, we get.. 127965
Beginning from the right of 7, i.e. position x, sort all the digits in asc order, i.e. smallest first.. we get.. 127569.
#include<stdio.h>
#include<string.h>
void reverse(char s[])
{
printf("entring reverse\n");
int c, i, j;
for (i = 0, j = strlen(s)-1; i < j; i++, j--)
{
c = s[i];
s[i] = s[j];
s[j] = c;
}
printf("exit reverse\n");
}
int atoi(char s[])
{
printf("entring atoi s=%s\n",s);
int i, n, sign;
for (i = 0; (s[i] == ' '); i++) /* skip white space */
;
sign = (s[i] == '-') ? -1 : 1;
if (s[i] == '+' || s[i] == '-') /* skip sign */
i++;
for (n = 0; (s[i] >='0' && s[i] <= '9'); i++)
n = 10 * n + (s[i] - '0');
printf("exit atoi\n");
return sign * n;
}
void itoa(int n , char s[])
{
printf("entring itoa\n");
int i, sign;
if ((sign = n) < 0) /* record sign */
n = -n; /* make n positive */
#include<stdio.h>
#include<string.h>
void reverse(char s[])
{
printf("entring reverse\n");
int c, i, j;
for (i = 0, j = strlen(s)-1; i < j; i++, j--)
{
c = s[i];
s[i] = s[j];
s[j] = c;
}
printf("exit reverse\n");
}
int atoi(char s[])
{
printf("entring atoi s=%s\n",s);
int i, n, sign;
for (i = 0; (s[i] == ' '); i++) /* skip white space */
;
sign = (s[i] == '-') ? -1 : 1;
if (s[i] == '+' || s[i] == '-') /* skip sign */
i++;
for (n = 0; (s[i] >='0' && s[i] <= '9'); i++)
n = 10 * n + (s[i] - '0');
printf("exit atoi\n");
return sign * n;
}
void itoa(int n , char s[])
{
printf("entring itoa\n");
int i, sign;
if ((sign = n) < 0) /* record sign */
n = -n; /* make n positive */
i = 0;
do
{ /* generate digits in reverse order */
s[i++] = n % 10 + '0'; /* get next digit */
} while ((n /= 10) > 0); /* delete it */
if (sign < 0)
s[i++] = '-';
s[i] = '\0';
reverse(s);
printf("exit itoa\n");
}
int find_bigger(int num)
{
printf("inside find_bigger\n");
char str[20]= "\0";
char temp;
int i,j;
itoa(num,str);
printf("str=%s\n",str);
i = strlen(str)-1;
j = strlen(str)-2;
while(j >= 0)
{
if(str[j] < str[i])
{
temp = str[j];
str[j] = str[i];
str[i] = temp;
break;
}
else
{
i--;
j--;
}
}
printf("returning from find_bigger\n");
return atoi(str);
}
int main()
{
int num;
num = find_bigger(4555);
printf("num = %d\n", num);
return 0;
}
I am not sure if any body has already posted this solution:
found = false;
- for(i = n - 1; !found && i > 0; i --)
{
if(numStr[i-1] < numStr[i])
{
found = true;
}
}
if(found)
{
a[i];
// do a insertion sort
for(j = i+1; j < n && a[j] > a[i]; j++)
;
swap(a[i], a[j-1]);
reverse(a , i+1, n-1);
// at this point a[] has the next number than what was originally
// present in a[]
return 1;
}
else
return -1;
public class NextHighest
{
public void sort(int[] num, int i, int length)
{
// sorting algorithm
}
public static void main(String[] args)
{
int[] num = new int[]{7,5,8,6};
int temp = num.length-1;
int i;
for(i=num.length-1;i>1;i--)
{
if(num[i] > num[i-1])
{
int swap = num[i-1];
num[i-1] = num[temp];
num[temp] = swap;
break;
}
else
{
if(a[temp] > num[i])
temp = i;
}
}
sort(num,i,num.length);
}
}
Hi all....
I don't know how much right my solution is...
Give your review...
I have taken an example in the code. Replace that with your input and try.
Thanks...... All the best
<pre lang="" line="1" title="CodeMonkey92592" class="run-this">int FindNextGreater(int num)
{
int previousDigit = -1;
int numOfDigits = NumOfDigits(num);
if(numOfDigits==1)
return -1;
int indexOfPreviousDigit = numOfDigits;
while(num>0)
{
int digit = num%10;
if(digit>previousDigit)
{
previousDigit = digit;
indexOfPreviousDigit--;
continue;
}
return Swap(num, indexOfPreviousDigit, indexOfPreviousDigit-1);
}
return -1;
}</pre><pre title="CodeMonkey92592" input="yes">
</pre>
i tried this, but its giving me error,
1) NumOfDigits not defined in this scope
any idea how to get rid of this err
i tried this, but its giving me error,
1) NumOfDigits not defined in this scope
any idea how to get rid of this err
1.Start from right to left reading each digit
2.If the entire number is read in ascending order then return -1
3.Else stop when it is decreased, swap the decreased digit with the digit immediately bigger than the decreased digit from the set of surpassed digits
4. Sort the remaining digits to the right of the swapped digit
Ex: 1092
1.come from right, the digit decreased from 9 to 0
2. the surpassed digits are 2,9 so swap 0 with immediate bigger digit i.e, 2 (results in 1290)
3. sort remaining digits (1209)
Here is the solution written in C# (Input taken as string to support larger numbers also)
private static string GetNextHighest(string num)
{
StringBuilder number = new StringBuilder(num);
bool flag = false;
int index;
int[] numberCount = new int[10];
if (number.Length == 1)
{
return number.ToString();
}
numberCount[Convert.ToInt32(char.ConvertFromUtf32(number[number.Length - 1]))]++;
for (index = number.Length - 2; index >= 0; index--)
{
if (number[index] < number[index + 1])
{
flag = true;
int swapNumber = Convert.ToInt32(char.ConvertFromUtf32(number[index]));
numberCount[swapNumber]++;
for (int iter = swapNumber + 1; iter < 10; iter++)
{
if (numberCount[iter] > 0)
{
numberCount[iter]--;
number[index++] = Convert.ToChar(iter+48);
break;
}
}
break;
}
numberCount[Convert.ToInt32(char.ConvertFromUtf32(number[index]))]++;
}
if (flag)
{
for (int iterator = 0; iterator < 10; iterator++)
{
for (int iter = 0; iter < numberCount[iterator]; iter++)
{
number[index++] = Convert.ToChar(iterator + 48);
}
}
return number.ToString();
}
else
{
return "-1";
}
}
We can also use the linked list approach
1. Get the last digit from the no and add it to linked list in increasing order.
2. Convert it to no from the sorted linked list.
int BiggestPossibleNo(int n) {
while( n > o) {
rem = n % 10;
n = n / 10;
head = insertSortList(rem); // adds to list in increasing order
no = convertListNo(head);
}
retutn no;
}
int convertListNo(Node head) {
int power = 1;
int no = 0;
while(head) {
no = power * (head->no) + no;
head = head->next;
power *= 10;
}
return no;
}
Sorry guys the convertListNo(head) should be called outside the while loop in BiggestPossibleNo().
int BiggestPossibleNo(int n) {
while( n > o) {
rem = n % 10;
n = n / 10;
head = insertSortList(rem); // adds to list in increasing order
}
no = convertListNo(head);
retutn no;
}
why am i doing this when i can directly sort and put the elements in a stack, pop it and get the max val. Sort in asc and push in stack
Use bucket sort to sort the digits and also count their frequencies and then print them in descending order with each digit occurring according to its frequency.
<pre lang="" line="1" title="CodeMonkey7194" class="run-this">//No need of any data structures
int main()
{
int n=9768;
int num=n;
int reverse=0;
int digit,right;
while(num){
digit=num%10;
num/=10;
right=0;
int p=1;
while(reverse && (reverse%10) < digit){
right=(reverse%10)*p+right;
p*=10;
reverse/=10;
}
reverse=(((reverse*10)+digit)*p)+right;
}
if(n!=reverse) cout<<reverse; else cout<<-1;
cin.ignore(2);
return 0;
}</pre><pre title="CodeMonkey7194" input="yes">
</pre>
int findBigger(int input)
{
int dig = 0;
int digPre = 0;
int i = 0;
int temp = input;
if (temp <= 0)
{
return -1;
}
while (temp != 0)
{
digPre = dig;
dig = temp % 10;
temp = temp / 10;
if (dig < digPre)
{
break;
}
if (temp==0)
{
return -1;
}
i++;
}
return input + 9 * 10^(i-1) * (digPre - dig);
}
time complexity: O(k^2)
code works.
int method(string s)
{
vector<int> v;
int i,j;
int flag=0;
for(i=s.size()-1;i>=0 && !flag;i--)
{
for(j=i-1;j>=0 ;j--)
if(s[j] < s[i])
{
flag=1;
cout<<s[i]<<" "<<s[j]<<" "<<i<<" "<<j<<"\n";
break;
}
if(j<0)
v.push_back(s[i]-'0');
}
if(flag==1)
{
v.push_back(s[j]-'0');
s[j]=s[i+1];
sort(v.begin(),v.end());
for(int i=j+1,k=0;i<s.size();i++,k++)
s[i]=v[k]+'0';
}
cout<<s;
}
<pre lang="" line="1" title="CodeMonkey67436" class="run-this">class BiggestNumber {
int biggestNumber(int n) {
int originalNumber = n;
int[] digitFrequencies = new int[10];
boolean isNegative = n < 0;
if (isNegative) {
n *= -1;
}
while (n != 0) {
++digitFrequencies[n % 10];
n /= 10;
}
n = 0;
if (isNegative) {
for (int i = 1; i < 10; ++i) {
while (digitFrequencies[i] != 0) {
n = n * 10 + i;
digitFrequencies[i] = digitFrequencies[i] - 1;
}
while (digitFrequencies[0] != 0) {
n *= 10;
digitFrequencies[0] = digitFrequencies[0] - 1;
}
}
n *= -1;
} else {
for (int i = 9; i > -1; --i) {
while (digitFrequencies[i] != 0) {
n = n * 10 + i;
digitFrequencies[i] = digitFrequencies[i] - 1;
}
}
}
return n == originalNumber ? -1 : n;
}
public static void main(String[] args) {
BiggestNumber instance = new BiggestNumber();
System.out.println(instance.biggestNumber(0));
System.out.println(instance.biggestNumber(1230));
System.out.println(instance.biggestNumber(-2130));
System.out.println(instance.biggestNumber(3210));
System.out.println(instance.biggestNumber(-1023));
}
}
</pre><pre title="CodeMonkey67436" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey69754" class="run-this">class BiggestNumber {
int biggestNumber(int n) {
int originalNumber = n;
int[] digitFrequencies = new int[10];
boolean isNegative = n < 0;
if (isNegative) {
n *= -1;
}
while (n != 0) {
++digitFrequencies[n % 10];
n /= 10;
}
n = 0;
if (isNegative) {
boolean isZeroThere = digitFrequencies[0] != 0;
if(isZeroThere) {
for(int i = 1; i < 10; ++i) {
if(digitFrequencies[i] != 0) {
n = n * 10 + i;
digitFrequencies[i] = digitFrequencies[i] - 1;
break;
}
}
while (digitFrequencies[0] != 0) {
n *= 10;
digitFrequencies[0] = digitFrequencies[0] - 1;
}
}
for (int i = 1; i < 10; ++i) {
while (digitFrequencies[i] != 0) {
n = n * 10 + i;
digitFrequencies[i] = digitFrequencies[i] - 1;
}
}
n *= -1;
} else {
for (int i = 9; i > -1; --i) {
while (digitFrequencies[i] != 0) {
n = n * 10 + i;
digitFrequencies[i] = digitFrequencies[i] - 1;
}
}
}
return n == originalNumber ? -1 : n;
}
public static void main(String[] args) {
BiggestNumber instance = new BiggestNumber();
System.out.println(instance.biggestNumber(0));
System.out.println(instance.biggestNumber(1230));
System.out.println(instance.biggestNumber(-2130));
System.out.println(instance.biggestNumber(3210));
System.out.println(instance.biggestNumber(-1023));
}
}
</pre><pre title="CodeMonkey69754" input="yes">
</pre>
some people think they are over smart. we are here to study so please behave like a student not like a rascal.
here is my java code. please check it and notify if there is any problem. all constructive comments are welcome.
int given = 73741;
String s = Integer.toString(given);
int [] arr = new int[s.length()];
for(int i=0; i<s.length(); i++){
arr[s.length()-1-i] = given%10;
given = given/10;
}
boolean flag = true;
int k = 0;
int ii = (arr.length-1);
while(ii>=0 && flag==true){
for(k=ii-1; k>=0; k--){
if(arr[k] < arr[ii]){
int temp = arr[ii];
arr[ii] = arr[k];
arr[k] = temp;
flag = false;
break;
}
}
ii--;
}
quicksort(arr, k+1, arr.length-1);
System.out.println("\n");
for(int i=0; i<arr.length; i++){
System.out.print(arr[i]);
}
int a;
cin>>a;
int b=a;
int c[10];
for(int i=0;i<10;i++)
c[i]=0;
int x=-1,y=-1;
i=0;
while(b!=0)
{
i++;
x=b%10;
c[x]++;
b/=10;
if(y>x)
break;
y=x;
}
if(x==y)
cout<<"No. is largest";
else
{
for(int j=++x;j<10;j++)
if(c[j]>0)
{
b=b*10+j;
c[j]--;
i--;
break;
}
int k=0;
for(j=0;j<i && k<10;)
{
if(c[k]>0)
{
b=b*10+k;
c[k]--;
j++;
}
else
k++;
}
cout<<b;
}
My approach:
public int immediateGreater(int num) {
char[] string = String.valueOf(num).toCharArray();
int length = string.length;
if(length<=1)
return -1;
int[] temp = new int[length];
for(int i=0; i<temp.length; i++) {
temp[i] = 10;
}
int realLength = 1;
temp[0] = string[length-1]-'0';
for(int i=length-2; i>=0; i--) {
if(string[i]>=string[i+1]) {
temp[realLength] = string[i]-'0';
realLength++;
}else {
int min = string[i+1]-'0';
int pos = i+1;
for(int j=0; j<realLength; j++) {
if(temp[j]<min&&temp[j]>(string[i]-'0')) {
min = temp[j];
pos = j;
}
}
int y = string[i] - '0';
string[i] = (char)(min+48);
temp[pos] = y;
java.util.Arrays.sort(temp);
pos = 0;
for(int j=realLength; j>0; j--) {
string[string.length-j] = (char) (temp[pos++]+48);
}
return Integer.parseInt(new String(string));
}
}
return -1;
}
It will no be over .. :)
Ex :- 102
Answer should be 120 but if u will sort it will result in 210 ;)
Complexity will be increase if you will take larger digits !!
The question doesnt say to give the immediately larger number. It asks you to find "a" larger number. The complexity argument would actually come into picture if we are literally talking about n to be so significant that it would take too much time. I think hasinamjanu's solution is correct.
If qus is not specific about largest OR larger...!
sorting is quite lengthy... below i am trying to optimize it....!
if number given is ABCD then :
pick A.. match with remaining digits... if found greater then A... swap digits....
else pick B compare with remaining if found greater then B.. swap digits...
else pick C .... and so on...!
surely, neha you are the dumbest person i have ever witnessed posting on forums things that are so obvious.
if it is true what you are saying, its a question even new born baby can solve! if you dont understand question please get out of here (go join nursery school)
The question need to be more specific. Does the interviewer wants the immediate greater number that can be formed or any greater number? for example if given 1234 then answer xan be 1243, 1324,1342 etc. the best way is to start with the right most digit and see if a digit on the left side is smaller than it and then switch their position.
- Algo Visa September 19, 2011