You are not logged in. Please login at www.codechef.com to post your questions!

×

LUCKFOUR - editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Kulik
Tester: Roman Furko
Editorialist: Balajiganapathi Senthilnathan

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic string

PROBLEM

For each number, you have to count the number of times the digit 4 occurs in it.

QUICK EXPLANATION

Input the number as a string and count the number of times the character '4' occurs in it.

EXPLANATION

We may be tempted to input the number as an int, but this is really a string related task. We have to count the number of times a particular character appears in the string. So, taking the input as a string helps us avoid all the complicated stuff we will have to do if we input as a number.

We just have to loop through all characters of the string and if it is '4', increment the answer.

It is also instructive to see how we can solve this if we treat the input as a number.

Say we have a number x = 12345. How can we extract its digits? Observe that we can easily get the rightmost digit(unit's place) - if we divide x by 10 and take the reminder, it will be the rightmost digit. Further, the quotient we get is the rest of the number. For example, 12345 = 1234 * 10 + 5. So we get both the unit's place digit and the rest of the number. Now to get the next digit, we continue in the same fashion. When should we stop? Suppose x is a single digit, say x = 1. Now the quotient after dividing by 10 is 0, and we can stop since there are no more digits to process.

Pseudocode:

ans = 0
while x > 0:
    remainder = x % 10
    quotient = x / 10
    if remainder == 4 ans++
    x = quotient

Complexity

The number of times the while loop will run is equal to the number of digits. Say d is the number of digits, the complexity will therefore be $O(d)$. Also, if we treat the input as integer, we can see that $d = \lceil log_{10}$ $n \rceil$. So, the complexity will be $\mathcal{O}(log$ $n)$.

AUTHOR'S, TESTER'S and Editorialist's SOLUTIONS:

setter
tester
editorialist

asked 18 Feb '15, 23:05

balajiganapath's gravatar image

6★balajiganapath ♦♦
75542742
accept rate: 77%

edited 16 Jun '15, 12:02

vicky002's gravatar image

1★vicky002 ♦♦
2561314


Even if the input is given as an integer (for example in TopCoder SRMs, you have to implement a function instead of reading inputs from STDIO), you could still use sprintf(C++) or str()(Python) or whatever methods your familiar language has and turn the number to string. This will reduce the possibility of making errors.

link

answered 22 Feb '15, 14:11

johnathan79717's gravatar image

4★johnathan79717
196125
accept rate: 0%

yes . Actaully just check s[i]=='4' .

link

answered 22 Feb '15, 14:13

adityakhanna1999's gravatar image

1★adityakhanna1999
1315
accept rate: 14%

I used numeric input rather than string and got AC

link

answered 22 Feb '15, 14:14

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

for _ in xrange(input()):
    print raw_input().count('4')

Gotta love python. :)

link

answered 22 Feb '15, 14:14

grebnesieh's gravatar image

7★grebnesieh
757211
accept rate: 16%

include<stdio.h>

include<conio.h>

struct count
{
char a[50];
}e[5];
void main() {
char i,j=0,c=0;

printf("enter the strings");
for(i=0;i<5;i++)
{
gets(e[i].a);
}

for(i=0;i<5;i++)
{
for(j=0;j<50;j++)
{
if(e[i].a[j]=='4')
c=c+1;
}
}
printf("number of 4s is %d",c);

getch();
}

link

answered 23 Feb '15, 01:49

pksinha_09's gravatar image

2★pksinha_09
112
accept rate: 0%

edited 23 Feb '15, 01:53

Another way

the difference between the length of original string and string.replace("4","") will give you the answer

public class NumberOfFours {

private static StringBuilder sb= new StringBuilder();

public static void main(String[] args) {

    Scanner input= new Scanner(System.in);
    int numberOfTestCases = input.nextInt();

    while(numberOfTestCases-- >0){

        String inputString = input.next();
        Solve(inputString);

    }
    System.out.println(sb);
}

private static void Solve(String inputString) {

    String s = inputString.replaceAll("4", "");

    int diff = inputString.length()-s.length();
    sb.append(Integer.toString(diff)).append("\n");
}

}

link

answered 24 Feb '15, 21:53

njr07121977's gravatar image

2★njr07121977
211
accept rate: 0%

For reference .... I have tried this and it worked for me

import java.lang.; import java.util.;

class four { public static void main(String[] args) { Scanner obj= new Scanner(System.in); int x,z; x= obj.nextInt(); if ((x>0)&&(x<=100000)) { int[] y; y = new int[x]; for(int i=0; i<x; i++) { z = obj.nextInt();

            int count = 0,a=1,b;

            while(a!=0)
            {
                b = z%10;
                if (b==4)
                {
                    count++;
                }
                a = z/10;
                z = a;
            }
            y[i] = count;
        }
        for(int j = 0 ; j <x ; j++)
        {
            System.out.println(y[j]);
        }
    }
}

}

link

answered 10 Jan '16, 17:37

drupadpreenja's gravatar image

0★drupadpreenja
1
accept rate: 0%

Is the second method is more efficient than the first method?

link

answered 01 Feb '16, 02:21

cruisedevice's gravatar image

0★cruisedevice
1
accept rate: 0%

Hi, I am not able to get following line : (Subtask 1): 0 ≤ Numbers from the list ≤ 9 - 33 points. (Subtask 2): 0 ≤ Numbers from the list ≤ 109 - 67 points.

can someone elaborate it?

Thanks

link

answered 05 Jun '16, 23:59

vijnux's gravatar image

0★vijnux
1
accept rate: 0%

i actually managed to receive 33 points so i guess i got Subtask 1, but i am not able to fulfill Subtask 2 although its the same as Sub1 but with different values. Can someone help me ? I am quite new to programming at all so my solution is not that good i guess :D

Thats what i got so far : (comments are in german, sorry)

https://www.codechef.com/viewsolution/12076756

link

answered 11 Nov '16, 19:07

coppice's gravatar image

0★coppice
1
accept rate: 0%

Hello Guys..!!

I have this C Code which I wrote for this problem. It runs fine and gives me the right answers in my Dev-C++ Environment. But the CodeChef Online Judge says Wrong answer and doesn't award me points. Can anyone please tell me what is the problem here...??

PS: Code Below


#include <stdio.h>

int main()
{
int T , rem , c , e ;

scanf("%d" , &T) ;

for ( int i = 0 ; i < T ; ++i )
{
    scanf("%d" , &e) ;

    while (e != 0)
    {
        rem = e % 10 ;

        if (rem == 4)
        {
            ++c ;
        }

        e = e / 10 ;
    }
    printf("%d\n" , c) ;
    c = 0 ;
}
}
link

answered 27 Dec '16, 14:04

sagar19l22's gravatar image

1★sagar19l22
584
accept rate: 7%

edited 27 Dec '16, 14:05

@sagar19122 I think you should define your c=0, because it will give wrong output when number is 0.

link

answered 23 Mar '18, 19:40

elli0t's gravatar image

4★elli0t
574
accept rate: 4%

How about this:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 0;
    string number = "";
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> number;
        cout << count(number.begin(), number.end(), '4') << "\n";
    }
}
link

answered 24 Aug '18, 23:00

salil03's gravatar image

2★salil03
306
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,688
×67

question asked: 18 Feb '15, 23:05

question was seen: 5,740 times

last updated: 24 Aug '18, 23:00