## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
1
of 3 vote

Let A=[An-1, An-2, ..., A1, A0].
Let 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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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!

Comment hidden because of low score. Click to expand.
0

What about A=180? In this case B=199?
Similarly for A=191. In this case B=200?

I am also not sure about the 09999 case being a valid example. It should have just been considered 9999, in which case there is no solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ->

Comment hidden because of low score. Click to expand.
0

Try 191. I think your algorithm will return 281 when the answer should be 209...

Comment hidden because of low score. Click to expand.
0

Updated and fixed.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

My bad, 105 case is missing.....
Will Update

Comment hidden because of low score. Click to expand.
0

It is looking good to me

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Try 191. I think your algorithm will return 281 when the answer should be 209...

Comment hidden because of low score. Click to expand.
0

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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Try 190. You might also want to explain your algorithm next time if you really want people to provide feedback. It's a lot easier to give you a counter-example that way than to first read through your code and try to understand it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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:
print next_isosum(a)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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:
print next_isosum(a)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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"...

Comment hidden because of low score. Click to expand.
0

yes,in this case,I had to traverse until 2nd one as kth digit and for 100 output does not exist

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

I took this from "math.stackexchange.com".
Thanks to peter

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````int fin(int i)
{
int m,j,k,n=9;
m=i;
i=i/10;
while(i%10==9)
{
i/=10;
n*=10;
}
return m+n;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I found the first non 9 number and incremented it.
Decremented the digit after it.

``````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;``````

}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

Example of 111->120 doesn't fit in your solution.
Your solution, for the input 111 will be 021

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

How will the case of 09999 will be handled?

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
1
of 1 vote

Try 191. I think your algorithm will return 281 when the answer should be 209...

Comment hidden because of low score. Click to expand.
0

ok...i am again posting another algo in a separate post

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.