## iCIMS Interview Question for Senior Software Development Engineers

• -1

Country: United States
Interview Type: Written Test

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

Your solution appears to fail at N = 11. Your code above finds the number of 1's to be 1 but it is obviously 4. Did you unit test?

N = 11, Power = 2.85311670611E11, findNumTimes1Appears(11) = 1

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

It fails at N equal to 19:

N = 19, Power = 6.115909044841455E19, findNumTimes1Appears() = 0

You can save me some time checking your answers by writing some test cases. Try these for starters:

``````for (int i = 0; i < 49; ++i) {
System.out.println("N = " + i + ", Power = " + Math.pow(11, i) + ", findNumTimes1Appears() = " + findNumTimes1Appears(i));
}
int N;
N = 50; System.out.println("N = " + N + ", Power = " + Math.pow(11, N) + ", findNumTimes1Appears() = " + findNumTimes1Appears(N));
N = 100; System.out.println("N = " + N + ", Power = " + Math.pow(11, N) + ", findNumTimes1Appears() = " + findNumTimes1Appears(N));
N = 200; System.out.println("N = " + N + ", Power = " + Math.pow(11, N) + ", findNumTimes1Appears() = " + findNumTimes1Appears(N));``````

Also notice that for N=300, the pow() function overflows.

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

What a terrible question.

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

There is a simpler solution :). Just consider that 11 is actually (10 + 1) and suddenly it is trivial.

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

didn't get that. can you plz explain more?

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

didn't get that. can you plz explain more?

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

Instead of working with actual integer, we can use linkedlist to represent the number and calculate the pow. The order of the solution comes to be O(n^2)

``````public static int getCountDigit(int pow) {
if(pow == 0) return 1;
if(pow ==1) return 2;
int ret_count = 0;
for(int i = 1; i < pow; i++) {
int j = number.size() - 2;
int sum = 0;
int carry = 0;
while(j > 0) {
sum = number.get(j) + number.get(j - 1);
number.set(j, ((sum % 10) + carry));
carry = sum / 10;
j--;
}
if(carry != 0) {
number.set(0, number.get(0) + carry);
}
}
for(int i = 0; i < number.size(); i++) {
if(number.get(i) == 1) {
ret_count++;
}
}
return ret_count;
}``````

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

``````public static int getCountDigit(int pow) {
if(pow == 0) return 1;
if(pow ==1) return 2;
int ret_count = 0;
for(int i = 1; i < pow; i++) {
int j = number.size() - 2;
int sum = 0;
int carry = 0;
while(j > 0) {
sum = number.get(j) + number.get(j - 1);
number.set(j, ((sum % 10) + carry));
carry = sum / 10;
j--;
}
if(carry != 0) {
number.set(0, number.get(0) + carry);
}
}
for(int i = 0; i < number.size(); i++) {
if(number.get(i) == 1) {
ret_count++;
}
}
return ret_count;
}``````

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

``````public static int getCountDigit(int pow) {
if(pow == 0) return 1;
if(pow ==1) return 2;
int ret_count = 0;
for(int i = 1; i < pow; i++) {
int j = number.size() - 2;
int sum = 0;
int carry = 0;
while(j > 0) {
sum = number.get(j) + number.get(j - 1);
number.set(j, ((sum % 10) + carry));
carry = sum / 10;
j--;
}
if(carry != 0) {
number.set(0, number.get(0) + carry);
}
}
for(int i = 0; i < number.size(); i++) {
if(number.get(i) == 1) {
ret_count++;
}
}
return ret_count;
}``````

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

Check this out:

``````public class Count {

public static void main(String[] args) {
countOnes(1000);
}

public static int countOnes(int power){
int count = 0;

if(power < 2){
count = power + 1;
} else{
StringBuilder number = new StringBuilder("11");
while((--power) > 0){
char [] charArray = number.toString().toCharArray();
int carry = 0;
number = new StringBuilder(""+charArray[charArray.length-1]);

for (int i = charArray.length-1; i > 0 ; i--) {
int temp = Integer.parseInt(""+charArray[i]) + Integer.parseInt(""+charArray[i-1]) + carry;

carry = temp/10;
temp = temp%10;

number.append(temp);
}

number.append(Integer.parseInt(""+charArray)+carry);
number.reverse();

}

Pattern pattern = Pattern.compile("1");
Matcher matcher = pattern.matcher(number);

while(matcher.find()){
count++;
}
}

return count;
}
}``````

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

import java.util.*;
public class ElevenPowN {
static Scanner in=new Scanner(System.in);
public static void main(String[] args)
{
long pow,val=11,rem = 1,count=0;
System.out.println("Enter the power :");
pow=in.nextInt();

for(int i=1;i<=pow;i++)
{
val=val*11;
}

while(rem!=0)
{
rem=val%10;
if(rem==1) count++;
val=val/10;
}

System.out.println("The number of one's are : "+count);
}

}

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

``````static int CountOfDigitOne(int N, out string l)
{
int c = 0;
string prev = "11";
string current = string.Empty;
for (int i = 2; i <= N; i++)
{
int rem = 0;
current = string.Empty;
for (int j = prev.Length -1 ; j > 0; j--)
{
int digit = prev[j] - '0';
int digit2 = prev[j - 1] - '0';
int n = digit + digit2 + rem;
if (n >= 10)
{
rem = 1;
n -= 10;
}
current = n + current;;
}
current += prev[prev.Length - 1];
current = prev + current;
prev = current;
}
if (N == 0)
{
current = "1";
}
else if (N == 1)
current = "11";
for (int i = 0; i < current.Length; i++)
{
if (current[i] == '1')
c++;

}
l = current;
return c;
}``````

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

``````static int CountOfDigitOne(int N, out string l)
{
int c = 0;
string prev = "11";
string current = string.Empty;
for (int i = 2; i <= N; i++)
{
int rem = 0;
current = string.Empty;
for (int j = prev.Length -1 ; j > 0; j--)
{
int digit = prev[j] - '0';
int digit2 = prev[j - 1] - '0';
int n = digit + digit2 + rem;
if (n >= 10)
{
rem = 1;
n -= 10;
}
current = n + current;;
}
current += prev[prev.Length - 1];
current = prev + current;
prev = current;
}
if (N == 0)
{
current = "1";
}
else if (N == 1)
current = "11";
for (int i = 0; i < current.Length; i++)
{
if (current[i] == '1')
c++;

}
l = current;
return c;
}``````

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

I took a different approach to the problem.
power of 11 is a power of (x+1) where x = 10
( 10 + 1 ) * ( 10 + 1 )
or
(x + 1) * (x+1)
x2 + 2x + 1 ===> power of 2
x3 + 3x2 + 3x + 1 ===> power of 3
x4 + + 4x3 + 6x2 + 4x + 1 ===> power of 4
x5 + 5x4 + 10x3 + 10x2 + 5x + 1 ===> power of 5
The constants at each term of power of x is called binomial coefficient.
For x = 10, if the coefficient is 1 the final number will have a 1.
But if the coefficient is more than 10 we need to carry ahead and add to next power term.

The following code works fine for some numbers I tested and it does not calculate the actual number, so there will be no overflow.

``````unsigned int binomial_coefficient(int n, int k) {
if (k < 0 or k > n)
return 0;
if (k == 0 or k == n)
return 1;
k = std::min(k, n - k);
int c = 1;
for (int i=0; i < k; i++)
c = c * (n - i) / (i + 1);
return c;
}

unsigned int ones_in_power_of_eleven(int N) {
std::vector<unsigned int> binomial_coeffs(N+1);
for (int k=0; k <= N/2; ++k) {
unsigned int c = binomial_coefficient(N,k);
binomial_coeffs[k] = c; // binomial coefficients are symmetric
binomial_coeffs[N-k] = c;
}

for (int i=0; i < N; i++) {
unsigned int coeff = binomial_coeffs[i];
unsigned int cahead = coeff / 10;
unsigned int remainder = coeff % 10;
binomial_coeffs[i] = remainder;
}

int ones = 0;
for (int i=0; i <= N; i++) {
if (binomial_coeffs[i] == 1)
ones++;
}
return ones;
}``````

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

Could you provide this code in Java?

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

It's very interesting solution. I didn't expect to see binomial coefficients here :).
As I can see time complexity is O(N^2) and memory consumption is O(N).

On the other hand the solution where we the number is represented as a container of digits (for example, getCountDigit() method posted by bhanu.ashwani above) has the same time and memory characteristic. IMHO, that solution is more straightforward and obvious than this.

Correct me about solution comparing if I am wrong.

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

I agree with you, this method is less intuitive, I was trying to make it faster by reducing complexity. But it may not be possible.

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

In this special case of (x+1)^N
if we have binomial coefficient == 1, the number will have a 1 in it.
This program used this property to calculate number of 1's in the final number without calculating the number.

``````unsigned int binomial_coefficient(int n, int k) {
if (k < 0 or k > n)
return 0;
if (k == 0 or k == n)
return 1;
k = std::min(k, n - k);
int c = 1;
for (int i=0; i < k; i++)
c = c * (n - i) / (i + 1);
return c;
}

unsigned int ones_in_power_of_eleven(int N) {
std::vector<unsigned int> binomial_coeffs(N+1);
for (int k=0; k <= N/2; ++k) {
unsigned int c = binomial_coefficient(N,k);
binomial_coeffs[k] = c; // binomial coefficients are symmetric
binomial_coeffs[N-k] = c;
}

for (int i=0; i < N; i++) {
unsigned int coeff = binomial_coeffs[i];
unsigned int cahead = coeff / 10;
unsigned int remainder = coeff % 10;
binomial_coeffs[i] = remainder;
}

int ones = 0;
for (int i=0; i <= N; i++) {
if (binomial_coeffs[i] == 1)
ones++;
}
return ones;
}``````

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

As the last comments recommended using pascal triangle would help. I use different way fo calculating the coefficients. I used the literal mathematical formula but the C implementation by @DattaP is more efficient. Here is my Java Code:

``````class Problem{
public int solution(int N){
int carry=0;
int counter=0;
for(int i=0;i<N;i++){
int term= choose(N,i)+carry;
if((term%10)==1)
counter++;
carry=term/10;
}
return counter;
}
int choose(int n, int k){
return (factorial(n))/(factorial(k)*factorial(n-k));
}
int factorial(int n){
int result=1;
for(int i=1;i<=n;i++)
result*=i;
return result;
}
}``````

}

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

For N== 3, solution(3) returns 1 which is clearly wrong.

Also, factorial(35) throws an ArithmeticException.

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

I've used BigInteger to arrive at the solution. Please comment.

``````package find.ones.eleven;

import java.math.BigInteger;

public class FindOnes {

public static void main(String[] noargs) {
System.out.println("Output: " + findOnes(1000));
}

public static int findOnes(int in) {
BigInteger b = BigInteger.valueOf(11);
System.out.println("Input: " + b.toString());
BigInteger bout = b.pow(in);
System.out.println("[DEBUG] 11^" + in + ": " + bout.toString());
char[] carray = bout.toString().toCharArray();
int count = 0;
for(int i = 0; i < carray.length; ++i) {
if(carray[i] == '1') {
++count;
}
}
return count;
}

}``````

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

power(11,N) can be calculated as below.
11
121
1331
14641
161051
1771561
19487171

private static int getNoOfOne(int N){
if (N==0) return 0;
else if (N==1) return 2;
else{
int[][] a=new int[N][N+1];
a=1;
a=1;
for(int i=1;i<N;i++){
a[i]=1;
a[i][N]=1;
for(int j=1;j<N;j++){
a[i][j]=a[i-1][j-1]+a[i-1][j];
if(a[i][j]>=10){
a[i][j-1]+=1;
a[i][j]=a[i][j]%10;
}
}
}
int count=0;
for(int x:a[N-1]){
if(x==1) count++;
}
return count;
}

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

``````class SolutionNumberOfOnesAppearsInElevenPowerN {

public int getNumberOneInElevenPowerN(int n) {

long num = (long) Math.pow(11, n);
long div = (long) Math.pow(10, n);
int count = 0;
System.out.print("(11 ^ " + n + "):  " + num + " \t NUMBER OF 1 : " );
while(num != 0) {
if(num/div == 1) {
count++;
}
num = num % div;
div = div/10;
}
System.out.print(count);
System.out.println();;
return count;
}
}

public class NumberOfOnesAppearsInElevenPowerN {

public static void main(String[] args) {
SolutionNumberOfOnesAppearsInElevenPowerN sol = new SolutionNumberOfOnesAppearsInElevenPowerN();
sol.getNumberOneInElevenPowerN(0);
sol.getNumberOneInElevenPowerN(1);
sol.getNumberOneInElevenPowerN(2);
sol.getNumberOneInElevenPowerN(3);
sol.getNumberOneInElevenPowerN(4);
sol.getNumberOneInElevenPowerN(5);
sol.getNumberOneInElevenPowerN(6);
sol.getNumberOneInElevenPowerN(7);
sol.getNumberOneInElevenPowerN(8);
sol.getNumberOneInElevenPowerN(9);
sol.getNumberOneInElevenPowerN(10);
sol.getNumberOneInElevenPowerN(11);
sol.getNumberOneInElevenPowerN(12);
}
}``````

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

you cannt use Math.pow as it will overflow if you have big N. remember N <= 1000

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

import java.util.*;
public class ElevenPowN {
static Scanner in=new Scanner(System.in);
public static void main(String[] args)
{long pow,val=11,rem = 1,count=0;
System.out.println("Enter the power :");
pow=in.nextInt();

for(int i=1;i<=pow;i++)
{val=val*11;}

while(rem!=0)
{ rem=val%10;
if(rem==1) count++;
val=val/10; }

System.out.println("The number of one's are : "+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.