우리는 정수로 주어진다. N은 제수로 간주되며 1 - N부터 시작하는 숫자로 나누어지며 작업은 설정된 비트 수가 더 많은 제수의 수를 계산하는 것입니다. 주어진 숫자 N으로 나눈 몫.
예
입력 - 정수 N =6
출력 - N을 나눌 때 몫보다 더 많은 세트 비트를 갖는 제수의 수는 다음과 같습니다. 5
설명 - 먼저 숫자 N을 1 - N부터 시작하는 숫자로 나누고 제수의 세트 비트와 몫을 계산합니다. 즉
1-> N =6 /1(1) =6(2) =1 <2 =고려하지 않음
2-> N =6 /2(1) =3(2) =2 =2 =고려됨
3-> N =6 /3(2) =2(1) =2> 1 =고려됨
4-> N =6 /4(1) =1(1) =1 =1 =고려됨
5-> N =6 /5(2) =1(1) =2> 1 =고려됨
6-> N =6 /6(2) =1(1) =2>1 =고려됨
보시다시피 고려된 경우를 선택하고 출력은 5가 됩니다.
입력 - 정수 N =10
출력 - N을 나눌 때 몫보다 더 많은 세트 비트를 갖는 제수의 수는 다음과 같습니다. 8
설명 - 먼저 숫자 N을 1 - N부터 시작하는 숫자로 나누고 제수의 세트 비트와 몫을 계산합니다. 즉
1-> N =10 /1(1) =10(2) =1 <2 =고려되지 않음
2-> N =10 /2(1) =5(2) =2 =2 =고려됨
3-> N =10 /3(2) =3(2) =2 =2 =고려됨
4-> N =10 /4(1) =2(1) =1 <2 =고려하지 않음
5-> N =10 /5(2) =2(1) =2> 2 =고려됨
6-> N =10 /6(2) =1(1) =2>1 =고려됨
7-> N =10 /7(3) =1(1) =3>1 =고려됨
8-> N =10 /8(1) =1(1) =1 =1 =고려됨
9-> N =10 /9(2) =1(1) =2> 2 =고려됨
10-> N =10 /10(2) =1(1) =2> 1 =고려됨
보시다시피 고려된 경우를 선택하고 출력은 8이 됩니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
- 양의 정수 N을 입력하고 함수 divisors_quotient()에 인수로 전달합니다.
- divisors_quotient()
- 함수 내부
- N - 함수 set_quo(N) + 1에 대한 호출을 반환하고 set_quo() 함수로 이동
- set_quo() 함수 내부
- 시작과 끝으로 임시 변수를 만들고 시작을 1로 초기화하고 sqrt(N)으로 끝냅니다.
- start
- IF(verify() 함수 호출 및 인수로 temp 및 N 전달)를 확인한 다음 end를 temp로 설정
- ELSE, 시작을 임시 + 1로 설정
- IF(! verify() 함수를 호출하고 temp와 N을 인수로 전달) start + 1을 반환합니다.
- ELSE, 리턴 시작
- verify() 함수 내부
- IF(val_bit(temp/val) 함수 호출이 val_bit(val) 함수 호출보다 작음)를 확인한 다음 true를 반환하고 그렇지 않으면 False를 반환합니다.
- val_bit()
- 함수 내부
- 결과를 저장할 임시 변수 개수를 선언합니다.
- 시작 루프 WHILE val에 값이 있습니다. 루프 내에서 val을 val / 2로 설정하고 카운트를 1만큼 늘립니다.
- 반환 횟수.
예시
#include <bits/stdc++.h>
using namespace std;
int val_bit(int val) {
int count = 0;
while (val) {
val = val / 2;
count++;
}
return count;
}
bool verify(int val, int temp) {
if (val_bit(temp / val) <= val_bit(val)) {
return true;
}
return false;
}
int set_quo(int N) {
int start = 1;
int end = sqrt(N);
while (start < end) {
int temp = (start + end) / 2;
if (verify(temp, N)) {
end = temp;
} else {
start = temp + 1;
}
}
if (!verify(start, N)) {
return start + 1;
} else {
return start;
}
}
int divisors_quotient(int N) {
return N - set_quo(N) + 1;
}
int main() {
int N = 10;
cout << "Count of divisors having more set bits than quotient on dividing N are: " << divisors_quotient(N);
return 0;
} 위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
출력
Count of divisors having more set bits than quotient on dividing N are: 8