## Interview Question

• 0

Country: India
Interview Type: In-Person

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

You can refer to the following logic:
a.If zero does not exist in the array then number is not possible.
b.Sort the whole array and then calculate the sum of the whole array.If the sum of the digits is divisible by 3 then the number can be formed and generate the number.
c.If sum of digits is not divisible by 3 then as the array is sorted take every number and subtract it from the sum just calculated above. If sum is divisible by 3 then generate the number and if not then continue further in this fashion.
d.The array is sorted to get the largest number formed from the array.
Here is the below code:

``````#include <stdio.h>
#include <stdlib.h>

int compare(const void *a,const void *b)
{
return (*(int *)a-*(int *)b);
}
int calculateSum(int arr[],int n)
{
int i,sum=0;
for(i=0;i<n;i++)
sum=sum+arr[i];
return sum;
}
int generateNumber(int arr[],int j,int n)
{
int i;
int num=0,power,k=0;
for(i=j;i<n;i++)
{
power=(arr[i]*pow(10.0,k));
num=power+num;
k=k+1;
}
//to include last zero in the number
return (num+1)*10;
}
void findSum(int arr[],int n)
{
int i=0,sum,num;
if(arr[i]!=0)
{
printf("\nNumber not possible");
return;
}
else
{
sum=calculateSum(arr,n);
if(sum%3==0)
{
num=generateNumber(arr,1,n);
printf("The number is %d ",num);
return;
}
else
{
for(i=0;i<n;i++)
{
int c=sum;
sum=sum-arr[i];
if(sum%3==0)
{
num=generateNumber(arr,i+1,n);
printf("The number is %d ",num);
return;
}
else
{
sum=c;
}
}
}
}
}
void printArray(int arr[],int n)
{
int i;
for(i=0;i<n;i++)
printf(" %d ",arr[i]);
}
int main()
{
int arr[]={6,7,8,0,1,2};
int i;
int n=sizeof(arr)/sizeof(arr);
qsort(arr,n,sizeof(int),compare);
printArray(arr,n);
findSum(arr,n);
}``````

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

Based on your description it sounds like you are only removing at most 1 digit if the sum % 3 isn't zero? What about cases when you need to remove 2 digits, such as {3, 2, 2, 0} and {3, 1, 1, 0}?

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

@Sunny

In the for-loop vgeek is removing the elements until the sum % 3 = 0. I think that should work.

Can this algorithm be generalized for m generic divisors d1,d2...dm?

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

Then consider {7, 4, 2, 1, 0}. If I understand his for-loop properly, he would try removing 1 then 2 then 4 then 7 then finally conclude no solution exists. That's because after removing each of these numbers the sum%3 is still not 0.

The solution should be to just remove 2 because that would immediately make sum%3 = 0.

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

i have edited the code it should work now.

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

Hmm but I think now it will not work for cases like {3, 1, 1, 0}, which was working before...

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

the test cases you given may not be correct, 8610 also can be divisible by 2,3,5.
several points:
- the latest digit must be 0;
- all digits add up sum can divide by 3;

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

Actually 8760 would be the biggest in this case.
This problem essentially boils down to "given an array of non-zero digits, generate the largest number that can be divisible by 3", because you simply need to place all the zeros on the right. If there's no zero, then no solution exists, because only when the last digit is 0 can the number be divisible by both 2 & 5.

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

The result should be 8760.

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

can someone plz explain why not 8760...?

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

the answer is 8760 only..the question maker might have made some mistake..

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

for the first case, the out put should be 8760

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

Several mathematical properties:
(1) Number is divisible by both 2 & 5 only when last digit is 0
(2) Number is divisible by 3 only when sum of digits is divisible by 3

Having said that, this is my algorithm:
(1) First sort all the digits
(2) If the ones-digit isn't 0, then no solution
(3) Otherwise, the sum of digits modulo 3 is either 0, 1 or 2
(4) If mod3 is 2 and there isn't at least a digit with modulo=2 or 2 digits with modulo=1, then no solution
(5) If mod3 is 1 and there isn't at least a digit with modulo=1 or 2 digits with modulo=2, then no solution
(6) Otherwise, we proceed to create the number by carefully checking which digits we should skip over to ensure the final number has modulo=0
(7) The code is actually rather messy and I don't know how to drastically clean it up

``````static int maxDivisible(int[] arr) {
Arrays.sort(arr);

int mod3 = 0;
int numMod2 = 0;
int numMod1 = 0;
for(int i : arr) {
int modulo = i%3;
mod3 = (mod3 + modulo)%3;
if(modulo == 2)
numMod2++;
else if(modulo == 1)
numMod1++;
}
if(arr != 0)
return -1;
if(mod3 == 2 && numMod2 < 1 && numMod1 < 2)
return -1;
if(mod3 == 1 && numMod1 < 1 && numMod2 < 2)
return -1;

int total = 0;
int multiplier = 1;
for(int i=0; i<arr.length; i++) {
int digit = arr[i];
int modulo = digit%3;
if(mod3 == 2) {
if(modulo == 2) {
// skip this digit
mod3 = 0;
continue;
} else if(modulo == 1 && numMod2 == 0) {
// skip this digit only if numMod2 == 0,
// because it's better to remove 1 digit than 2 digits
mod3 = 1;
continue;
}
} else if(mod3 == 1) {
if(modulo == 1) {
mod3 = 0;
continue;
} else if(modulo == 2 && numMod1 == 0) {
mod3 = 2;
continue;
}
}
total += digit * multiplier;
multiplier *= 10;
}
}``````

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

As people have mentioned, a zero must be the final digit. The sum of the rest of the numbers must be divisible by 3.
First off, we can select any numbers which are multiples of 3, since when added to the other numbers they will not change its 3-divisibility.
Next, for the remaining numbers each number is either one or two removed from a 3-divisible (e.g. 4 is one removed, 5 is two removed, six is divisible again).

That means that for the rest of the numbers, you have to remove at most two numbers (two one-removed numbers) since if you have 3 numbers of any combination (2x1 + 1x2 = 3 + 1, so remove a one; 1x1 2x2 = 3 + 2, so remove a two; 3x1 or 3x2 is fine, since they'll be 3-divisible) then you will find a way to use at least two of those numbers.
Look through the list, remove the smallest possible numbers, and sort the remaining numbers from largest to smallest to make your result.

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

int residual = sum % 3;
if(residual != 0){
int modulo1 = count_if(arr, arr + len, [](int i)->bool{ return i % 3 == 1; });
int modulo2 = count_if(arr, arr + len, [](int i)->bool{ return i % 3 == 2; });
int replaceMod;
int cnt;

if(modulo2 == 0){
replaceMod = 1;
cnt = residual;
}
else if(modulo1 == 0){
replaceMod = 2;
cnt = (residual == 1) ? 2 : 1;
}
else {
replaceMod = residual;
cnt = 1;
}

newLen -= cnt;

for(int i = len - 2; i >= 0; --i){
if(arr[i] % 3 == replaceMod){
arr[i] = 0;
cnt --;

if(cnt == 0) break;
}
}
}

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

first check for 0 .if no of 0 are zero return -1;
else
count no of 9,8,7,6,5,4,3,2,1,0 in arry ..
as 9,6,3 are always divisble by 3.so they will be in answer always..
now check for

``````8,8,8
8,8,2
8,5,2
8,2,2
7,7,7
7,7,1
7,4,1
5,5,5
5,2,2
4,4,4
4,4,1
2,2,2
1,1,1
8,7
8,4
8,1
7,5
7,2
5,4
5,1
4,2
2,1
combination``````

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

``````public final class MaxNumberGenerator {

private MaxNumberGenerator(){
super();
}

private static final BigInteger ONE_MINUS = new BigInteger("-1");

public static BigInteger findMax( int[] baseArr ){

int zeroElemIndex = findZeroIndex(baseArr);

// check for '0' element index
if( zeroElemIndex < 0 ){
return ONE_MINUS;
}

// copy array except zero index
int[] arr = copyArrayExceptOneElement(baseArr, zeroElemIndex);

sortInReverseOrder( arr );

List<List<Integer>> rems = remBuckets( arr, 3);

List<Integer> maxNumber = merge(listToArr(rems.get(0)), listToArr(rems.get(1)), listToArr(rems.get(2)));

return decimalListToInt(maxNumber);
}

@SuppressWarnings("serial")
private static List<List<Integer>> remBuckets(int[] arr, int divValue){

final List<Integer> zero = new ArrayList<>();
final List<Integer> one = new ArrayList<>();
final List<Integer> two = new ArrayList<>();

for( int val : arr ){
int rem = val % divValue;

if( rem == 0 ){
}
else if( rem == 1){
}
else {
}
}

}

private static int[] copyArrayExceptOneElement(int[] baseArr, int indexToSkip){

int[] arr = new int[baseArr.length-1];
int arrIndex = 0;

for( int i =0; i < arr.length;  ){

if( arrIndex != indexToSkip ){
arr[i] = baseArr[arrIndex];
++i;
}

++arrIndex;
}
return arr;
}

private static void sortInReverseOrder( int[] arr ){
Arrays.sort( arr );

int left = 0;
int right = arr.length-1;

while( left < right ){

int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;

++left;
--right;
}

}

private static int findZeroIndex( int[] arr ){

for( int i = 0; i < arr.length; i++ ){
if( arr[i] == 0 ){
return i;
}
}

return -1;
}

private static BigInteger decimalListToInt( List<Integer> list ){

Iterator<Integer> it = list.iterator();

BigInteger res = BigInteger.ZERO;

while( it.hasNext() ){
res = res.multiply( BigInteger.TEN).add( BigInteger.valueOf(it.next()) );
}

return res;
}

private static int[] listToArr( List<Integer> list ){
int[] arr = new int[list.size()];

for( int i =0; i < arr.length; i++ ){
arr[i] = list.get(i);
}
return arr;
}

private static List<Integer> merge( int[] zero, int[] one, int[] two  ){

List<Integer> number = new ArrayList<>();

int zeroIndex = 0;
int oneIndex = 0;
int twoIndex = 0;

while( oneIndex < one.length ){

int zeroValue = (zeroIndex < zero.length ? zero[zeroIndex] : Integer.MIN_VALUE);

if( twoIndex >= two.length ){

if( oneIndex >= one.length - 2 ){
break;
}

while( oneIndex < one.length - 2 ){

for( int i =0; i < 3; i++, oneIndex++ ){

while( zeroIndex < zero.length && zero[zeroIndex] > one[oneIndex] ){
++zeroIndex;
}

}
}
}
else {
if( one[oneIndex] > zeroValue ){

if( two[twoIndex] > zeroValue ){

++oneIndex;
++twoIndex;
}
else {
if( zeroValue != Integer.MIN_VALUE){
zeroValue = zero[zeroIndex++];
}

++oneIndex;
++twoIndex;
}
}
else if( two[twoIndex] > zeroValue ){

if( zeroValue != Integer.MIN_VALUE){
zeroValue = zero[zeroIndex++];
}

++oneIndex;
++twoIndex;

}
}
}

while( zeroIndex < zero.length ){
++zeroIndex;
}

return number;
}

}``````

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

test cases:

``````assertEquals( new BigInteger("8760"), MaxNumberGenerator.findMax( new int[]{1,8,7,6,0}) );
assertEquals( new BigInteger("87600"), MaxNumberGenerator.findMax( new int[]{1,8,0,7,6,0}) );
assertEquals( new BigInteger("97770"), MaxNumberGenerator.findMax( new int[]{7,7,7,9,0}) );
assertEquals( new BigInteger("77760"), MaxNumberGenerator.findMax( new int[]{7,7,7,6,0}) );
assertEquals( new BigInteger("870"), MaxNumberGenerator.findMax( new int[]{7,0,8}) );

assertEquals( new BigInteger("-1"), MaxNumberGenerator.findMax( new int[]{7,7,7,6}) );

int[] bigArr = new int[]{3, 9, 3, 7, 0, 7, 0, 4, 6, 9};
assertEquals( new BigInteger("9977643300"), MaxNumberGenerator.findMax(bigArr) );``````

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

Can you please try finding value for following array {1,2,8,7,6,0} with your logic ?

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

Will generate "876210" number.

876210 % 2 == 0
876210 % 3 == 0
876210 % 5 == 0

So, works correctly.

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

Step1: Sort the digits {8,7,6,1,0}
Step2: if least number is not zero , return false
Step3: construct any array with reminders {2,1,0,1,0}
Step4: get the sum of reminders and get the reminder of this sum from 3. (2+1+0+1+0)%3 = 4 %3 = 1
step5: if reminder is zero, format the number from sorted array and print it. If reminder is not zero, move to next step
Step6: Check if the reminder exists in the list.
step7: if YES, remove the least number yielding that reminder. {2,1,0,1,0} -- remove 1 in this case
if NO, start removing the least numbers that yield non-zero reminders, so that the sum of reminders of removed numbers equal to calculated reminder.

Format the number with remaining digits.

Code:

``````#include <iostream>

using namespace std;

long getMaxNumber(int a[],int size);

int main()
{
int a[] = {1,2,4,9,0,0};

int n = sizeof(a)/sizeof(a);

long number = getMaxNumber(a,n);

cout <<"number : "<<number <<endl;

getchar();
return 0;

}

//bubble sort, assending order
void sort(int a[],int n)
{
for(int i = 0 ; i < n  ; i++)
{
for(int j = 0 ; j< n-1 ; j++)
{
if(a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;

}
}
}

}
long getMaxNumber(int input[],int size)
{
//I don't want to touch the original array.
//Copy the elements into new array
int a[size];
for(int i = 0 ; i < size ; i++)
{
a[i] = input[i];
}
sort(a,size);

//least element is not zero, i.e. zero is not present in the array.
// Hence not divisible by 2 and 5
if(a != 0 ) return -1;

int rem[size];
int rem_sum = 0;

//populate all the reminders of digits into new array
// Also trying to get the sum of reminder at the same time
for(int i = 0; i < size ; i++)
{
rem_sum += (rem[i] = a[i]%3);
}

// reminder that is in excess
rem_sum %= 3;

//stores the indices of digits in the array, that we are going to remove
int removed_index = {-1,-1};

if(rem_sum != 0)
{
int removed_rem_sum = 0;
for(int i = 0 , j=0 ; i < size ; i++)
{
if(rem[i] == rem_sum) // equal case
{
removed_index = i;
removed_index = -1;
break;
}
else if(rem[i] > rem_sum) // greater case
{
continue;
}
else if(removed_rem_sum != rem_sum && rem[i]!=0)//lesser case
{
removed_index[j] = i;
removed_rem_sum += rem[i];
j++;
}

} //for loop

//we were not able to remove anything
//for example: in case the the digits are 0,5,8
if(removed_index == -1)
return 0;
} //if rem_sum!=0

long number = 0;
for(int i = size-1 ; i > -1 ; i-- )
{
if(removed_index != i && removed_index != i)
{
number = number*10 + a[i];
}
}

return number;

}``````

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.