Algorithm

Problem Name: beecrowd | 2544

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2544

Kage Bunshin no Jutsu

 

By Ricardo Oliveira, UFPR BR Brazil

Timelimit: 1

Kage Bunshin no Jutsu (or the "Shadow Clone Technique", for English speakers) is a ancient technique often used during ninja battles.

When used, the technique creates a copy identical to its user. That way, if a given ninja uses the technique, a copy of that ninja comes to existence, so there are two of the same ninja (the original one and his copy).

The technique is always executed by all ninjas existing in the moment. That way, if the technique is used again, there will be four ninjas in total (the two previous ones and two new copies), and so on.

There are N copies of a given ninja (including the original one). Your task is to determine how many times the technique was used.

 

Input

 

The input contains several test cases. Each test case contains a line with the number N (1 ≤ N ≤ 106). It is guaranteed that N is such that it is possible to get exactly N copies of a ninja (including the original one).

The input ends with end-of-file (EOF).

 

Output

 

For each test case, print a line with the number of times the technique was used.

 

 

 

Input Sample Output Sample

1
2
4

0
1
2

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <math.h>

int main(void)

{
    int i, j, n;

    while (scanf("%i", &n) != EOF)
    {
        j=log(n)/log(2);
        printf("%i\n", j);
    }

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
1 2 4

Output

x
–
+
cmd
0 1 2

#2 Code Example with C++ Programming

Code - C++ Programming


#include<iostream>
using namespace std;
int main(){
	int a;
	while(cin >> a){
		if(a == 1)
		cout << 0 << endl;
		else{
			int count = 0;
			int sum = 1;
			for(int i = 1;; i++){
				 sum = sum*2;
				 count++;
				 if(sum > a)
				 break;
				 if(sum == a)
				 break;
				}
				cout << count << endl;
			}
		}
		return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
1 2 4

Output

x
–
+
cmd
0 1 2

#3 Code Example with Java Programming

Code - Java Programming


import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()) {
			int total = sc.nextInt();
			int conta=0;
			while(total!=1) {
				if (total%2==0) {
					total/=2;
					conta++;
				}
				else
					return;
			}
			System.out.println(conta);
		}
		sc.close();
	}
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
1 2 4

Output

x
–
+
cmd
0 1 2

#4 Code Example with Javascript Programming

Code - Javascript Programming


const { readFileSync } = require("fs")
const input = readFileSync("/dev/stdin", "utf8")
	.split("\n")
	.map((value) => Number.parseInt(value, 10))

function main() {
	const responses = []

	for (let i = 0; isNaN(input[i]) == false; i++)
		responses.push(Math.log2(input[i]))

	console.log(responses.join("\n"))
}

main()
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
1 2 4

Output

x
–
+
cmd
0 1 2
Advertisements

Demonstration

Previous
#2543 Beecrowd Online Judge Solution 2543 UFPR Gaming Solution in C, C++, Java, Js and Python
Next
1546 Beecrowd Online Judge solution Feedback adhoc solution in C, C++