## InMobi Interview Question

Country: India
Interview Type: Written Test

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

``````/**
* Given a number, return the count of numbers having non-repeating
* digits till that number starting from 1.
*
* ("Non-repeating digits" is ambiguous.
* Let's assume it means two consecutive digits can not be the same.
* If it means that all digits are unique the logic is very similar as well.)
*
*/

function count (n) {
var A =  []
var i = 0
var r = n / (Math.pow(10, i))
while (r > 1) {
A[i++] = true
r = n / (Math.pow(10, i))
}
if (A.length === 1) {
return
}
console.log(A)
var l = A.length - 1
for (i = 0; i < l; ++i) {
if (i === 0) {
A[i] = 9 // 9 ways to select 1 number 1-9
continue
}
A[i] = 10 - 1 // 10 ways to select any next digit
// except can't select the previous
// digit = 10 -1 = 9 ways

}

console.log(A)
var B = []
// Calculate out the sum for each of the powers of 10
// except the highest power of 10
// given n = 3456
// 1->9 9 ways
// 10->99 81 ways
// 100->999 729 ways
// etc.
for (i = 0; i < l; ++i) {
if (i === 0) {
B[0] = A[0]
} else {
B[i] = A[i] * B[i - 1]
}
}
console.log(B)

l = A.length - 1

// For the remainder we need to deal with each power of 10
// separately:
// 1000-2999
// 3000-3399
// 3400-3449
// 3450-3456
for (; l >= 0; l--) {
var base = Math.pow(10, l)
var to = Math.floor(n /base) * base
to -= l === 0 ? 0 : 1
console.log(to)
to = '' + to //convert to string
var sum = 1
for (i = 0; i <= l; ++i) {
sum = to.charAt(to.length - 1 - i) * sum
}
console.log(sum)
B.push(sum)
}
console.log(B)

sum = 0
// now sum everything up.
for (i = 0; i < B.length; ++i) {
sum += B[i]
}

}

count(3456) //Ans: 2562
count(7) //Ans: 7
count(22) //Ans: 20
count(100) //Ans: 90
count(99) //Ans: 90
count(37) //Ans: 34``````

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

For simplicity, I considered the input as an array instead of digits, however logic is same.

``````#include <iostream>
#include <set>

using namespace std;

int main()
{
int n[5] = { 2, 2, 2, 2, 4 };
set<int> nset;
for (int i = 0; i < 5; i++)
{
nset.insert(n[i]);
}

int sum = 0;
for (int k : nset)
sum += k;

cout << sum << endl;
}``````

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

#include <iostream>
#include <set>

using namespace std;

int main()
{
int n[5] = { 2, 2, 2, 2, 4 };
set<int> nset;
for (int i = 0; i < 5; i++)
{
nset.insert(n[i]);
}

int sum = 0;
for (int k : nset)
sum += k;

cout << sum << endl;
}

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

Hello,

Thanks srterpe. I meant the same thing as the unique digits can you please post the code here for that?

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

Here's the solution using Javascript / es6

``````const count = (number) => {
let toCount = [], temp;
for(let i = 1; i <= number; i++) {
temp = new Set(i.toString().split(''));
if (temp.size === i.toString().split('').length) {
toCount.push(i);
}
}
}``````

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

This problem can be imagined as a permutation problem.
Observe the following. Suppose the number *n* has no of decimal digit *d*.
The problem has no solution if d > 10. You can generalise it to any base now.
Now, start with generating permutations of :

*1* out of D = [ 0, 1, 2, ...., 8, 9 ].
Then, *2* out of D ( note for leading 0s )
Then *3* out of D ( note for leading 0s )
....
Finally *d* out of D, and there, we need to find how many of them are smaller then n.
One can theoretically reach that no, given a number.

So, let's solve it for 42.
Clearly for
d = 1 -> 1-9 ( 9 ) options
d = 2 -> There are total 10 * 9 options, out of which 9 has leading zeros.
That takes the toll to 81. How many of them are larger than 42 ?
Obvious,
There are [5,6,...9] for the first digit and [0,1,...,9] for the next.
Also there are 4 for first and [3,5,...9] for second digit.

Hence, there are 5 * 9 + 6 unique digited nos greater than 42.

Hence, the total is : 9 + 81 - 51 = 39
Now, let's verify with ZoomBA:

``````n = 42
t = sum ( [1: n + 1 ] ) -> {
x = str(\$.o)
#|set( x.value )| == #|x| ? 1 : 0
}
println( t )``````

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

``````//specialNumbers : numbers which don't have any digit repeated.
public void init() {
ncr = new long[11][11];
fac = new long[11];
fac[0] = 1;
for (int i = 1; i < 11; ++i)
fac[i] = fac[i-1] * i;
for (int i = 0; i < 11; ++i)
for (int j = 0; j < 11; j++)
ncr[i][j] = 0;
ncr[0][0] = 1;
for (int i = 1; i < 11; ++i) {
ncr[i][0] = 1;
for (int j = 1; j <= i; ++j)
ncr[i][j] = ncr[i-1][j] + ncr[i-1][j-1];
}
}
/**
* Input and set bounds.
* Max(specialNumbers) is 9876543210. (pigeonhole principle).
*/
private String getN() {
String mx = "9876543210";
String input = IO.nextLine();
if (input.length() > mx.length())
return mx;
else if (input.length() < mx.length())
return input;
else if (input.compareTo(mx) > 0)
return mx;
else return input;
}

void solve() {
numStr = getN();
len = numStr.length();
boolean[] isAvail = new boolean[10];
Arrays.fill(isAvail, true);

long ans = count(0, isAvail, 10);
for (int i = 1; i < len; i++) {
// 'i' length specialNumbers.
ans += fac[i - 1] * ncr[9][i - 1] * 9;
}

IO.writer.println(ans);
}

/**
* count specialNumbers of length 'len' which are less than or equal to "numStr".
* Iterate "numStr" left to right, maintaining which digits we have used already.
* id : position in "numStr"
* isAvail : maintains which digits we have used
* cnt : number of digits not yet used
*/
long count(int id, boolean[] isAvail, int cnt) {
if (id == len) return 1;

long ans = 0;
int x = numStr.charAt(id) - '0';
int c = 0;

for (int i = 0; i < x; ++i) {
if (cnt == 10 && i == 0) // this case handled in solve() function
continue;
if (isAvail[i])
c++;
}
// count of specialNumbers less than "numStr"
ans = ncr[cnt - 1][len - id - 1] * fac[len - id - 1] * c;

if (isAvail[x]) {
isAvail[x] = false;
ans += count(id + 1, isAvail, cnt - 1);
isAvail[x] = true;
}
return ans;
}``````

Test cases:
100000000000
9876543210
1000000
999999
453
3456
1
10
102

8877690
8877690
168570
168570
342
1939
1
10
91

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

Comment?

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

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class solution {

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int no = scan.nextInt();
int count = 0;
for(int i=1;i<=no;i++)
{
String a = Integer.toString(i);
char[] b =a.toCharArray();
int flag = 0;
if(a.length()>1)
{
for(int j=1;j<a.length();j++)
{
//System.out.println(b[j-1]+"=="+b[j]);
if( (b[j-1]==b[j]))
{
flag =1;
// System.out.println("Has Repeated Numbers!");
break;
}
}
}
if(flag == 0)
{
count++;
//System.out.println("count:"+count+" --> "+"No:"+a);
}
}
System.out.println(count);
}
}

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

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class solution {

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int no = scan.nextInt();
int count = 0;
for(int i=1;i<=no;i++)
{
String a = Integer.toString(i);
char[] b =a.toCharArray();
int flag = 0;
if(a.length()>1)
{
for(int j=1;j<a.length();j++)
{
//System.out.println(b[j-1]+"=="+b[j]);
if( (b[j-1]==b[j]))
{
flag =1;
// System.out.println("Has Repeated Numbers!");
break;
}
}
}
if(flag == 0)
{
count++;
//System.out.println("count:"+count+" --> "+"No:"+a);
}
}
System.out.println(count);
}
}

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

Its great!

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

``````import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class solution {

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int no = scan.nextInt();
int count = 0;
for(int i=1;i<=no;i++)
{
String a = Integer.toString(i);
char[] b =a.toCharArray();
int flag = 0;
if(a.length()>1)
{
for(int j=1;j<a.length();j++)
{
//System.out.println(b[j-1]+"=="+b[j]);
if( (b[j-1]==b[j]))
{
flag =1;
//  System.out.println("Has Repeated Numbers!");
break;
}
}
}
if(flag == 0)
{
count++;
//System.out.println("count:"+count+" --> "+"No:"+a);
}
}
System.out.println(count);
}
}``````

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.