CareerCup

The first 10 numbers contain 9 numbers without 4.
The first 100 numbers contain (9*9) numbers without 4.
The first 1000 numbers contain (9*9*9) numbers without 4... and so on.
Store the number of numbers without 4 against each power of 10. Maybe in an array.

Split N into its powers of 10 like:
a*10^x + b*10^(x-1) + c*10^(x-2)+... and so on

Use the above array to calculate the total number, but beware of any 4s in a, b, c, etc.

So the total becomes:
a*(number of 4less numbers in first 10^x) + b*(number of 4less numbers in first 10^(x-1)) + ... and so on.

import java.util.*;

public class CountFours
{
    public CountFours()
    {
    }

    /**
     * Recursively count how many numbers below n don't have a 4 in decimal
     * representation.
     */
    public int count(int n)
    {
        // base case when we have single digit
        if (n < 4) {
            return n;
        }
        
        if (n >= 4 && n <=9) {
            return n - 1;
        }

        // otherwise for multi digit numbers, compute the order of magnitude
        int orderPower = (int) Math.floor(Math.log10(n));
        // actual number order 
        int order = (int) Math.pow(10, orderPower);

        // the first digit of the number n
        int d = (int) n / order;

        // the rest of the number when first digit is removed
        int remainder = n % order;

        // if the number starts with 4, then all of the remainder should not
        // be counted. Therefore, the count value is the same as number that
        // starts with d-1 as first digit and all the rest of digits are 9
        if (d == 4) {
            // remainder is all 9s
            remainder = (int) Math.pow(10, orderPower) - 1;
        }

        // compute the power of 9
        int ninePower = (int) Math.pow(9, orderPower);

        if (d < 4) {
            return d * ninePower + count(remainder);
        } else {
            return (d - 1) * ninePower + count(remainder);
        }
    }

    /**
     * Count number of times 4 appers in any number less than equal to
     * n by converting the numbers to string and comparing digits as chars.
     */
    public int naiveCount(int n)
    {
        int withoutFourCount = 0;

        for (int i = 1; i <= n; i++) {
            if (!containsFour(i)) {
                withoutFourCount++;
            }
        }

        return withoutFourCount;
    }

    /**
     * Check if the number contains 4 by converting the number to string,
     * walking through the string and looking for char '4'
     */
    public boolean containsFour(int n)
    {
        String value = String.valueOf(n);

        if (value.indexOf('4') != -1) {
            return true;
        }

        return false;
    }

    /**
     * Test recursive algorithm against naive algorithms for all numbers
     * up to n
     */
    public void test(int n) 
    {
        for (int i = 0; i <= n; i++) {
            if (naiveCount(i) != count(i)) {
                System.out.println("Recursive algorithm is wrong for n = "
                        + i);
                return;
            }
        }

        System.out.println("Passed for all numbers up to " + n);
    }

    /**
     * Print how many numbers below n do not contain 4
     */
    public void testCount(int n) 
    {
        System.out.println("For n = " + n + " there are " + count(n) 
                + " numbers that don't contain 4");
    }

    public static final void main(String args[])
    {
        CountFours app = new CountFours();
        app.test(10000);
        app.testCount(1000);
        app.testCount(Integer.MAX_VALUE);
    }
}

I have found more efficient algorithm of this problem， it uses recursion。

#include<iostream>
using namespace std;

#define count(x, y) ((x) <= 4 && (y) >= 4 ? (y) - (x) : (y) - (x) + 1)

int calculate_num(int N)
{
    int m, r;
    int result;

    m = N / 10;
    if (m == 0) {
        return count(0, N);
    }
    result = 0;
    r = N % 10;
    if (r > 0) {
        result += count(0, r - 1) * calculate_num(m);
    }
    result += count(r, 9) * calculate_num(m - 1);
    return result;
}

int main(int argc, char **argv)
{
    int n;

    cin >> n;
    cout << calculate_num(n) - 1 << endl;
    return 0;
}

A more optimized approach using recursion can be used:
C(k) : number of numbers of k digits that do not contain 4
N[k] : kth digit in the number N
f(k) : for a given digit k return the number of digits possible for that place (unit, tens, hunderds) e.g if k = 3 then we have 4 options 0,1,2,3 and if k = 5 then we have 5 options 0,1,2,3,5
The recursion equation will be
C(k+1) = (f(N[k]) -1)*(9^k) + C(k)
Base case
C(1) = f(N[1])

Note: This solution includes 0 as a number in its answer

Runs in constant time. Uses recursion and written in C++

int countExclude4(int n) {
	return (n - countContain4(n-1));
}

int countContain4(int n) {

	int factor = -1;
	int k = n;

	// Reached the unit digit
	if (k < 4) return 0;
	else if (k < 10) return 1;

	// Find the highest factor of n
	while (k > 0) {
		factor++;
		k /= 10;
	}

	// Find the number of numbers containing 4 in n/10
	int prevMax = 0;
	for (int i = 0; i < factor; ++i)
		prevMax = (prevMax * 9) + (int)pow(10, i);

	int quotient = n / (int)pow(10,factor);
	int remainder = n % (int)pow(10,factor);

	int sum = 0;

	// e.g 4 in 45623
	if (quotient == 4)
		sum = quotient * prevMax + (remainder + 1);
	// e.g 1 in 10000
	else if (quotient == 1 && remainder == 0)
		sum = prevMax;
	// e.g 2 in 273
	else if (quotient < 4)
		sum = quotient * prevMax + countContain4(remainder);
	// e.g 7 in 720324
	else
		sum = (quotient-1) * prevMax + (int)pow(10, factor) + countContain4(remainder);

	return sum;

}

class Googleque
def initialize(val)
@n=val
@array= Array.new
@i=0
@count=0
if @n <= 0 then
puts " No Positive numbers present"
else
logic
end
end

def logic
for i in 0..@n
calculation(i)    # Applying calculation logic for every number until 'N'
i=i+1
end
puts "Total no of positive integers which does not contain '4' it are.\n"
puts "#{@n-@count}"
end

def calculation(i)
@i= 0

until i==0
@array[@i]= i%10
i=i/10
@i=@i+1
end
if @array.include?(4) then
@count = @count+1
end

end

end

puts "Enter your number"
val= gets.to_i
ob= Googleque.new(val)

This can be solved by a recursive approach that works by removing Most Significant Digits(MSD) one at a time in each recursive step and counting the number of numbers that don't include 4.

Suppose the given integer N has k digits - d1,d2,...,dk. There are 2 cases: d1 < 4 and d1>=4 and the recursion yields itself as:

1. For d1 < 4
f(d1,d2,...,dk) = d1 * (k-1)^9 + f(d2,d3,..,dk)

2. For d1 >= 4
f(d1,d2,...,dk) = (d1-1) * (k-1)^9 + f(d2,d3,..,dk)

Both can as well be combined to:
f(d1,d2,...,dk) = [(d1 - floor((d1)/4) - floor((d1)/8)) * (k-1)^9] + f(d2,d3,..,dk)

The base cases are:
f(d) = d, for d<4. [It could have been d+1, had the question not been asking for numbers *lesser* than the given number]

f(d) = d - 1, for d>=4 [It could have been d, had the question not been asking for numbers *lesser* than the given number]

def nine_based_numeral_system(max)
    sw  = count = 0
    pos = max.to_s.length

    max.to_s.scan(/./).each do |number|
      number = number.to_i
      if number == @filter && sw == 0
        number -= 1                     # As will be the same result 4xx than 399
        sw      = 1
      elsif sw == 1
        number = 9                      # As it has a previous 4 so this is the same as 3xxx
      elsif number > @filter
        number -= 1
      end
      pos   -= 1
      count += number * 9 ** pos
    end
    count -= 1
  end
end

}

Written in C#

int N = int.Parse(Console.ReadLine());
            string[] dizi = new string[N];
            int counter = 0;
            for (int i = 0; i < N; i++)
            {
                bool isContainFour = false;
                dizi[i] = i.ToString();
                for (int j = 0; j < dizi[i].Length; j++)
                {
                    if (dizi[i][j] == '4')
                    {
                        isContainFour = true;
                    }
                }
                if (isContainFour == false)
                {
                    counter++;
                    //possible to write those numbers
                    //Console.WriteLine(dizi[i]);
                }
            }
            Console.WriteLine(counter);
            Console.ReadLine();

void countNot4(unsigned int N)
{
	int count =0;
	
	for(int i=1;i<N;i++)
	{
		bool isFour = false;
		int k=0;
		char a[25];
		itoa(i,a,10);
		while(a[k]!='\0')
		{
			if(a[k]=='4')
			{
				isFour = true;
				break;
			}
			k++;
		}
		if(!isFour)
			count++;
	}
	cout << "\n Count is .." << count;
}

public class NonFour {        
    public long getNonFourCount(long N) {
        int numberOfDigits = (int)Math.floor(Math.log10(N)) + 1;
        int fisrtDigit = (int)(N / (long)Math.pow(10, numberOfDigits-1));
        
        long count =0;
        if(N<10) {
            for(int j = 0; j<=N; j++) {
                if(j!=4)
                    count++;
            }
            return count;
        }
        
        long pow = (long)Math.pow(9, numberOfDigits-1);
        count = pow;
        
        for(int i =1; i< fisrtDigit; i++) {
            if(i != 4) {
                count += pow;
            }
        }
        
        N = N % (long)Math.pow(10, numberOfDigits-1);
        return count + (N==0? 1 : getNonFourCount(N));
    }
    
}

Sorry, in my last solution didn't take care of numbers starting with 4. This is not brute-force:

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package javatest;

/**
*
* @author neerajks
*/
public class NonFour {
public long getNonFourCount(long N) {
int numberOfDigits = (int)Math.floor(Math.log10(N)) + 1;
int fisrtDigit = (int)(N / (long)Math.pow(10, numberOfDigits-1));

long count =0;
if(N<10) {
for(int j = 0; j<=N; j++) {
if(j!=4)
count++;
}
return count;
}

long pow = (long)Math.pow(9, numberOfDigits-1);
count = pow;

for(int i =1; i< fisrtDigit; i++) {
if(i != 4) {
count += pow;
}
}

N = N % (long)Math.pow(10, numberOfDigits-1);
return fisrtDigit !=4 ? count + (N==0? 1 : getNonFourCount(N)) : count;
}

}

import java.util.Scanner;

/**
 *
 * @author uğur
 */
public class CountNumber {
    
    public static void main (String args[]) {
        
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        
        int count = 0;
        
        for (int i = 0 ; i < n ; i++ ) {
            if ( !containFour(i)) {
                count++;
            }
        }
        
        System.out.println(count);
        
    }
    
    public static boolean containFour(int i) {
        
        return String.valueOf(i).contains("4");
                
    }
    
}

What about this :P

public int integerCount(int N)

{

int count = 0;

for(int i =0 ; i < N; i++)

{

if(!Integer.toString(i).contains("4"))

{

count++;

}

}

return count;
}

int pow = 0;
        int sum = 0;
        int digit = 0;
        while (number > 0) {
            digit = number % 10;
            sum += (digit > 4)? ((digit-1) * power (9,pow)) :
                           ((digit) * power (9,pow));
            number /= 10;
            pow++;
        }

#include <stdio.h>
#include <string.h>

main()
{

int N = 40;

int rem = 0;
int mul = 1;
int temp = N;
int noOftimes = 0;


while(temp){

rem = temp % 10;

if(rem == 0){
rem = 10;
}
noOftimes += (rem-1)*mul;
mul = mul*9;
temp = temp/10;


}

printf(" Number of times 4 is not present in %d is %d",N, noOftimes);




}

If you are reading this, then hats off to you.

Here is my take on the solution.

public static int countNos(int N) {
        if (N < 0) {
            throw new IllegalArgumentException("Input cannot be less than zero");
        }

        int[] digits = getDigits(N);
        int sum = 0;

        for (int i = 0; i < digits.length; i++) {
            if(digits[i] == 4) {
                digits[i] = 3;
            }
            
            int x = digits[i] > 4 ? digits[i] - 1 : digits[i];
            x = (int) (x * Math.pow(9, digits.length - (i + 1)));
            sum += x;
        }
        
        return sum;
    }

    private static int[] getDigits(int num) {
        if (num == 0)
            return new int[1];

        int size = (int) Math.log10(num) + 1;
        int[] digits = new int[size];

        int n = num;
        for (int i = size - 1; i >= 0; i--) {
            digits[i] = n % 10;
            n = (n - digits[i]) / 10;
        }

        return digits;
    }

public static void main(String[] args) throws Exception{
       int N;
       Scanner in = new Scanner(System.in);
       System.out.println("Enter an integer: ");
       N= in.nextInt();
       int count = 0;
       System.out.println("Integer entered by user: "+N);  
       for(int i =1; i<N ; i++) {
           StringBuilder sb = new StringBuilder();
           sb.append("");
           sb.append(i);
           String strI = sb.toString();
           if(!strI.contains("4")) {
               count += 1;
           }           
       }
        System.out.println("Number of positive integers less than "+N+" that do not contain 4 are: "+count);         
    }

int _count(int num, int dec_n, int *inc_sum) {
    if (num == 0) {
        *inc_sum = 1;
        return 0;
    }

    int sum = _count(num/10, dec_n+1, inc_sum);

    int s, q = (num %10);

    /* 
     * If any of the msd has a 4 then no need to calculate the count
     */
    if (*inc_sum) {
        if (q == 4){
            s = (q * power(9, dec_n)) -1;
            (*inc_sum) = 0; // for lsd

        } else {
            q = (q < 4) ? q : q-1;
            s = q * power(9, dec_n);
            (*inc_sum) = 1;
        }

        sum += s;
    }

    return sum;
}

int count (int num) {
    int inc_sum;
    return _count(num, 0, &inc_sum);
}

//Brute Force
public int count(int N){
		int sum = 0, i = 0;
		String s;
		while (i++ < N){
			s = Integer.toString(i);
			if (s.indexOf("4") == -1) sum++;
		}
		return sum;
	}

/*
* Pouya Karimi - This code is written in C
*/
#include <iostream>
int main(int argc, char const *argv[])
{
int a, counter = 0, b;
std::cout << "Enter a number: ";
std::cin >> a;
for(int i=1;i<=a;i++){
b = i;
while ( b != 0 ){
if(b % 10 == 4){
counter ++;
}
b = b/10;
}
}

std::cout << "The number is: " << a-counter << "\n" ;
return 0;
}

void getCountForNumber(int num)
{
    int count = 0;
    for (int i = 1; i< num; i++)
    {
        int temp = i;
        while ( temp )
        {
            if ( temp % 10 == 4 )
            {
                //Digit 4 found.
                break;
            }
            temp /= 10;
        }

        if ( temp == 0)
        {
            ++count;
        }
    }
    std::cout<<"\nNumbers found : "<<count;
}