Interview Question
Country: United States
lets say the N digits of A are: [An-1, An-2, ..., A1, A0]
Consider A' which is composed of the N-1 most significant digits of A: [An-1, An-2, ..., A1]
So, A = {A', A0}
To find B:
compute B = {A'+1, A0-1}
If B ends up being more than N digits, then there is no solution.
The solution I gave doesnt handle the "A->09999 B-> 18999" case. What does "next least N-digit number B" mean? clearly, B->18999 is not the next least digit after A->09999!
Algorithm:
-------------------
- Decrement 1 from the least significant digit and increment for 1 it's predecessor only if least significant digit != 0 and predecessor < 9. Reason is you cannot decrement from 0 and increment above 9 to make it fall under 0-9.
- Evaluate the sum of all the digits seen so far.
- If the above condition doesn't satisfy, repeat the same with the same number without the least significant digit.
- The moment we hit the condition, take the sum and find the smallest number for all the rest of the digits seen before.
Code:
-------------------
I treat the number as a number array to account for 0999. 0999 otherwise means octal representation (leading 0).
Let's say I have num = {A0, A1, A2, A3 }
Things to check for
1. Always start with last but 1 (A2 and the second least significant digit) element and check if it is < 9. If it is 9, there's no way you can increment it by 1. Also check if A3 != 0. If so, you cannot decrement it. Hence continue
2. Repeat the above step until you do hit the if case and can break out of the loop. (Since we are looking for the next larger number to satisfy the mentioned condition)
#include <stdio.h>
void smallestNum(int *numarr, int i, int j, int sum)
{
for (j;j>i; j--)
{
int sub = sum>9?9:sum;
numarr[j] = sub;
sum -= sub;
}
}
void nextBig(int *numarr, int length)
{
int sum = numarr[length-1];
for (int i =length-2; i>=0; i--){
sum += numarr[i+1];
if (numarr[i] != 9 and numarr[i+1] != 0)
{
numarr[i] += 1;
numarr[i+1] -= 1;
sum -= 1;
smallestNum(numarr, i, length-1, sum);
break;
}
}
}
int main(void){
int number[] = {1,9,9,9,0};
int length = (int)(sizeof(number)/sizeof(number[0]));
nextBig(number, length);
for (int i=0; i<length; i++)
printf("%d",number[i]);
printf("\n");
}
190 -> 208
1990 ->
public int[] findNext(int[] arr) {
int j = arr.length - 2;
for(int i = arr.length-1; i >=0;i--){
if(j <0) break;
else{
if(arr[i] == 0 || arr[j] == 9){
j--;
continue;
}else{
arr[i]--;
arr[j]++;
break;
}
}
}
return arr;
}
PFB the solution in java. It works fine for all inputs.
package test;
public class MyLearning {
public static void main(String[] args) {
boolean flag = true;
String a = "999999999999212111199999";
int c[] = new int[a.length()];
for (int i = a.length()-1; i >=0; i--) {
c[i]= a.charAt(i)-48;
if(i< a.length() - 1 && c[i] == 9 && flag){
continue;
}else if (i< a.length() - 1 && flag){
c[i+1] = c[i+1] - 1 ;
c[i] = c[i] + 1;
flag = false;
}
}
String b = "";
for (int i = 0; i < c.length; i++) {
b = b+c[i];
}
if (b.equalsIgnoreCase(a)) {
System.out.println("doesn't exist");
}else{
System.out.println(b);
}
}
}
PFB the updated code. Check and let me know if the solution is not valid for any input.
public class MyLearning {
public static void main(String[] args) {
boolean flag = true;
String a = "686";
int j =0;
int c[] = new int[a.length()];
for (int i = a.length()-1; i >=0; i--) {
c[i]= a.charAt(i)-48;
if(i< a.length() - 1 && c[i] == 9 && flag){
continue;
}else if(i == a.length() - 1 && flag && c[i] == 0){
for( j = a.length() - 2 ;j >= 0 ;j--){
if(c[j]!=0&&j!=0){
c[a.length() - 1]= 1;
c[a.length() - 2]=c[j]-1 ;
c[j]=0;
flag = false;
continue;
}else if(j==0){
flag = false;
}
}
}
else if (i < a.length() - 1 && flag ){
c[i]= c[i]+1;
int temp = c[i+1];
c[i+1]= c[a.length()-1]-1;
for( j = a.length() -1 ;j > i+1 ;j--){
c[j]= c[j-1];
}
if(j != a.length() -1)
c[j+1] = temp;
flag = false;
}
}
String b = "";
for (int i = 0; i < c.length; i++) {
b = b+c[i];
}
if (b.equalsIgnoreCase(a)) {
System.out.println("doesn't exist");
}else{
System.out.println(b);
}
}
}
def next_isosum(n):
s = list(n)
s.reverse()
m = len(s)
j = -1
for i in xrange(m):
#find the first digit != 0
if s[i] > '0':
j = i
s[i] = chr(ord(s[i]) - 1)
break
if j == -1:
return None #n ~0000 => no solution possible
for i in xrange(j+1, m):
#now find the first digit != 9, if any
if s[i] < '9':
s[i] = chr(ord(s[i]) + 1)
#all the digits between j included and i exclueded were 9: so we can increment only the last one of them
for k in xrange((i-j)/2 + 1):
tmp = s[j+k]
s[j+k] = s[i-k-1]
s[i-k-1] = tmp
s.reverse()
return ''.join(s)
return None
from sys import stdin
if __name__ == '__main__':
while True:
a = stdin.readline().strip()
print next_isosum(a)
def next_isosum(n):
s = list(n)
s.reverse()
m = len(s)
j = -1
for i in xrange(m):
#find the first digit != 0
if s[i] > '0':
j = i
s[i] = chr(ord(s[i]) - 1)
break
if j == -1:
return None #n ~0000 => no solution possible
for i in xrange(j+1, m):
#now find the first digit != 9, if any
if s[i] < '9':
s[i] = chr(ord(s[i]) + 1)
#all the digits between j included and i exclueded were 9: so we can increment only the last one of them
for k in xrange((i-j)/2 + 1):
tmp = s[j+k]
s[j+k] = s[i-k-1]
s[i-k-1] = tmp
s.reverse()
return ''.join(s)
return None
from sys import stdin
if __name__ == '__main__':
while True:
a = stdin.readline().strip()
print next_isosum(a)
Here's my solution.
Running complexity O(2n) worst case, when we don't find a solution.
int *toArray(char *number, int size)
{
int *buffer = new int(size);
for (int i=0; i<size; i++) {
buffer[i] = number[i] - '0';
}
return buffer;
}
int length(int n)
{
int len = 1;
while ((n /= 10))
++len;
return len;
}
bool canIncrease(int slot)
{
assert(slot >= 0);
assert(slot <= 9);
return (slot != 9);
}
bool canDecrease(int slot)
{
assert(slot >= 0);
assert(slot <= 9);
return (slot != 0);
}
bool process(int *array, int size)
{
assert(size > 0);
assert(array != NULL);
if (size < 2)
return false;
int p1 = size-2;
int p2 = size-1;
while (!canIncrease(array[p1])) {
--p1;
--p2;
if (p1 < 0)
break;
}
while (!canDecrease(array[p2])) {
++p2;
if (p2 == size)
break;
}
if (p1 >= 0 && p2 < size && p1 < p2){
array[p1]++;
array[p2]--;
return true;
}
return false;
}
int main(){
int n = 0;
int size = length(n);
int *result = toArray(n);
if (process(result, size)){
printf("%d\n\n", *result);
}
delete result;
n = 111;
size = length(n);
result = toArray(n);
if (process(result, size)){
printf("%d\n", result[0]);
printf("%d\n", result[1]);
printf("%d\n\n", result[2]);
}
delete result;
n = 5;
size = length(n);
result = toArray(n);
if (process(result, size)){
printf("%d\n", result[0]);
printf("%d\n", result[1]);
printf("%d\n\n", result[2]);
}
delete result;
char number[] = "09999";
result = toArray(number, 5);
if (process(result, 5)){
printf("%d\n", result[0]);
printf("%d\n", result[1]);
printf("%d\n", result[2]);
printf("%d\n", result[3]);
printf("%d\n", result[4]);
}
delete result;
}
Leave the least significant digit. From 2nd digit onwards,find the first digit which is not 9.If no such digit,return error or -1
Let k be that digit..store all digits before that in an array
Increment kth digit by 1 and for all digits before kth digit,sort them and then, decrement the lowest nonzero digit and add after the incremented digit
111
kth digit is 2nd one
increment it to 2 and den decrement 1 at LSB
191
increment 1 at MSB to 2
sorting gives 1 9,decrement 1 to 0 and add after 2...its 209
check for other numbers 190-208
0999-1899 and so on
You might have realized this by now, but what if the input is 1100? In that case all the digits before k are zero and so you can't "decrement the lowest nonzero digit"...
Divide the number into four regions:
Region 1: Trailing zeros.
Region 2: The lowest digit not in Region 1.
Region 3: Consecutive 9s starting with the digit above Region 2.
Region 4: All remaining digits.
Region 1 and Region 3 may be empty. Region 4 may also be empty: if it is assume that it has value 0.
The required number is made up from bolting together the values
Region 4+1Region 1Region 2−1Region 3.
It is obvious that the number of digits is the same because the 1 added to Region 4 is cancelled out by the 1 subtracted from Region 2 and all the other digits are the same, if in a different order.
Example 1: 217 has no Region 1 or Region 3, Region 2 is 7 and Region 4 is 21. The required number is made up from 21+1 and 7−1, or 226.
Example 2: 197 has no Region 1, Region 2 is 7, Region 3 is 9 and Region 4 is 1. The required number is made up from 1+1 and 7−1 and 9, or 269.
Example 3: 97 has no Region 1, Region 2 is 7, Region 3 is 9 and Region 4 is empty so is assigned 0. The required number is made up from 0+1 and 7−1 and 9, or 169.
Example 4: 199 has no Region 1, Region 2 is 9, Region 3 is 9 and Region 4 is 1. The required number is made up from 1+1 and 9−1 and 9, or 289.
Example 5: 468992000 Region 1 is 000, Region 2 is 2, Region 3 is 99 and Region 4 is 468. The required number is made up from 468+1 and 000 and and 2−1 and 99, or 469000199.
Here's my solution:
#include<iostream>
#include<cstring>
using namespace std;
int main(){
string s;
int arr[50],l,i,j,t,sum=0,flag=0;
cin>>s;
l=s.length();
for(i=0;i<l;i++)
arr[i]=s[i]-'0';
sum=arr[l-1];
cout<<sum<<"\n";
for(i=l-2;i>=0 && flag==0;)
{
sum+=arr[i];
if(arr[i]==9 || sum<arr[i]+1)
{
i--;
continue;
}
t=sum-arr[i]-1;
for(j=l-1;j>=i+1 && t>=0;j--)
{
if(t<=9)
arr[j]=t;
else
arr[j]=9;
t=t-arr[j];
}
if(t==0){
arr[i]=arr[i]+1;
flag=1;
}
}
if(flag==0)
cout<<"not possible";
else {
for(i=0;i<l;i++)
cout<<arr[i];
}
return 0;
}
Here;s my solution
#include<iostream>
#include<cstring>
using namespace std;
int main(){
string s;
int arr[50],l,i,j,t,sum=0,flag=0;
cin>>s;
l=s.length();
for(i=0;i<l;i++)
arr[i]=s[i]-'0';
sum=arr[l-1];
cout<<sum<<"\n";
for(i=l-2;i>=0 && flag==0;)
{
sum+=arr[i];
if(arr[i]==9 || sum<arr[i]+1)
{
i--;
continue;
}
t=sum-arr[i]-1;
for(j=l-1;j>=i+1 && t>=0;j--)
{
if(t<=9)
arr[j]=t;
else
arr[j]=9;
t=t-arr[j];
}
if(t==0){
arr[i]=arr[i]+1;
flag=1;
}
}
if(flag==0)
cout<<"not possible";
else {
for(i=0;i<l;i++)
cout<<arr[i];
}
return 0;
}
function calculate_b(array $a)
{
if (is_array($a))
{
$a_index = $b_index = 0;
//find the lowest a index, and next b index.
for ($i = 0; $i < count($a); $i++) {
if ($a[$a_index] > $a[$i])
$a_index = $i;
if ($a[$i] >= $a[$i] && $a[$i] < 9)
$b_index = $i;
}
//if the index is the same, then set the b_index.
if ($a_index == $b_index) {
//if value at $a_index is 9, then there is no result.
if ($a[$a_index] == 9) {
return false;
} else {
//else set b_index to the last index.
$b_index = count($a) -1;
}
}
$a[$a_index] = ($a[$a_index] == 0) ? ($a[$a_index] + 1) : ($a[$a_index] - 1);
$a[$b_index] = ($a[$b_index] == 9) ? ($a[$b_index] - 1) : ($a[$b_index] += 1);
for ($i = 0; $i < count($a); $i++) {
if ($a[$i] == 0) {
array_push($a, $a[$i]);
unset($a[$i]);
}
}
return $a;
}
}
This is the code in PHP.
function calculate_b(array $a)
{
if (is_array($a))
{
$a_index = $b_index = 0;
//find the lowest a index, and next b index.
for ($i = 0; $i < count($a); $i++) {
if ($a[$a_index] > $a[$i])
$a_index = $i;
if ($a[$i] >= $a[$i] && $a[$i] < 9)
$b_index = $i;
}
//if the index is the same, then set the b_index.
if ($a_index == $b_index) {
//if value at $a_index is 9, then there is no result.
if ($a[$a_index] == 9) {
return false;
} else {
//else set b_index to the last index.
$b_index = count($a) -1;
}
}
if ($a[$a_index] == 0) {
$a[$a_index] += 1;
$a[$b_index] -= 1;
} else {
$a[$a_index] -= 1;
$a[$b_index] += 1;
}
for ($i = 0; $i < count($a); $i++) {
if ($a[$i] == 0) {
array_push($a, $a[$i]);
unset($a[$i]);
}
}
return $a;
}
}
Check to see if it's correct :P
I found the first non 9 number and incremented it.
Decremented the digit after it.
But it doesnt solve the 999->doesnt exist case. Please help me will that :\
int Next(int a)
{
int b,f,c,level=1;
f=a;
b=a;
while(f!=0)
{
c=f%10;
f=f/10;
if((f%10)+1<10)
{
b=b+pow(10,level);
b=b-pow(10,level-1);
break;
}
else
level++;
}
return b;
}
Leave the least significant digit. From 2nd digit onwards,find the first digit which is not 9.Let k be that digit
Increment kth digit by 1 and decrement (k-1)th digit by 1. I think that will serve the purpose
Example of 111->120 doesn't fit in your solution.
Your solution, for the input 111 will be 021
no by k-1 i meant 1st digit
kth digit is 1"1"1
k-1 th digit is 11"1"
so output is correct--1(1+1)(1-1)=120
@maneesh--here kth digit is 0
and (k-1)th digit is last 9
so 0 is changed to 1 and 9 to 8
so output is 18999
Let A=[An-1, An-2, ..., A1, A0].
- Sunny June 20, 2013Let i be the smallest value such that Ai is > 0.
Let j be the smallest value > i such that Aj is < 9.
If no such i & j exist, then there's no solution.
Otherwise, decrement Ai and increment Aj.
We know all digits to the right of i are 0, and that all digits between j and i are 9, by definition of i & j.
So the digits should look like An-1, ..., Aj, 9, ..., 9, Ai, 0, ..., 0
That means if we simply reverse all the digits to the right of Aj, we should have the answer.
For example, if A=[1, 1, 1], then i=0 and j=1. We then have [1, 2, 0] and that's the answer.
If A=[0, 9, 9, 9, 9], then i=0 and j=4. We then have [1, 9, 9, 9, 8], so after reversing we have [1, 8, 9, 9, 9].
If A=[9, 9, 9] then i=0 but no valid value for j, so no answer.