A polite number is a positive integer that can be written as the sum of two or more consecutive positive integers. Given N, find the N-th polite number.
Examples:
Input : 4
Output : 7
Explanation: The first 3 are 3(1+2), 5(2+3),
6(1+2+3).
Input : 7
Output : 11
Explanation: 3, 5, 6, 7, 9, 10, 11.
There exist an interesting pattern that only powers of 2 are not present in series of Polite numbers. Based on this fact, there exist below formula (Lambek–Moser theorem) for N-th polite number.
Here to find Nth polite number we have to take n as n+1 in the above equation
The inbuilt log function computes log base-e, so dividing it by log base-e 2 will give log base-2 value.
Given below is the implementation of the above approach:
C++
// CPP program to find Nth polite number#include <bits/stdc++.h>using namespace std;// function to evaluate Nth polite numberdouble polite(double n){ n += 1; double base = 2; return n + (log((n + (log(n) / log(base))))) / log(base);}// driver codeint main(){ double n = 7; cout << (int)polite(n); return 0;} |
Java
// Java program for finding N-th polite numberimport java.io.*;class GFG { // function to find N-th polite number static double polite(double n) { n += 1; double base = 2; return n + (Math.log((n + (Math.log(n) / Math.log(base))))) / Math.log(base); } // driver code public static void main(String[] args) { double n = 7; System.out.println((int)polite(n)); }} |
Python
import math# function to find Nth polite number def Polite(n): n = n + 1 return (int)(n+(math.log((n + math.log(n, 2)), 2))) # Driver coden = 7print Polite(n) |
C#
// Java program for finding // N-th polite numberusing System;class GFG { // Function to find N-th polite number static double polite(double n) { n += 1; double base1 = 2; return n + (Math.Log((n + (Math.Log(n) / Math.Log(base1))))) / Math.Log(base1); } // Driver code public static void Main(String []args) { double n = 7; Console.Write((int)polite(n)); }}// This code is contributed by// Smitha Dinesh Semwal |
PHP
<?php// PHP program to find// Nth polite number// function to evaluate // Nth polite numberfunction polite($n){ $n += 1; $base = 2; return $n + (log(($n + (log($n) / log($base))))) / log($base);}// Driver code$n = 7;echo((int)polite($n));// This code is contributed by Ajit.?> |
Javascript
<script>// Javascript program to find// Nth polite number// function to evaluate// Nth polite numberfunction polite(n){ n += 1; let base = 2; return n + (Math.log((n + (Math.log(n) / Math.log(base))))) / Math.log(base);}// Driver coden = 7;document.write(parseInt(polite(n)));// This code is contributed by _saurabh_jaiswal.</script> |
Output:
11
Time complexity: O(1)
Auxiliary space: O(1)
Reference: Wikipedia
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/n-th-polite-number/ […]